Uncovering the overlapping community structure of complex networks in nature and society

書名（以學術體例詳填資料，網路來源提供超連結及檢索日）：

Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.

* 匈牙利生物物理學學者

導讀者：朱蘊兒                    

原作摘要：

自然界和社會中的許多複雜系統都以網絡的狀態存在，且這些網絡往往為層級結構。為了解釋這些網絡的結構，我們需要將大網絡切分成內部連結更密集的子群（communities），而目前我們所知的那些分群方式往往會將大網絡切分成沒有重疊的子群，可實際中大多數的網絡都是相互交疊的。

本文我們將先介紹有重疊子群的網絡在統計上的特征，接著再介紹我們效率很高的一個檢測大規模網絡中交互重疊子群的工具。

重點整理：

一、 研究背景

在一個網絡中總會有一部分節點間的連結密度高於其他節點，這群節點的組合常被我們稱作：clusters、communities、cohesive groups、modules，莫衷一是。但目前的分群方式常常分出來的都是沒有交集的子群，這與實際情況不符，我們每個人都從屬於不同的群體，家庭、學校、興趣團體等等，而每種蛋白質片段都可以從屬於不同的蛋白質。

圖一 重疊性子群示例

b) 分裂式分群方式

c) k-clique-community (k=4) *重疊的節點用紅色標誌

1.     K-clique：由k個節點組成的完全子圖，每兩個節點間都有連結。

2.     K-clique-community：兩個K-clique間若有K-1個節點重合，即有某個節點與某個K-clique中的K-1個節點有連結，則將兩個K-clique合併為一個 K-clique-community，重複此合併動作直至沒有節點可以被納入子群。

* 限制：只能分析二元網絡（沒有方向、沒有權重）

→ 任意圖都可以簡化為二元網絡：忽略方向、設置權重門檻，門檻以上為1，以下為0

二、 案例介紹

使用了三個ego-network作為分析案例：

1.     學者的合著網絡：以物理學家G. Parisi為例，從the Los Alamos cond-mat archive學術資料庫中搜索並建立與他的合著學者網絡。

2.     詞語共現網絡：在認知心理學領域，與bright這個詞共同出現的詞語網絡。

3.     蛋白質網絡：在DIP core list of the protein-protein interactions列表中羅列出的，釀酒酵母中，以蛋白質ZDS1為中心，若不同的蛋白質存在於同一個蛋白質複合體或者擁有相同功能，則其之間有一條邊，繪製出蛋白質網絡。

圖二 三種示範網絡

* K-clique-communities的K=4

* 用不同顏色標記不同子群(community)，若點或邊同時存在於兩個以上子群，那麼以紅色標記來凸顯它們的特殊性。

* 蛋白質網絡具有預測蛋白質功能的作用：比如在圖三中，Ycr072c這個蛋白質的功能未明，經過k-clique-community分群后，被分入了墨綠色那一群，從GO-TermFinder package中檢索該子群中每一個蛋白質的功能，發現出現次數最高的是「合成核糖體」，未明可以推測該蛋白質的功能也是「合成核糖體」。

三、 如何找到最有效的分類？

我們可以做個實驗，逐一嘗試可能的K（3到6之間）與權重門檻w，看看分類結果如何。需要知道的是隨著K的提升，網絡中的子群越來越少，而隨著權重門檻w的提升，網絡中的邊也越來越少，網絡的結構也變得越來越散。

如何評價分類結果：

1.     一個有意義的分群結果應當是這樣的：群內邊的密度較群外高、約束性不必太高（？）、不能忽略關鍵的切分點（將它們移除后子群就散了）、子群間有重疊。

2.     一個壞的分類結果：「過濾現象」，就是當門檻降低、邊的數量提升到一個程度時，會出現巨型子群，為了防止這一現象出現，研究者要求分類結果中最大子群不能超過次大子群規模的兩倍，這樣我們才能找到足夠多的子群，不會分得太粗以至於結構中的細節被掩蓋。

→ 邊夠多：權重門檻w不能太大，保留下來的邊占原來邊的數量的比例f*不會低於50%。

→ 點夠多：K不能太大，未被分群的散落節點不能多於一半。

最後的參數配置：

1.     學者合著網絡：k=5，f*=93%；k=6，f*=75%；

2.     詞語共現網絡：k=4，f*=67%；

3.     蛋白質網絡：k=4。

蛋白質網絡分出了非常分散的82個子群，如圖三所示。

