社團結構

從 集智百科
跳到: 導覽搜尋

在網絡科學研究中,如果某個網絡中的節點可以輕易地被劃分為若干個內部緊密連接的節點集(集合間可能重合),那麼就可以說這個網絡具有社團結構 Community structure。在節點集不重疊的特殊情況下,網絡自然地被分成一個個節點集,這些節點集內部連接緊密而節點集與節點集之間連接稀疏(但也存在節點集重疊的情況)。 更廣泛的定義基於這樣一個原則:即如果節點對都屬於同一個社團,則更有可能相互連接;如果它們不屬於同一個社團,則更不可能相互連接。 一個相關但不同的問題是社團搜索,其目標是找到某個節點所屬的社團。


目錄

屬性

在研究計算機、信息網絡、社會網絡和生物網絡等網絡時,經常發現網絡具有許多不同的特徵,包括小世界性 Small-world property重尾度分佈 Heavy-tailed degree distributions 聚集性 Clustering 等。 而網絡也具有共同特徵——都具有社團結構。社團結構指的是網絡中內部連接比其餘部分更加密集的節點組。 這種聯繫的不均勻性表明網絡內部存在某種自然的劃分。將節點集進行劃分,就產生了一個個社團。也就是說,每個節點被放入一個社團中,且該社團唯一,這是一個有用的簡化,多數社團檢測算法都適用於這種類型的社團結構。 然而,在某些情況下,則是一個節點位於多個社團(即社團具有重疊性 )的社團結構能夠更好表示所研究的對象。這可能發生在社交網絡中:每個節點代表一個人,而社團代表不同的朋友群體,如: 一個社團代表家庭,另一個社團代表同事,還有一個社團代表來自同一體育俱樂部的朋友等等。 下面所討論的基於團結構的社團檢測算法 Clique-based method 的例子,就屬於這種具有重疊性的社團結構。


有些網絡可能不具有任何有意義的社團結構。例如許多基本的網絡模型,例如隨機圖 Random graph Barabsi-Albert 模型 Barabási–Albert model 就不具有社團結構。

重要性

一個演示社團結構的小型網絡草圖,包含三組內部緊密連接的節點,各組之間連接較為稀疏

社團結構在實際網絡中相當常見,社會網絡包括基於共同位置、興趣、職業等的社團團體(實際上是這個術語的起源)。在網絡中找到一個潛在的社團結構(如果它存在的話)是很重要的,重要原因有很多:


首先,社團允許我們創建一個大範圍的網絡地圖,因為單個社團就像網絡中的元節點,這使得研究更加容易;其次,由於社團通常與系統的功能單元相對應,因此單個社團也能闡明網絡所代表的系統功能。如在代謝網絡中,這些功能組對應於周期或路徑;而在蛋白質相互作用網絡 Protein interaction network 中,社團對應於生物細胞內具有類似功能的蛋白質;在引用網絡中,社團對應於研究主題。 而識別網絡中的子結構,有助於深入了解網絡的功能以及拓撲效應之間是如何相互影響的。這種見解對於改進譜聚類 Spectral clustering 等圖的數據處理算法有一定的參考價值。


此外,社團的重要性還體現在:它們的屬性通常與網絡的普遍屬性迥異。因此,只關注普遍屬性通常會忽略網絡內部許多重要且有趣的特性。例如,在一個給定的社交網絡中,愛交際的群體和沉默寡言的群體可能同時存在。


其次,社團的存在通常也會影響到傳播過程,如在網絡上發生的謠言傳播或流行病傳播。 因此,為了正確理解這些過程,最重要的就是檢測社團,並研究它們如何在各種環境下影響傳播過程。


最後,社團檢測在網絡科學中的一個重要應用是預測網絡中的缺失鏈接和識別網絡中的錯誤鏈接。 在測量過程中,由於多種原因,有些鏈接可能無法被觀察到。 同樣,由於測量中的失誤,一些鏈接可能會錯誤地輸入數據。 社團檢測算法很好地處理了這兩種情況,因為它允許給定節點對之間存在連邊。

社團檢測算法

在任意網絡中檢測社團可能是一項困難的計算任務。 網絡中的社團數目(如果存在的話)通常是未知的,且社團規模和密度往往不同。儘管存在這些困難,一些檢測社團的方法已經被發展和應用,並取得了不同程度的成功。

最小割法

將網絡劃分為若干部分的最古老的算法之一是最小割法(以及諸如比率割法和歸一化割法等變體)。 此方法可用於並行計算的負載平衡,儘可能減少處理器節點之間的通信。


