基于邊模式的社團檢測算法

摘 要： 為了檢測網絡的社團結構，提出基于統計推理的邊模式社團檢測方法，在計算機生成的網絡中和實際網絡檢測了算法的可行性和準確性，并與現有的兩種基于邊模式的社團檢測方法做了比較。實驗表明，所提出的方法可以快速有效地檢測出重疊社團，在性能上優于后兩種方法。

關鍵詞： 復雜網絡； 社團結構； 邊模式； 網絡檢測

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2013）14?0031?04

Link model based detection algorithm of community structure in complex networks

GAO Hong?yan， QIAN Yu， LIU Fei

（Baoji University of Arts Science， Baoji 721016， China）

Abstract： The link model community detection method based on statistic inference is proposed in the paper to detect community structure of networks. The feasibility and accuracy of the algorithm were tested in both the synthetic networks and actual networks. It was compared with other two available community detection methods based on link model. It turns out that the proposed method can find out the overlapping communities rapidly and its performance is better than that of the previous methods.

Keywords： complex network； community structure； link model； network detection

0 引 言

對復雜網絡結構和功能的研究近年來成了各學科專家探討的熱點問題[1?2]。社團結構是復雜網絡中研究的最核心的問題之一，社團是將復雜網絡的點集按照一定的規則劃分的子集，在子集內部，各點聯系相對緊密，而在各子集之間，點的聯系相對稀疏。社團結構是復雜網絡最重要的特性之一，揭示網絡的社團結構對了解網絡結構和功能非常重要[3]。到目前為止，人們提出了各種揭示社團結構的方法，大致基于譜分的思想，層次聚類法，基于優化的思想?；谧V分的思想主要通過計算特殊矩陣的特征向量來進行社團的劃分[4?5]；層次聚類法又分分裂算法和凝聚算法，最經典的就是GN算法和Newman快速算法。GN算法是通過不斷地從網絡中移除介數最大的邊將網絡逐步細化若干個社團[6]。Newman快速算法按照一定的規則向原始空網中添加邊來實現的[7]?；趦灮乃枷胗蠯ernighan?Lin算法[8]，極值優化算法等等[9]，這些算法主要通過最優化目標函數來實現社團劃分的。當然，還有許多將兩種或以上算法結合起來的變種算法，如結合譜分析的凝聚算法等[10]。這些算法的一個共同特點就是劃分社團時，將網絡中的點進行劃分，它們都屬于基于點模式的社團發現算法，當然，由于點模式社團發現由來已久，所以算法比較成熟。但是研究發現，這些算法只能將節點劃分到一個社團當中，對于那些存在著大量的重疊節點的社團的檢測效果并不理想。而實際當中，這種網絡卻大量存在，比如社會網中，個體由于不同的關系可能屬于不同的社團，如：朋友關系，家庭關系，工作關系等。再如科學合作網，作者根據研究興趣可屬于不同的研究團體。

科學家們也提出了一些發現重疊社團的方法，如派系過濾法[11]，基于模塊度的擴展定義的思想，以及基于優化的思想[12]。這些都是從點的角度來劃分社團。本文另辟蹊蹺，將社團定義為邊的劃分，而非點的劃分。這樣，與點關聯的邊可屬于多個社團，點也就屬于多個社團。

基于邊模式的社團劃分由T.S.Evans首次提出，它通過構造線圖實現社團劃分[13]，后來，Ahn將在基于節點相似的的聚類算法基礎上提出了基于邊相似性的聚類方法[14]。本文在研究前人算法的基礎上，受任偉的簡單概率算法啟發[15]，提出一種新的基于統計推理的邊模式社團發現算法。

1 基于線圖的劃分方法

線圖是圖論中的一個概念，可以為任何一個圖G構造線圖L（G），L（G）的一個節點對應G的一邊， 當G中兩邊相互鄰接時（既有公共頂點），其對應線圖中相應兩節點有邊相連。線圖的制作過程如圖1所示。

圖1 線圖的構造過程

設原圖的鄰接矩陣為A，關聯矩陣為B，線圖的鄰接矩陣為C則三者存在以下關系：

（1）

（2）

式中：為圖A中節點i的度；為沖擊函數，當i=j時，=1，否則=0。由此可知，任何圖都與G都和一線圖L（G）一一對應，而且有以下性質：

（1）若原圖是連通的，線圖也是；

（2），原圖的邊色數等于線圖的點色數。

那么可以通過對線圖邊的劃分實現對原圖點的劃分。而且，由于線圖本質上也是基本圖，所以任何關于圖聚類的算法都可以應用到線圖的社團劃分中去。

文獻[13]將隨機游走思想應用于線圖，提出兩種線圖上的隨機游走過程“邊?邊隨機游走”和“邊?節點?邊隨機游走”，對質量函數Q進行優化，采用基于模塊度優化的算法對線圖進行社團劃分。

