複雜網路中橋接式與強鍵式連結之偵測、分析與應用

Bridge and Bond Link in Complex Networks: Detection, Analysis and Applications

黃全榮

指導教授 ： 孫春在

國立交通大學/資訊學院/多媒體工程研究所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00339

摘要

強弱連結是分析複雜網路的核心概念之一。然而，先前的研究對於網路連結強弱的定義面臨兩種挑戰：一、對於模糊不清的強弱定義，在應用上認定困難。二、雖然嚴格定義了強弱的界線，卻以非強即弱的判斷方式區分連結性質，未能反映許多真實網路的性質。我們強調複雜網路具有階層性質，並認為複雜網路中的連結在不同階層時具有不同的特性，有些連結對於區域訊息傳遞具有較大的影響力，但是對於全域訊息傳遞的影響力較低；有些連結對於區域到全域的訊息傳遞都極具影響力。
為了避免在量化連結性質時模糊不清的強弱定義或非強即弱的判斷方式，我們基於連結特性提出了橋接式與強鍵式連結的概念，並且設計一套偵測演算法，該演算法能夠依據拓樸與統計上的意義偵測出某特定連結在不同網路階層中所具有的性質。在分析之後，我們將連結分為下列四種類型：全域橋接式連結、N階橋接式連結、強鍵式連結和沉沒橋接式連結。以此為基礎，我們觀察三種不同類型真實網路中連結在不同階層時具有的性質，瞭解網路中每一條連結從區域觀點到全域觀點的性質變化，並且依據演算法將連結分成不同類型。藉由這些不同類型的連結在網路中存在的比例，我們能夠描述網路的拓樸性質與動態特性。
最後，我們以連結的階層性質與連結類型分佈比例為基礎提出了三個應用：一、尋找網路中的社群結構。二、真實網路分群。三、分析真實網路與理論網路在拓樸架構上的相似性。實驗結果顯示，本研究提出的概念除了在這些應用上得到不錯的結果之外，更能夠以一致的概念與方法解決不同的問題，說明了掌握連結的階層性質能夠給予研究學者在網路拓樸架構的建構或演化原理上更深入的瞭解。

關鍵字

強弱連結 ； 複雜網路 ； 分群 ； 社群結構

並列摘要

A concept of strong-ties and weak-ties played an important role in complex network studies. However, different researcher would face following problem in defining strong or weak of links: (1) Ambiguous definition between strong and weak, and (2) Clear definition of limit between strong and weak but link is either strong-tie or weak tie (dichotomy method). We considered that characteristic of links varies in different network layers (hierarchy property). Some links have obvious influence on information transmission in local area, but have no effect on information transmission in global scale; and some link have significant influence on information transmission from local to global scale.
To avoid ambiguous definition and dichotomy method when quantifying links, we applied characteristic of links to propose the concept of bridge link and bond link, and designed an algorism which can detect varies characteristic of links in the different network layers according to topology properties and statistically significant, then classify links into four types：Global bridge link, N degree bridge link, Bond link, and Sink bridge link. In this paper, we observed the characteristic of links in different layers under three real networks, and realized variation in properties of every links from local to global view, then classified links into different types according to the algorism. We can describe the topology structure and specific dynamic properties of networks by means of the proportion of different link types.
Ultimately, we proposed three applications based on hierarchy property of links and the proportion of different link types: (1) find community structure in complex network; (2) complex network clustering; (3) analyzing the correlation between real-world network and theoretic network on topology structure. The results demonstrated that the concept we proposed not only led to decent results on these applications, but also resolved different problems with the consistent methodology. By analyzing and realizing hierarchy property of links, researchers in many fields of science will have a better understanding of design principle or evolution principle beyond complex network.

並列關鍵字

strong-ties and weak-ties ； complex network ； clustering ； community structure

參考文獻

Albert, R. and Barabsi, A. L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47-97.

Artzy-Randrup, Y., Fleishman, S. J., Ben-Tal, N., and Stone, L. (2004). Comment on "network motifs: Simple building blocks of complex networks" and uperfamilies of evolved and designed networks". Science, 305(5687):1107c+.

Barabasi, A. L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439):509-512.

Barrat, A., Barthelemy, M., Pastor-Satorras, R., and Vespignani, A. (2003). The architecture of complex weighted networks.

Bascompte, J., Melin, C. J., and Sala, E. (2005). Interaction strength combinations and the overfishing of a marine food web. Proceedings of the National Academy of Sciences of the United States of America, 102(15):5443-5447.