基于貢獻函數的重疊社區劃分算法

劉功申 孟 魁 郭弘毅 蘇 波 李建華

?

基于貢獻函數的重疊社區劃分算法

劉功申 孟 魁*郭弘毅 蘇 波 李建華

(上海交通大學電子信息與電氣工程學院 上海 200240)

現實世界中的網絡結構呈現出重疊社區的特征。在研究經典的標簽算法的基礎上，該文提出基于貢獻函數的重疊社區發現算法。算法將每個節點用三元組(閾值、標簽、從屬系數)集合來表示。節點的閾值是每次迭代過程中標簽淘汰的依據，該值由多元線性方程自動計算而來。從屬系數用于衡量當前節點與標簽所標識社區的相關度，從屬系數的值越大說明該節點與標簽所標識社區的關聯性越強。在每一次迭代的過程中，算法依據貢獻函數計算每個節點的從屬系數，并生成新的三元組集合。然后依據標簽決策規則淘汰標簽，進行從屬系數規范化。通過對真實的復雜網絡和LFR(Lancichinetti Fortunato Radicchi)自動生成的網絡進行測試可知，該算法的社區劃分準確率高，而且劃分結果穩定。

復雜網絡；社區發現；重疊社區

1 引言

經典的社區發現算法假設某個節點僅僅屬于一個特定社區，這種假設顯然和現實不完全相符。在現實世界的復雜網絡系統中，存在一些節點同時屬于不同的社區，這便是所謂的重疊社區結構[1]。針對重疊社區的挖掘問題，Palla等人[2]提出了針對重疊社區的派系過濾(Clique Percolation Method, CPM)算法，該算法將社區視作由一些互相連通的完全子圖構成的集合。將節點數目為的完全子圖定義為-clique，當兩個-clique之間擁有個公共節點時，則認為這兩個-clique是相鄰的。自從Palla提出Clique概念以來，許多研究者便不斷嘗試提出新的基于Clique思想的社區發現算法[3]。

Gregory[4]在GN算法的基礎上提出了能發現重疊社區的CONGA (Cluster-Overlap Newman Girvan Algorithm)算法，其主要思想是將邊介數較高的節點再分裂成多個副本。對于分裂后的節點，采取經典的社區發現算法進行挖掘社區結構。由于某些節點在算法運行過程中分裂成多個副本，這些副本在后續運行過程中可能被劃分到不同的社區，并最終實現一個節點可以同時屬于多個社區的目的。

文獻[5]采用了非負矩陣分解來發現重疊社區結構，采用非負矩陣分解在重疊社區發現任務上具有很好的準確性和良好的解釋性。文獻[6]提出了基于非負矩陣分解的圖規范化方法，在該方法中使用了能反映節點間相似度的度量方法，實驗證明這種方法能提高社區劃分的準確度。文獻[7]提出了一種基于非負矩陣的半監督社區劃分方法，該方法利用了標簽的先驗知識進行訓練，在劃分工程中歸并標簽。

Raghavan等人[8]提出的基于標簽傳播的社區發現算法(Label Propagation Algorithm, LPA)具有非常好的時間復雜度，這促使Gregory[9]將LPA算法從非重疊社區拓展到了重疊社區，提出了基于標簽傳播的重疊社區發現算法。Gregory的算法[9]繼承了傳統標簽的優秀的時間復雜度指標，在不同的網絡數據上具有較好的測試結果。但是，該算法也具有明顯的劣勢：(1)繼承了傳統標簽傳播算法的缺點—隨機性。(2)算法執行時需要事先設置參數，而且的不同取值對算法的結果影響非常大。但如何選擇合適的值是個難題。

本文在分析現有算法的基礎上，提出基于貢獻函數的重疊社區劃分標簽傳播算法(Overlapping- Communities Recognition Algorithm based on Contribution Function, OCRA-CF)。通過引入貢獻函數，克服了Gregory算法的隨機行為，使算法結果更加穩定。同時能夠自動計算各個節點的閾值，避免了Gregory所提算法中值選擇問題。此外，OCRA-CF還具有較好的擴展性及并行計算優勢。

2 算法設計

OCRA-CF算法的創新改進在于：(1)為每個節點自動計算閾值，該閾值反映了某個節點屬于多個社區的可能程度。(2)采用貢獻函數計算從屬系數。貢獻函數反映了鄰居節點的貢獻情況。(3)采用較穩定的規則進行標簽淘汰，最大程度地提高了算法結果的穩定性。