2 基于邊相似性的聚類算法

該方法從考慮邊的鄰居信息（即與一條邊有共同節點的邊）出發。如果網絡中兩條邊有共同的鄰居信息或者相近的鄰居信息，則這兩條邊就被認為是相似的，它們同屬一個社團的概率就大一些。

對于無向，無權網絡，節點i的鄰居節點集合用N（i）表示，節點i及鄰居節點集合用，認為鄰居邊（即共享一個節點的邊）比相互獨立的邊相似性更強，所以計算邊相似性時，只考慮哪些鄰居邊。邊和邊的相似性有以下幾種定義方式：

（3）

（4）

（5）

在這三個相似度的表達式中，節點k的信息并沒有出現，這是因為節點k的引進不能帶來任何信息量。得到邊相似矩陣后，采用層次聚類法最其進行社團劃分，層次聚類法又分single?linkage，complete?linkage和average?linkage，single?linkage的類間距離為兩個類中對象間距離的最小值，complete?linkage的兩個類中對象間距離距離的最大值，average?linkage的類間距離為兩個類中對象間距離的平均值。層次聚類的關鍵是如何確定最佳劃分。文獻[14]引入一個類似于節點劃分的模塊的參量—劃分密度D來確定聚類何時結束。對于一個含M條邊，N個節點的網絡，該網絡的一個劃分，所劃分的社團個數為C，子集中的邊數，與這些邊相關聯的節點數，注意有這樣的關系：，則社團C的邊密度：

（6）

而劃分密度為的平均值。

（7）

此處，劃分密度克服的模塊的受精度限制的缺點，它可檢測出任意規模的社團。

3 基于統計推理的邊模式社團發現算法

統計推理指的是根據一組觀察數據和一個假設的模型推導出數據集的特性。如果數據集是網絡圖，假設節點連接情況的模型必須和網絡的真實拓撲結構相符合。

3.1 模型的定義

將網絡中邊的社團劃分想象為圖中的邊涂色問題，同一社團中的邊，給涂上同一種顏色，不同社團的邊，給涂上不同的顏色。所以可以定義這樣的模型，該模型是一個具有N個節點的無向網絡，該網絡的邊假設被圖上了K種顏色，即被劃分給了K個社團，用參數來表征模型中邊的顏色特性，它表示與節點i相連的邊為顏色z的概率。為位于節點i和節點j的z色邊的邊數的均值，而節點i和節點j之間的實際z色邊數服從關于的泊松分布。這意味著網絡可以是多圖——即網絡中一對節點之間可有多條邊。盡管大多數實際網絡只有單邊，但引進多邊可大大降低模型的復雜性，而且由于的值本來就很小，所以引進的誤差也是微乎其微的。隨著模型的建立，邊社團也伴隨而生，對于某個z值，若節點i和節點j有大的，，則連接i，j的邊為z色的概率就大，這些邊就屬于社團z。

3.2 檢測重疊社團

根據定義的模型，直接生成相應的網絡。由于相互獨立且服從泊松分布的隨機變量的和仍服從泊松分布，所以節點i，j之間的邊的所有顏色的均值為，i，j之間邊的實際顏色服從關于的泊松分布，由此生成鄰接矩陣為A的網絡的概率為：

（8）

式中：A為鄰接矩陣；第二部分為包含自環的情況。

這里，根據統計推理的思想，觀察數據就是網絡的拓撲結構，即網絡的鄰接矩陣，假設的模型為第3.1節定義的帶參數的模型，那么現在的任務就是根據觀察數據，假設模型推導出模型的參數，這樣就可以得到網絡中邊的顏色劃分，及社團劃分。為了得到參數，采用數理統計中的最大似然法求解。即求式（8）左邊達到最大值時的參數值。對式（8）進行簡化，重新排列，得到簡化的似然函數如下：

（9）

式（9）很難直接微分求解，這里采用Jensen不等式對其進行簡化：此處，為任意正數集，為概率且滿足當滿足有：

（10）

此處概率只要滿足條件即可。在不等式（10）中，只要選擇合適的值，就能取到等號，假設給定的最佳真值，則的最佳真值由下式給出：

（11）

同樣，給定的最佳真值， 對式（10）進行微分得到的值。

（12）

對式（12）求和，并重新排列，得到下列關系：

（13）

聯合式（12），式（13）得到：

（14）

最大化似然函數現在簡化為同步求解式（11）和式（14），可采用EM算法求解，即給隨機設置一組初始值，將其值代入式（11）得到，再將所得代入式（14）得到的值，這樣來回迭代，在迭代的過程中，似然值單調增加，當似然值達到最大值時所對應的即為假設的模型的最佳真值，為了防止似然值陷入局部最大值，可采取重復計算取最大值的方法。最終得到參數值就是邊（i，j）被涂為z色的概率，它恰恰就是進行社團劃分所需要的參數。進一步，當，則節點i就屬于社團z。