在最小割法中,網絡被分割成預定數量且大小相似的部分,選擇這些部分使得節點組之間的邊數達到最小。這種算法在許多應用程序中運行良好,但並不適用於檢測一般網絡中的社團結構,因為不論社團是否隱含在結構中,它只能找到數目固定的社團,而社團的數目通常是未知的。


層次聚類

在網絡中檢測社團結構的另一種方法是層次聚類 Hierarchical clustering 。 在這種算法中,定義了一種相似性度量 Similarity measure ,去量化節點對之間的某些(通常是拓撲的)相似性。 常用的測量方法包括餘弦距離健康指數 Cosine similarity 雅卡德指數 Jaccard index ,以及漢明距離健康指數鄰接矩陣 Hamming distance between rows of the adjacency matrix 。 然後根據該算法將相似的節點分組到同一個社團中。


有幾種常見的分組方案,其中最簡單的兩種是單鏈接聚類和完全鏈接聚類 Complete linkage clustering 。前者在不同群組中的所有節點對的相似度小於給定的閾值的情況下,將兩個群組視為獨立的社團; 後者則是在每個群組中的所有節點對的相似度大於給定的閾值的前提之下進行分組。 一個有趣的方法是使用各種相似或不同的測度,通過凸和 convex sums 來改進層次聚類的性能。


Girvan-Newman 社團檢測算法

另一個常見的社團檢測算法是 Girvan-Newman 算法 Girvan–Newman algorithm :首先識別社群之間連接的邊,然後去除這些邊,留下的就是社團。 該方法利用圖論中的中心性度量來進行識別,當邊位於多對節點之間時,給每條邊賦予一個較大的數字。


Girvan-Newman算法返回的結果具有較好的質量,且由於它與許多標準軟件包兼容,因此得到廣泛應用。但其運行緩慢,在n個頂點和m條邊的網絡上耗費時長為O(m2n),導致其並不適用於超過幾千個節點的網絡。

模板度最大值

儘管模板度最大值法有着它眾所周知的缺點,但它依然是用於使用最為廣泛的社團檢測算法之一。 模塊度 Modularity是一種衡量社團劃分質量的標準,也是一個利益函數。 模塊度最大值法通過搜索一個或多個具有特別高的模塊化的網絡的可能劃分來檢測社團。由於對所有可能的劃分進行窮舉搜索十分困難,所以實際的算法都是基於近似優化方法,如貪婪算法,模擬退火或光譜優化。不同的算法使得檢測速度和準確性之間達到不同類型的平衡。 一種流行的模塊度最大值法是 Louvain 算法 Louvain method ,該算法迭代地優化本地社團,直到社團狀態不再變化、全局模塊化不能夠再得到改善。 一個利用RenEEL的算法是當前最優良的模塊度最大值算法,該算法是一個極值集成學習EEL範式 Extremal Ensemble Learning paradigm 的例子。


模塊度優化的有效性是值得懷疑的,因為已經證明模塊度優化受分辨率的大小限制,這導致我們往往不能檢測到比某個規模更小的集群; 另一方面,由於模塊度值表徵着具有高模塊化的大量分區的簡併度,接近絕對最大值,這可能與其他算法非常的不同。

基於推論統計學的社團檢測算法

基於推論統計學 statistical inference 的算法試圖將生成模型數據 generative model 和能對社團結構進行編碼的網絡數據相匹配。 與其他辦法相比,這種辦法的總體優勢在於其原則性更強,而且有能力從根本上解決具有統計意義的問題。 文獻中的算法大多是基於隨機塊模型 The stochastic block model 以及混合隸屬度、程度校正、層次結構等變量。 模型選擇可以使用一些有原則的算法,例如最小描述長度(或貝葉斯模型選擇)和似然比檢定。 目前有許多算法可以對隨機塊模型進行有效的推理,包括置信傳播和凝聚蒙特卡羅算法。與嘗試給定目標函數對網絡進行聚類的算法不同,這類算法是基於生成模型的。生成模型不僅可以描述網絡的大規模結構,而且可以用來歸納數據和發現網絡中的缺失或虛假鏈路。

基於團結構的社團檢測算法

團就是一個無向圖的完全子圖,團中的每個節點都與團中的其他節點相連。 由於節點之間的聯繫不可能比這更緊密,所以在網絡中產生了很多基於團結構的社團檢測算法,由此還可以分析具有重疊性的社團結構。在這些算法中,一個節點可以同時屬於多個社團,從而形成一個「重疊的社團結構」。