2.1重要函數

在每一次迭代的過程中，算法將決定每一個節點的所有鄰接點的標簽以及該標簽對下一輪的貢獻度。算法的核心由4個因素構成：閾值計算、貢獻函數、從屬系數和選擇規則。在本文中，每個節點擁有獨特的閾值，并且實現了閾值的自動計算。從屬系數都經過規范化處理過程，某個節點的所有從屬系數的值相加為1。同樣地，貢獻函數的取值也經過規范化處理，某個節點的貢獻函數的值相加也是1。最后，根據選擇規則來決策保留那些標簽或者淘汰那些標簽。

2.1.1閾值計算 每個節點的閾值和該節點可能所屬的社區數相關。事實上，節點的閾值就是該節點所屬社區數的倒數。因此，估算社區數是閾值計算的核心任務。但在未執行完該社區劃分算法之前，不可能知道每個節點實際屬于幾個社區，因此，只能采用估算的方法來預測節點可能屬于幾個社區。本文提出了為每個節點估算所屬社區數量的方法，該方法主要包括估算社區度和計算社區數兩個步驟。

(1)估算社區度： 所謂社區度就是衡量節點屬于多個社區的可能程度。社區度是本文為每個節點計算的一個數值，該值越大說明該節點同時屬于多個社區的可能性就越大，反之亦然。

本文把經典網絡的標準劃分結果作為先驗知識，把每個節點的靜態特征數據作為后驗知識，通過多元線性回歸模型擬合出估算社區數的方程。社區數估算函數為

(2)計算社區數： 計算社區數的工作就是根據已知的社區度估算出該節點可能同時屬于的社區數量。根據美國認知科學家George的研究，人類短期記憶一般一次只能記住5~9個事物，也就是常說的“7加減2”原則。近年來對社區網絡的數據統計分析的結論也證實，現實社會中的自然人或者網絡中的虛擬人(即社會網絡節點)盡管有較多的圈子存在，但短期內頻繁交往的圈子數約為個。基于此，本文把每個節點可能屬于社區數的最大值定為9，并按節點的社區度為每個節點賦予區間上的整數值。

2.1.4標簽決策 標簽決策是標簽選擇或淘汰的規則。在算法的每輪迭代中，對于每一個節點，需要按照一定的規則在集合中選擇標簽或淘汰標簽。

2.2參數擬合

2.3 算法流程

算法的整個流程包括4個步驟：計算網絡靜態特征值、計算閾值、節點賦初值和迭代過程。其中，迭代過程是算法的核心部分，同時也是時間復雜度最高的部分。

(1)計算網絡靜態特征值： 網絡靜態特征值是指節點的度(degree)、介數(betweenness)[10]、接近度(closeness)[11]、權威度(authority)[12]等。本文的實驗部分使用這幾個參數完成了算法。作為對本文的擴展，在實際工程中還可以增加其他參數，或者僅僅使用其中的部分參數。

(2)計算節點閾值： 通過式(1)和式(2)，為每個節點估算出社區數，那么，該節點的閾值()就是社區數的倒數。

(3)節點賦初始值： 迭代開始前為每個節點賦值一個標簽，且從屬系數為1。每個節點初始狀態包含如下兩項內容：(只包含一個三元組)和貢獻函數表。

(4)迭代過程： 每一輪迭代主要包括3項任務，即從屬系數計算、標簽決策和終止條件判斷。

3 實驗與分析

3.1 實驗數據

在社區發現算法的研究領域中，有兩種方式對算法進行評價。一種是使用現實世界的網絡數據集對算法進行測試。由于真實網絡結構的復雜性，任何劃分都不具有絕對的正確性，因此，需要通過一些社區評價指標作為評價標準。典型的評價指標包括經典算法所提出的函數和Mod模塊度[13]等。實驗采用了許多具有代表性和研究價值的真實網絡數據集。其中包括著名的空手道俱樂部數據集(Karate_Club，簡稱Karate)、海豚網絡數據集(Dolphin_Social，簡稱Dolphin)、美國大學生職業足球聯盟數據集(American_Football，簡稱Football)、SNS數據集(Social_Community，簡稱S_C)、豆瓣數據集(Douban)、PGP數據集(PGP)、安然郵件系統數據集(Eron_mail，簡稱Eron)等。Z_follow是匿名發布者在北郵人(sns.byr.edu.cn)上的所有Follow節點組成的SNS網絡。Z_Friends是所有Follow的Follow節點形成的SNS網絡。根據數據提供者的說明，Z_Friends網絡的模塊度是0，也就是說，這個社區不存在小的社區結構。Bupt是整個北郵人SNS網絡的所有節點形成的社區。

