基于LFM算法的改進社區發現算法

肖永嘉，朱征宇

（重慶大學計算機學院，重慶 400000）

基于LFM算法的改進社區發現算法

肖永嘉，朱征宇

（重慶大學計算機學院，重慶 400000）

由于能夠反映網絡內部結構，重疊社區劃分在各領域有著越來越重要的作用。LFM算法是其中較為流行的一種社區劃分方法。但其存在一些缺點，例如在網絡變得龐大和復雜的時候，時間消耗會變得巨大。為了解決這一問題，提出核心區域的概念，并藉此對LMF算法進行改進。最后通過實驗驗證，發現該算法能夠減小時間消耗，同時能夠得到更為可靠的社區劃分。

重疊社區劃分；LFM；核心區域

0 引言

現實世界的很多復雜的相互作用的系統往往被抽象成網絡來表示，用來讓人們更好地理解復雜系統的全部特性，更好地應對現實的變化。例如互聯網環境下的社交網絡、電子商務；流行病傳播學中的疾病預防控制過程，生物學網絡中蛋白質組織構造等。隨著人們對復雜網絡的研究日益深入，社區結構作為復雜網絡存在的普遍特征，由于能有效地揭示網絡系統中群體的共性規律，是解決復雜系統的基礎，又能推進相關應用的發展，已經成為網絡研究的一個重要分支。而重疊社區的發現可以更為準確地理解網絡內部的拓撲結構信息，在近些年的研究中得到了越來越多的關注。

1 相關工作

社區并沒有一個嚴格意義上的定義，較為廣泛接受的是Newman和Gievan提出的“同一社區內的點與點之間的鏈接更緊密，不同社區之間的點的鏈接更稀疏[1，2]。”重疊社區即與其他社區擁有重疊節點的社區。如圖1中G1，G2擁有重疊的節點A1，A2因此G1，G2都是重疊社區。

基于局部優化的社區發現方法可以分為四類：局部拓展優化方法，從給定的初始節點逐步合并引起最大的社區度量增量的近鄰節點，從而進行局部擴展優化，各方法的主要差異在于對局部社區的度量不同。例如子圖度量優化的局部社區擴展算法LWP[3]，L-殼擴展的社區發現算法，LMD算法[4]，LFM算法[5]等；派系過濾方法CPM[6，12]其定義了一種嚴格的社區結構，并允許社區間存在重疊。為進一步分析網絡社區的重疊特性基于子圖強度將CPM算法擴展到加權網絡，提出了一種加權派系過濾算法CPMw[7]，為了進一步有效應用到大規模的加權和非加權社交網絡提出了一種快速派系過濾算法SCP標簽傳播法（LPA）[8]基于單個標簽傳播，網絡中的每個節點被確定地劃分至單一社區中，忽略了社區結構的重疊特性，為此拓展出多標簽傳播算法copra[9]；以及局部邊聚類優化方法，菲利波·拉迪奇（Filippo Radicchi）等人定義了一種邊聚類系數，并提出了一種社區發現的局部方法[10]，Ahn等人提出了一種基于連邊局部相似性的邊社區發現方法來檢測社區的重疊性和層次性[11]，潘磊等人提出另一種局部的邊社區發現方法等。

本文的主要工作是針對LFM算法在時間復雜度上的明顯不足進行改進，得到了較原算法在時間，評價效果都更為出色的改進算法。

圖1

2 算法介紹

2.1 相關定義

網絡可以通過抽象成圖G=（V，E）來表示，其中V= {v1，v2，v3，…}表示節點的集合，E={e1，e2，e3，…}表示邊的集合。

LFM算法中的適應度fG的定義如下：

其中kGin和kGout分別指的是圖G中內部和外部度數的總和，∝是一個正實數參數用來控制社區的規模。較大的∝值會產生較小的社區，較小的∝值會導致社區較大。此外原算法的作者對∝的取值進行了分析：在多數情況下當∝<0.5時整個網絡被劃分為一個社區，當∝>2時，每個節點都是一個單獨的社區。同時對本文實驗包含的三個測試集上時的實驗表明：∝取值為0.9時效果最好。