圖三 蛋白質網絡的子群網絡

* 邊的粗細與點的大小取決於它們佔據了幾個子群。

四、 研究發現

1.     子群內的節點數量的分佈符合冪律分佈，但指數較小，1<c<1.6

2.     子群間的連結數量（community degree）也符合冪律分佈，且與節點數的分佈成正比，也就是說，每個節點都貢獻了一定的連結數給子群，隨著節點數的增長，子群間的連結數量也在等比例增長。

3.     子群重疊的節點數量（即重疊大小）也符合冪律分佈，且指數很大，因此我們推論，沒有典型的重疊大小。子群數量亦然。

l  Junior：不理解，如果符合冪律分佈應當是要有典型的重疊大小，且這一典型的重疊大小出現的頻率要遠遠高於其他重疊大小。

4.     如表一，學者合著網絡和詞語共現網絡的平均聚類係數（average clustering coefficients）較高，這意味著不同子群間的重疊比例比較高、凝聚程度比較高。

5.     由子群構成的網路，其邊的分佈呈指數式分佈，而以點構成的網絡，就沒有這個特徵→不同層級有不同特征

6.     這樣的方法可以幫我們解析層級式的網絡傳播，比如病毒或網絡信息

* i和j為網絡中任意兩節點，若兩節點間有邊則Aij=1（無權重）/w（有權重），沒有邊則為0。m為邊的總數。ki和kj分別為i和j的連結數，若節點i 與節點j 同屬一個分群，則δ(ci,cj)為1，否則δ(ci,cj)為0。

* Q∈[-1,1]。如果組內連結密度與組外無差別，則Q=0。Q>0.3則被視為是好的、有意義的分組結果(Clauset & Newman & Moore, 2004)。

a)Girvan-Newman：割裂法，由整到分，做法是先將所有節點視為一個子群，不斷移除連結中介性（edge betweeness）[1]最高的邊，以達到切割網絡的目的，直到Modualrity的Q值達到最高值。哈哈哈竟然與我之前人工做的預處理的邏輯非常相似。計算速度慢，需要花費O(m2n)的時間，m為邊數，n為節點數。

b)   Clauset-Newman-Moore：融合法，由分到整，做法是將所有節點預設為單獨子群，而後逐一測試兩兩子群的融合，看哪兩個子群的融合最能提升Q，則融合這兩個子群，重複此過程，直到Q達到最高值。比G-N算法更節約資源、更高效，只需耗費O(nlog2n)的時間即可，因而可以分析大型網絡。

2.    Gephi的Modularity分群演算法：兩步驟融合，第一步類似Clauset-Newman-Moore，只是它不是進行任意兩個節點的合併測試，而是進行任意兩個相連節點的合併測試，減少一些計算量；第二步在第一步合併出的子群的基礎上，進行子群間合併，子群間的邊的權重等於原本節點間連結的總和，直到Q達到最大值。可以得到比Clauset-Newman-Moore更高的Q，可以處理更多節點，處理速度更快，且分出巨型子群的概率比Clauset-Newman-Moore來得小（Blondel & Guillaume & Lambiotte & Lefebvre, 2008）。

延伸閱讀：(請用學術體例將參考文獻中值得延伸閱讀之文章、書籍或網址列於此處)

1.    Clauset-Newman-Moore演算法：Clauset, A., Newman, M. E., & Moore, C. (2004). Finding community structure in very large networks. Physical review E, 70(6), 066111.

2.    Girvan-Newman演算法：M. Girvan and M.E.J. Newman, “Community structure in social and biological networks”, Proceedings of the National Academy of Sciences, Vol. 99, 2002, pp. 7821–7826.

3.    Gephi的Modularity演算法：Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):1-11.

4.    K-core演算法：Batagelj, V., & Zaversnik, M. (2003). An O (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049.

5.    蘇怡仁、溫建成、許維麟、陳岳群（2012）。〈以重疊社群分析引文網路支援論文自動分類之探討〉，第八屆知識社群國際研討會，台北。

與危機傳播相關之關鍵字及其概念內涵：

□ __________： 

□ __________：

□ __________：

□ __________：

資料狀況：

■ 電子檔（摘要／全文）:      全文     

□ 紙本（摘要／全文）:           

□ 其他狀況：           

如有重要相關圖表及附件請附在本頁後面，並在「其他狀況」項目內註明，如：附圖二張。

[1] 該邊出現在網路中任意兩個節點間最短路徑上的次數