另一種方式是利用人工構造數據集對算法進行評價。在利用人工構造數據集時，可以通過設定節點數、邊數、每個節點的平均度數、重疊度等控制變量來生成結構固定的網絡。由于生成的網絡結構固定，因此可以有針對性地對算法進行評價。此外，還可以通過改變一到兩個構造社區的參數變量，來針對性地測試算法的對不同網絡的適應性。Lancichinetti等人[14]提出的LFR基準程序是目前公認的構造人工網絡的程序。

3.2式(1)的參數估計

式(1)為典型的多元線性方程，本文采用多元線性回歸模型擬合該方程的參數。參數的估計過程主要包括：數據準備和線性回歸過程。

(1)數據準備： 國內外科研人員對Karate, Football和Dolphins網絡進行了充分研究，給出了公認的劃分結果[15]。本文基于這些公認的劃分結果，每個節點準備一個標準值，并設計了一個算法來計算該值。該算法主要由以下3個部分組成：

(a)節點連接的社區數： 節點和社區的連接定義為：“如果節點和社區中的任意節點有邊相連，則稱節點和社區有連接”。根據標準的社區劃分，能方便地統計每個節點分別和多少社區有連接(記為)。

(c)指向差異： 指向差異是指某個節點和多個社區連接情況的差異度量。對于節點而言，如果該節點和個社區有連接，且分別有條邊連接到社區。當無明顯差異時，更傾向于被當作個社區的橋接點，也就是重疊節點。反之，當差異較大時，更傾向于被劃分到值較大的那個社區，也就是說不是重疊節點。圖1(a)圖和圖1(c)的節點都傾向于作為社區的節點，而圖1(b)的節點更傾向于作為和的橋接點。

圖1 指向差異示意圖

因此，指向差異的計算表示為

最后，綜合上述3部分指標，每個節點的參考值計算公式為

(2)多元線性回歸： Karate, Football和Dolphins網絡標準劃分參見文獻[15]。靜態值的計算方法同2.3節。由于數據太多，表1僅給出了3個網絡的部分參數(分別給出了5個節點的數據)，其他節點的數據略去。根據表1的數據，可以把式(1)的參數確定下來：

(8)

3.3式(4)的參數估計

估算數據時，使用了人工生成網絡作為標準,數據集是由Lancichinetti等人[14]開發的LFR基準程序生成的人工數據集。表2中代表節點數；代表網絡中節點的平均度數；代表節點的最大度數；代表最小的社區規模，代表最大的社區規模；代表構成這個網絡的混合參數。值越大，網絡內部的社區結構將越不明顯。我們生成了4類人工網絡用作參數估計：(1)小網絡小社區；(2)小網絡大社區；(3)大網絡小社區；(4)大網絡大社區。

表1標準網絡的靜態特征值列表(部分)

網絡節點度介數接近度權威度式(4)值 Karate1160.4376352810.5689655170.0714127290.066131548 290.0539366880.4852941180.0534272310.283107528 3100.1436568060.5593220340.0637190652.226199031 460.0119092710.4647887320.0424227370.270443437 530.0006313130.3793103450.015260960.520041765 Dolphin160.0190825960.3465909090.0228330682.750868499 280.2133244360.3719512200.0074762740.650780668 340.0090728120.2824074070.0070642181.187597919 430.0023737970.3080808080.0140965461.850075725 5100.2489795920.0052039120.822860534 Football1120.0324899490.4237918220.0100923242.032694610 2120.0176211130.4130434780.0091323661.626829027 3120.0131224970.4071428570.0110170181.539988579 4120.0230700990.4206642070.0100686271.626829027 5110.0106638690.4028268550.0095893771.753784351

項目小網絡小社區小網絡大社區大網絡小社區大網絡大社區 N1000100050005000 K20202020 maxk50505050 minc10201020 maxc5010050100 mu0.1~0.90.1~0.90.1~0.90.1~0.9