適應度函數的定義如下：

其中G+{A}表示G中包含A的子圖，G-{A}則表示G中不包含A的子圖。如果fGA>0則表明將節點A加入社區G有益于提高社區質量，則將節點A加入社區G。

2.2 LFM算法的思想

首先引入包含頂點A的自然社區的獲取過程：

假設已有一個包含節點A的子圖G，

①對G的所有鄰接點循環操作，計算每個鄰接點對G的適應度函數值；

②將適應度值最大的點加入子圖G形成更大的子圖G'；

③重新計算子圖G'中的所有點的適應度值；

④如果其中一個節點的適應度值變為負數，則將該節點從子圖G'中剔除，形成新的子圖G"；

⑤如果發生④，則從③開始重復，否則，以子圖G"從①開始重復，直到第①步中所有鄰接點對子圖G的適應度值都為負數時結束。

對于LFM算法的執行過程就可以概括為以下幾步：

①隨機選取一個節點A；

②探測獲取包含節點A的自然社區；

③隨機選取一個為被劃分至任意社區的節點B；

④探測獲取包含節點B的自然社區，不管其臨節點是否屬于其他社區；

⑤從③開始重復，直至所有的節點都被至少分配在一個社區。

算法存在的問題有：

①在獲取自然社區時會有節點反復加入社區然后被剔除的死循環現象；

②在獲取自然社區時每加入一個新的節點都要重新計算一下社區內所有節點針對該社區的適應度值，導致計算量巨大。

針對上述兩條缺點，我們采取如下措施：

①在自然社區發現過程中，對現有社區G的所有鄰接點進行區別標記，如果某個鄰接點曾被加入臨時社區則在自然社區的獲取過程中不再將其加入臨時社區。

②引入核心區域的概念，并規定在獲取自然社區的過程中，如果節點A屬于現有社區的核心區域則則認為該節點將確定屬于現有社區，不再計算其適應度值。

這樣就解決了原算法中出現的問題，極大地提高了算法速度和劃分社區的質量。

2.3 改進算法思想

我們定義：如果某一個節點A在只跟當前社區G內的節點有邊相連，則該節點屬于當前社區的核心區域。如上圖2所示。

根據適應度值的定義：

我們可以得到表達式：

因此我們給出結論如果節點A屬于臨時社區G的核心區域，則將節點A加入社區G有益于社區劃分質量的提高。

圖2

此外，我們對臨時社區的所有鄰接點增加一個標記位，用來表示該鄰接點是否被訪問過即計算過其對社區G的適應度值，在拓展過程中，如果鄰接點中出現了已被訪問過的節點，則說明該節點在臨時社區G’重新計算適應度值的過程中不再有益于提高社區劃分質量，我們認為該節點將永遠不利于提高社區劃分質量。因此我們在新形成的社區G”的拓展過程中將跳過該節點，不再重復計算其對社區的適應度值。

改進后的包含節點A的自然社區獲取過程如下：

假設已有一個包含節點A的子圖G，

①對G的所有鄰接點進行判斷，如果屬于當前社區的核心區域，則對其標記并直接加入當前社區，如果不是進入②；

②對G的非核心區域且未訪問過的鄰接點循環操作，計算每個鄰接點對G的適應度函數值；

③將適應度值最大的點加入子圖G形成子圖G'，并將其標記為已訪問;

④重新計算子圖G'中的所有非核心區域的點的適應度值；

⑤如果其中一個節點的適應度值變為負數，則將該節點從子圖G'中剔除，并將其標記為已訪問過，形成新的子圖G"；

⑥如果發生⑤，則從②開始重復，否則，以子圖G"從①開始重復。

直到所有鄰接點對子圖G的適應度值都為負數時結束。

3 實驗

本章通過實驗驗證我們提出的改進算法的性能，我們將其與LFM原算法以及其他幾種較有代表性的算法進行比較，分別是CPM，COPRA。其中為了使這兩個算法效果最佳，在CPM算法中我們選取k取值為3，COPRA算法中v的取值為3。而在LFM算法及我們的改進算法中，我們參考LFM作者的分析取效果最佳的0.9。