3.3 算法復雜度分析

算法的存儲空間主要取決于存儲系數所需的空間，此算法中有兩個參數和。要求的空間復雜度為，而 要求的存儲空間復雜度為，m，n和K分別為網絡中邊數，節點數，劃分的社團數。因為m通常遠遠大于n，所以存儲空間主要由參數決定為。對于時間復雜度，算法迭代一次為，總運行時間取決于達到最大似然值前的迭代次數。

4 實 驗

在此使用真實的網絡檢測該的算法。

4.1 人工合成網絡

計算機生成的網絡是一個包含n=10 000個節點，被劃分成2個重疊社團的網絡。將x個節點放置在第一個社團當中，y個節點放置在第二個社團中，剩下n-x-y個節點放置在兩個社團當中，并與兩個社團其他節點連接的邊數的均值相等。設置每個節點的度均值為k。

做三組測試：

（1）固定重疊的節點數z=500，x=y=4 750，觀察算法隨k的變化情況。當k趨于10時，網絡中無邊，故無社團結構，當k變大時，可以直接檢測出社團結構；

（2）固定z=500，k=10，改變x和y；

（3）固定k=10，x=y，改變z。

實驗結果顯示，算法在相當一段參數范圍內執行結果良好。算法的準確性隨著K的增加而增加。當k>10時，執行結果與真實網絡幾乎一致，隨著z的增加，x，y比例的失衡，算法的準確性下降。

4.2 Zachary俱樂部網

Zachary俱樂部網是用來檢測算法的基準網絡之一，代表了大學運動俱樂部的關系網，由34個節點組成。圖2 是由本文算法得到的交疊社團劃分圖。由圖可知，劃分的社團結構很明顯，其中節點3，9 ，14， 20， 31為重疊節點，這些重疊節點代表了那些在兩個社團中都有朋友的個體，在爭論中，他們很難決定站在哪一方，故將其劃為重疊節點是合理的。

圖2 Zachary俱樂部網絡

4.3 和其他算法比較

在此做了兩組比較，首先將提出的方法與文中提到的兩種邊模式社團檢測做了比較，發現前兩種方法雖然定義了邊模式社團，但卻用節點社團的傳統方法對社團進行了檢測。其復雜度顯然要大于相對應的傳統方法。提出的方法在效率和復雜性上要略好一些。

其次，將所提算法與簡單概率算法進行比較，發現二者復雜性相同，均采用模型假設和EM算法。二者的主要區別在于SPAEM定義的參數是基于節點的連接性。而本文算法基于邊的連接性。故在檢測重疊節點方面，本文算法要優于SPAEM算法。

5 結 語

在該文中，綜述了現有的基于邊模式的設團檢測算法，并提出了一種新的邊模式社團檢測算法，該算法有嚴格的數學基礎，它是一種基于概率模型的邊社團檢測算法，易于實現，該算法的缺點是必須預知社團的個數，這是后面進一步研究的內容。由于復雜度的限制，它只能檢測中等規模的數據，需要進一步的改進。

參考文獻

[1] STROGATZ S H. Exploring complex networks [J]. Nature， 2001， 410： 268?276.

[2] BOCCALETTI S， LATORA V， MORENO Y， et al. Complex networks： structure and dynamics [J]. Physics Reports， 2006， 424（4/5）： 175?308.

[3] FORTUNATO Santo. Community detection in graphs [J]. Physics Reports， 2010， 486： 75?174.

[4] FIEDLER M. Algebraic connectivity of graphs [J]. Czech. Math. J.， 1973， 23： 298?304.

[5] POTHEN A， SIMON H， LIOU K?P. Partitioning sparse matrices with eigenvectors of graphs [J]. SIAM Journal on Matrix Analysis and Applications， 1990， 11（3）： 430?452.

[6] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [J]. Proc. Natl. Acad. Sci.， 2001， 99： 7821?7826.

[7] NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Phys. Rev. E， 2004， 69： 066133.

[8] KERNIGHAN B W， LIN S. An efficient heuristic procedure for partitioning graphs [J]. Bell System Technical Journal， 1970， 49： 291?307.

[9] DUCH J， ARENAS A. Community detection in complex networks using extreme optimization [EB/OL]. [2005?01?16]. http：//www. arxiv.org/pdf/cond?mat/0501368.

[10] DONETTI L， MU?OZ M A. Detecting network communities： a new systematic and efficient algorithm [EB/OL]. [2008?02?02]. http：//www.arxiv.org/pdf/cond?mat/0404652.

[11] PALLA G， DERéNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature， 2005， 435（7043）： 814?818.

[12] BAUMES J， GOLDBERG M K， KRISHNAMOORTHY M S， et al. Finding communities by clustering a graph into overlapping subgraphs [C]// Proceedings of IADIS AC. [S.l.]： IADIS ， 2005： 97?104.