圖2 獨立參數運行情況

3.4真實網絡數據集測試

(1)準確性評價： 對于真實網絡構成的數據集，采用社區結構參數評價算法結果的好壞。本文主要采用適用于重疊社區發現結果的評價函數Mod進行算法結果的評估。

本文算法(OCRA-CF)是在傳統標簽算法的基礎上改進而來，盡管通過貢獻度函數大大降低了算法的不穩定性，但還是保留了一定的標簽算法固有的不穩定性與隨機性。在針對真實數據集測試的過程中，本文在同一個數據集上先后運行了10次算法。其中Mod值和社區數都是平均值。

經與Karate, Dolphin和football數據集公認的劃分結果進行比對，OCRA-CF算法的社區劃分結果基本正確，幾乎沒有節點被錯誤劃分。而對于大規模的網絡數據集，從表3中的Mod一列可以看出OCRA-CF算法的運行結果也較為理想。Douban的數據來自于互聯網，節點之間的關聯度非常低，其社區結構幾乎為0。Z_friends的數據也是沒有節點之間連接的數據，其社區結構是0，符合數據發布者對數據的特征說明。

表3 OCRA-CF算法在不同數據集上的運行情況

(2)橫向比較： 同樣使用上述的測試數據集，我們將OCRA-CF算法與幾個經典算法進行了對照測試，結果展示如表4和表5所示，其中，Gregory為文獻[9]的算法。

在表4中，OCRA-CF, CPM, Gregory和CFinder算法采用Mod作為評價指標，而GN，Newman采用Q函數作為評價指標，LFM采用EQ評價。表中的OUT表示該算法在24 h內無法完成該數據的計算過程。從表4的數據可以看出，本文提出的OCRA-CF算法在各個數據集上表現都非常好。

在表5中，主要進行運行速度的比較，時間參數為s，從表中的結果可以看出，本文提出的OCRA- CF算法在各種數據集上的時間都較為理想。LFM算法在部分數據集上也表現出了異常優越的效果，但也有些數據的效果非常差，非常不穩定。

總之，OCRA-CF的優勢主要有兩點：(1)時間復雜度低。經典算法對于大型的數據集，都無法在實驗允許的時間內(這里設為24 h)得到社區發現結果。(2)社區劃分的模塊度適中。在各種數據集上都能獲得較好的模塊度評價指標。

3.5人工數據集測試

用LFR基準程序所產生的人工網絡擁有可控制的社區結構的，因此可以用來對算法的劃分準確度進行測試。NMI是評價標準的社區結構和算法輸出的劃分結構之間的相似度的定量指標。由于考慮到構造的數據集要有相當的規模才能具有測試的代表性，而GN或者CPM算法處理幾千節點的數據集時要耗費很長時間，因此本文采用算法復雜度相對較低的LFM算法與CFinder算法作為比較對象。

在對比實驗中，使用表2所列的參數生成了4組人工網絡。在結果的展示中，OCRA-CF算法、CFinder和LFM算法都取10次重復實驗的最佳結果進行比較。算法運行結果所得的NMI如圖3所示。各個圖中的縱坐標是NMI值，橫坐標是的值。4個圖的網絡屬性分別為：(a)小網絡/小社區；(b)小網絡/大社區；(c)大網絡/小社區；(d)大網絡/大社區。

表4 不同算法劃分結果的模塊度比較

表5不同算法的速度比較(s)

圖3 針對人工數據集的準確度比較

4 結論

在現實的社會網絡中，社區結構重疊是普遍存在的現象，因此，面向重疊社區的自動發現算法具有重要的研究意義和使用價值。本文提出的基于貢獻函數的重疊社區發現算法，即OCRA-CF算法，既繼承了傳統標簽算法的速度優勢，又能達到較好的劃分效果。通過在各種人工構造數據集和真實數據集上的進行測試，可以看出OCRA-CF運行結果較為理想，達到了可用的目標。在實際工作中，本文算法具還有兩大優勢：(1)由于OCRA-CF是基于經典標簽算法的改進，所以，該算法能比較方便地移植到Hadoop或Spark等并行計算平臺，以適應社交網絡的大數據需求。(2)OCRA-CF算法中使用的貢獻函數具有較強的擴展性，可以通過調整采用的網絡參數多少以及參數對應的權重獲得不同的貢獻函數，適應不同的應用場景。