3.1 實驗環境

處理器Intel core i5-5200U 2.20GHz，內存4G，硬盤500G，系統為Windows7 x64，編程語言為Java，開發環境為Eclipse4.4。

3.2 實驗數據

實驗數據包括真實網絡數據集和人工合成網絡數據集兩大類。

五組真實網絡數據集的參數如下，其中karate網絡為W.W.Zachary描述的20世紀70年代一所美國大學的空手道俱樂部中34名成員之間的友誼關系圖，dolphin網絡為David Lusseau描述的新西蘭神奇峽灣一個擁有62只海豚族群的關系網絡，American football網絡為Girvan等人描述的2000年秋季常規賽IA級別的115只球隊比賽的關系網絡，email網絡為具有1133個節點和5451條邊的網絡，blogs網絡為Adamic和Glance在2005年記錄的關于美國政治的3982個博客之間超鏈接的有向網絡。

表1 真實網絡數據集

人工合成網絡數據集的生成我們采用LFR（Lancichinetti-Fortunato-Radicchi）基準程序來構造人工網絡。根據Santo Fortunat在個人網站上提供的源程序，運行時的需要按如下格式輸入參數：benchmark-N-kmaxk-maxc-on-mu-om。

其中N表示節點數目，k表示網絡中節點的平均度；kmax表示節點的最大度；minc表示最小社區包含的節點的個數；maxc表示最大社區包含的節點的個數；on表示重疊節點的個數，om表示每個重疊節點屬于幾個社區；mu表示用來表示社區的混亂程度，mu越大社區發現的難度越大。

3.3 評價指標Qov和NM I

對于真實網絡，我們使用模塊度Qov對社區的劃分質量進行判斷，模塊度的提出基于一個簡單地理念：如果一個子圖是社區那么它的內部節點之間的連邊數一定比隨機生成的自圖的內部節點的連變數多。模塊度的相關概念可以參考文章，這里只給出公式。

對于由LFR基準程序生成的人工合成網絡，在生成網絡的同時程序會給出參考社區劃分，因此我們用標準化互信息度NMI（Normalized Mutual Information）來評價各種算法得到的社區劃分與已知社區劃分的相似程度。如果NMI=1則表示算法得到的結果與已知的社區劃分完全一致。

3.4 人工合成網絡上的時間對比

為了驗證我們的改進算法與原算法在時間上的改進，我們使用LFR基準程序生成兩組人工合成網絡節點數目分別從1000-10000，10000-100000.為了降低整個實驗過程的總耗時，我們將mu置為0.1。

其他參數取值分別為k=10，maxk=50，minc=10，maxc=50，on=100，om=0.1。

圖3

可以看到我們的改進算法在網絡規模相對較小（節點數<10000）時與原算法相比具有顯著提升，隨著網絡節點數目的增加我們的算法與原算法在時間消耗上的差距相對變小，主要原因是網絡規模的劇增導致社區的鄰接點數目劇增。導致在標記鄰接點和判斷是否為核心區域時消耗大量的時間。

3.5 現實網絡效果Qov對比

可以看到我們的改進算法在Karate，football，email三個網絡中效果優于原算法，在dolphins網絡中持平，在blogs網絡中效果比原算法差；與CPM算法相比我們的改進算法在Karate，football和blogs網絡中效果較好，在dolphins和email網絡中效果較差；與Copra算法相比，我們的改進算法在karate，email和blogs網絡中效果較好，在dolphins和football網絡中效果較差。

表2

3.6 人工合成網絡效果對比

為了比較各算法在不同類型網絡下的社區發現質量，我們根據網絡規模N及每個重疊節點所屬的社區個數om的不同，生成了四組由大小網絡和大小社區組合而成具有不同特征的人工網絡。為了降低計算復雜度，我們將影響社區復雜程度的參數mu固定為0.1。其他參數如下圖所示。

得到的各組數據分別如下所示：

表3