如果一個團不被其他任一團所包含,即它不是其他任一團的真子集,則稱該團為圖的極大團 maximal clique 。基於團的社團檢測算法其中的一種方法就是找到「極大團」 。(其簡單思想是:生成原始圖的所有子圖(可能有2n-1個子圖,n表示節點個數)→判斷這些子圖是不是團→刪除非極大團的其他團)其中, Bron-Kerbosch 算法 The Bron–Kerbosch algorithm 是找到極大團的經典算法之一。 最簡單的方法是只考慮大於最小尺寸(節點數)的極大團。 這些團體的聯合被定義為一個子圖,其組件(斷開的部分)被定義為社團。 這些算法通常在諸如 UCInet 這樣的社交網絡分析軟件 social network analysis software 中實現。


另一種方法是使用固定大小的團體,設大小為k。 這些圖的重疊可以用來定義一類 k- 正則超圖或一種團圖(線圖的一種推廣,此時k=2)。團圖的節點表示原始圖中的團,而團圖的邊則記錄原始圖中團的重疊。將以前的社團檢測算法(將每個節點分配給社團)應用到團圖,然後將每個團圖分配給社團,進而可以使用它來確定派系中節點間的關係。同樣,由於節點可能處於多個小團體中,所以它可以是多個社團的成員。例如,團滲透算法 clique percolation 將社團定義為 k-clique的滲透集群。 為了做到這一點,需找到一個網絡中的所有 k 派系,即所有完整子圖的 k 個節點。然後定義兩個共享 k-1個節點的 k-cliques k -團 為相鄰的 k-cliques,即用於定義團圖中的邊。然後將社團定義為k-clique的最大並集,其中任意 k-clique 可以通過一系列k-clique鄰接,從任意k-clique 到達其他k-clique 。 也就是說,社團只是團圖中的連通組件。 由於一個節點可以同時屬於幾個不同的k-clique滲透簇,故社團之間可以相互重疊。

社團檢測算法的評價標準

如何對算法進行評價以判斷哪些能夠更好地檢測到社團結構仍懸而未決,必須基於對已知結構的網絡的分析。 一個典型的例子是」四組」測試,在這種測試中,一個網絡被分成四個大小相等的組(通常每組32個節點) ,由於組內和組間連接的概率各不相同,導致出現了一些具有挑戰性的社團結構,這為社團檢測製造了一定難度。這樣的基準圖是康德 Condon 和 卡帕 Karp 的種植 l-分區模型 The planted l-partition model 的特例,或者也是「隨機塊模型」 Stochastic block models (一類包含社團結構的隨機網絡模型)更一般的情形。此外,還提出了其他更靈活的基準測試,允許不同的組大小和非平凡度分佈。例如 LFR 基準測試 LFR benchmark ,它是四組基準測試的擴展,包括節點度和社團大小的不同分佈,能夠更加嚴格地評價社團檢測算法。


常用的計算機生成基準測試從定義良好的社團網絡開始。這種結構由於重新布線或刪除鏈接而退化,使得算法越來越難以檢測到原始分區。最後,網絡到達一個隨機點。這種基準可以稱為是「開放的」。這些基準的性能是通過標準化互信息 Normalized mutual information 信息變化 Variation of information 等度量來評估的。 他們將算法得到的解與原來的社團結構進行比較,評估兩個分區的相似性。

可探測性

近年來,在對各種社團的研究中,我們得到一個相當驚人的結果——社團檢測問題存在階段性轉變,這表明隨着社團內部和社團之間連接的密度越來越接近或兩者都變得越來越小(由於社團結構變得太弱或網絡變得太稀疏) ,社團就會突然變得無法檢測。


從某種意義上說,社團本身仍然存在,因為邊的存在和缺失仍然與其節點的社團成員關係密切;但是,從理論上講,如果沒有社團結構,就不可能更好地標記節點,甚至不可能將圖與由Erdos-Renyi模型 Erdos–Renyi model 等空模型生成的圖區分開來。這種轉換與用於檢測社團的算法類型無關,這意味着我們在網絡中檢測社團的能力存在根本的限制,即使我們使用最優的貝葉斯推理(而不考慮我們的計算資源)。


考慮一個具有 n 個節點,q=2 的相同組的隨機塊模型,並且設Putin.pngPutout.png分別是組內和組間的連接概率。


如果Ppppinpout.png,由於社團內部的鏈接密度大於群體之間的鏈接密度,網絡將具有群體結構。


在稀疏情況下,Putin.pngPutout.png都以O n.png為比例,所以平均溫度是恆定的,則有:

Pin n.pngPppinot N.png


然後就不可能在下列情況檢測到這些社團: Cin Cout.png

進一步閱讀


相關鏈接

編者推薦

下是關於集智俱樂部關於社團結構的一些文章

若還想再進一步了解社團結構

本中文詞條由趣木木用戶參與編譯,劉佩佩用戶審校,歡迎在討論頁面留言 本詞條內容源自wikipedia及公開資料,遵守 CC3.0協議。

個人工具
名字空間
動作
導覽
工具箱