[1] WANG Xiaofeng, LIU Gongshen, PAN Li,. Uncovering fuzzy communities in networks with structural similarity[J]., 2016, 210(1): 26-33.

[2] PALLA G, DERENVI I, FARKAS I,. Uncovering the overlapping community structure of complex networks in nature and society[J]., 2005, 435(7043): 814-818.

[3] LEE C, REID F, McDAID A,. Detecting highly overlapping community structure by greedy clique expansion [C]. ACM International Conference on Paper Presented at SNA-KDD Workshop, Washington DC, USA, 2010. arXiv: 1002.1827.

[4] GREGORY S. An algorithm to find overlapping community structure in networks[J]. LNCS, 2007, 4702(12): 91-102.

[5] SHI Xiaohua. Community detection in social network with pair wisely constrained symmetric non-negative matrix factorization[C]. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France, 2015: 541-546.

[6] LIU Xiao, WEI Yiming, WANG Jian,. Community detection enhancement using no-negative matrix factorization with graph regularization[J]., 2016, 30(20): 1650130.

[7] WANG Zhaoxian, WANG Wenjun, XUE Guixiang,. Semi-supervised community detection framework based on non-negative factorization using individual labels[C], The Sixth International Conference on Swarm Intelligence, Beijing, China, 2015, 349-359

[8] RAGHAVAN U N, ALBERT R, and KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J].&, 2007, 76(3 Pt 2): 036106.

[9] GREGORY S. Finding overlapping communities in networks by label propagation[J]., 2009, 12(10): 2011-2024.

[10] ULRIK B. A faster algorithm for betweenness centrality[J]., 2001, 25(2): 163-177.

[11] EPPSTEIN D and WANG J. Fast approximation of gentrality[J]., 2004, 8(1): 39-45.

[12] KLEINBERG J M. Authoritative sources in a hyperlinked environment[J].(), 1999, 46(5): 604-632.

[13] NICOSIA V, MANGIONI G, CARCHIOLO V,. Extending the definition of modularity to directed graphs with overlapping communities[J].&, 2009, 2009(3): 3166-3168.

[14] LANCICHINETTI A, FORTUNATO S, and RADICCHI F. Benchmark graphs for testing community detection algorithms[J].&, 2008, 78(2): 046110.

[15] CAO Xiaochun, WANG Xiao, JIN Di,. Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization[J]., 2013, 03: 2993. doi: 10.1038/srep02993.

Overlapping-communities Recognition Algorithm Based on Contribution Function

LIU Gongshen MENG Kui GUO Hongyi SU Bo LI Jianhua

(,,200240,)

Overlapping is one of the most important characteristics of real-world networks. Based on the classic labeling algorithm, the overlapping-community orientated label propagation algorithm based on contribution function is proposed. In this algorithm, each node is indicated by a set of triples (threshold, label, and coefficient). The threshold value of every node is used as a metric for labels decision, which is calculated automatically by multiple linear regression equation. The dependent coefficient is used to measure the relevance of the current node with the correspondent community which is marked by the label. A greater value of dependent coefficient means a stronger association between the node and the community. During each iteration process, the dependent coefficients are calculated through Contribution Function (CF) of each node, and new triples are produced. Then the labels in terms of decision rules are selected, and the dependent coefficients of the node are normalized. According to the tests with real-world networks and automatic generation of LFR (Lancichinetti Fortunato Radicchi) test network, the algorithm can divide communication with high accuracy and robust result.

Complex networks; Communities detecting; Overlapping communities

TP309

A

1009-5896(2017)08-1964-08

10.11999/JEIT161109

2016-10-18；

改回日期：2017-04-24；

2017-05-26

孟魁 mengkui@sjtu.edu.cn

國家973關鍵技術研究項目(2013CB329603)，國家自然科學基金(61472248)

The National 973 Key Basic Research Program of China (2013CB329603), The National Natural Science Foundation of China (61472248)

劉功申： 男，1974年生，副教授，研究方向為內容安全、自然語言理解.

孟 魁： 女，1973年生，高級工程師，研究方向為移動安全、數據安全和社會網絡.

郭弘毅： 男，1992年生，碩士生，研究方向為推薦系統研究.

蘇 波： 男，1971年生，副研究員，研究方向為社會網絡分析.

李建華： 男，1965年生，教授、博士生導師，研究方向為電子與通信工程、信息安全.