我們可以看到在網絡規模較小的情況下（第1，2組數據），我們的改進算法的社區劃分質量高于其他三種算法；在網絡規模較大，同時社區規模較大的情況下的情況下（第3組數據）我們的改進算法的社區劃分質量也高于其他三種算法；只有在網絡規模較大且社區規模較小的情況下，我們的改進算法的社區劃分質量遜色于CPM算法，但仍然高于原算法和COPRA算法。

4 結語

本文針對LFM算法的不足提出了相對應的改進方案，結果表明在時間和社區劃分質量上相較于原算法都有了顯著地提升。但是無論原算法還是我們的改進算法都存在社區劃分不穩定的缺點，如何提高其穩定性有待進一步的工作。

[1]M.E.J.Newman And M.Girvan.Finding and Evaluating Community Structure In Networks.Physical Review E，69:026113，2004.

[2]V.Nicosia，G.Mangioni，V.Carchiolo and M.Malgeri.Extending the Definition Of Modularity To Directed Graphs With Overlapping Communities，Arxiv:0801.1647v4[Physics.Data-an]24 Mar 2009

[3]Luo F，Wang JZ，Promislow E.Exploring Local Community Structures In Large Networks.Web Intelligence and Agent System，2008，6（4）:387-400.

[4]Chen Q，Wu T T，Fang M.Detecting Local Community Structures In Complex Networks Based on Local Degree Central Nodes.Physica A-statistical Mechanics And Its Applications,2013,392(3):529-37.

[5]Lancichinetti A,Fortunato S,KertéSz J.Detecting The Overlapping and Hierarchical Ommunity Structure in Complex Networks.New Journal of Physics,2009,11（3）：033015.

[6]Palla G,Derenyi I,Farkas IEt Al.Uncovering the Overlapping Community Structure of Complex Networks in Nature And Society. Nature,2005,435（7043）：814-8.

[7]Farkas I,Bel D,Palla G Et A l.Weighted Network Modules.New Journal Of Physics,2007,9（6）：180.

[8]Raghavan U N,Albert R,Kumara S.Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks.Physical Review E,Statistical,Nonlinear,and SoftMatter Physics,2007,76（3 Pt2）：036106.

[9]Gregory S.Finding Overlapping Communities In Networks By Label Propagation.New Journal of Physics,2010,12（10）：103018.

[10]Radicchi F,Castellano C,Cecconi F Et Al.Defining and Identifying Communities in Networks.Proceedings of the National Academy of Sciences of the United States of America,2004,101（9）：2658-2663.

[11]Symeon Papadopoulos As,Athena Vakali,Yiannis Kompatsiaris Et Al.Bridge Bounding:a Local Approach for Efficient Community Discovery In Complex Networks.Physics And Society,2009.

[12]DeréNyi I,Palla G,Vicsek T.Clique Percolation In Random Networks.Physical Review Letters,2005,94（16）：160202.

Im proved Algorithm of Overlapping Community Detection Based on LFM

XIAO Yong-jia，ZHU Zheng-yu

（College of Computer Science,Chongqing University，Chongqing 400000）

Overlapping community detection has becomemore and more important since it can reveals the inner structure of networks.LFM algorithm is one of themost popular way to detect communities in complex networks,however the algorithm itself has some weaknesses,such as large time consumption when the network become large and complex.To overcome these problems,based on LFM,presents an improved LFM algorithm(M-LFM)which proposes a definition of core area and apply it into the process of community detection with LFM. Experiments on real networks and artificial networks show that the improved algorithm can decrease time consumption and get better result than LFM.

肖永嘉（1991-），男，山東臨沂人，研究方向為復雜網絡中重疊社區發現算法研究

2017-03-15

2017-05-10

1007-1423（2017）14-0021-06

10.3969/j.issn.1007-1423.2017.14.004

朱征宇（1959-），男，安徽馬鞍山人，博士生導師，研究生方向為數據挖掘技術、互聯網技術與檢索方法、電子商務網站與應用、軟件工程方法與應用、智能交通

Overlapping Community Detection;LFM;Core Area