王茜，方旭

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

基于標簽傳播算法在重疊社區(qū)發(fā)現中的改進

王茜，方旭

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

隨著信息技術的發(fā)展，復雜網絡越來越被廣泛關注。在真實網絡中，重疊社區(qū)發(fā)現也越來越普遍,與算法相比，標簽傳播算法簡單。在原有COPRA算法的基礎上，對標簽初始化和標簽選擇進行改進，提出一種新的重疊社區(qū)發(fā)現算法。實驗表明，該算法挖掘的重疊社區(qū)具有更高的模塊度，能夠更加有效地發(fā)現重疊社區(qū)結構。

復雜網絡；重疊社區(qū)發(fā)現；標簽傳播

1 重疊社區(qū)及其發(fā)現算法介紹

隨著信息技術的發(fā)展，大多數網絡都存在社區(qū)結構這一特征?，F有的社區(qū)發(fā)現主要分為非重疊社區(qū)發(fā)現和重疊社區(qū)發(fā)現兩大類，其中非重疊社區(qū)發(fā)現方法發(fā)現的社區(qū)是彼此不重疊的，一個節(jié)點只能屬于一個社區(qū)，而重疊社區(qū)發(fā)現允許一個節(jié)點同屬于多個社區(qū)。

重疊社區(qū)與非重疊社區(qū)比較具有更現實的意義，首先重疊節(jié)點是必然是社區(qū)中重要的節(jié)點，其次重疊社區(qū)反映了更加真實的社會網絡結構。那么重疊社區(qū)的發(fā)現及其算法研究已經成為目前一個熱點問題。

2 標簽傳播算法相關

2.1 標簽傳播思想

標簽傳播算法在2002年最早被提出，先為任一節(jié)點初始化一個標簽，然后根據鄰接點更新自己標簽，如果標簽直接越相似，那么鄰接點的標簽就更易被傳播。

2.2 LPA算法

圖G=（V，E）表示有n個節(jié)點{1，2，…，n}∈V，m條邊{1，2，…，m}∈E的無向無權復雜網絡，標簽傳播算法根據標簽傳播的思想，重復迭代更新到算法結束，最后根據節(jié)點標簽分類。標簽傳播具體流程如下：

（1）初始化，為節(jié)點分配標簽，x節(jié)點標簽為Cx（0）=x；

（2）隨機排列網絡中的節(jié)點，排列為X；

（3）對X中每個節(jié)點x，根據公式Cx（t）=f（C（x1）（t-1），…，Cxm（t-1），Cxm+1（t-1））對x節(jié)點的標簽進行更新。

（4）判斷每個節(jié)點的標簽是否都與其鄰接點中出現次數最多的標簽一致，如果是，則算法停止，否則設置t=t+1，繼續(xù)回到步驟（3）執(zhí)行；

2.3 COPRA算法

LPA算法簡單直觀，易于理解，而且求解準確性很高，無需指定社區(qū)個數等其他任何參數，最主要是算法時間復雜度很低，接近線性。但是LPA算法存在兩個問題：第一，其穩(wěn)定性較差，原因是社區(qū)間標簽易傳播，當一個節(jié)點存在多個可選標簽時，隨機地選擇其中一個，對于不同的隨機選擇會產生不同的社區(qū)發(fā)現結果。第二，在現實生活中，很多節(jié)點可能同時屬于多個標簽，而LPA算法是無法挖掘出重疊社區(qū)結構的，為此引入了多標簽結構c（c，b）。b表示節(jié)點x對社區(qū)c的從屬系數，其中0≤b≤1。通過bt（c，x）表示在第t次迭代節(jié)點x與社區(qū)c之間的從屬系數，具體計算公式為：

其中，N（x）表示節(jié)點x的鄰接點集合。

COPRA算法的流程是：

（1）標簽初始化階段是為任意節(jié)點x分配標簽c（x，1）。

（2）根據鄰接點集合標簽情況更新x節(jié)點標簽，如果有多個，則隨機選取v個。其中參數v為設定的節(jié)點可擁有的最多標簽數目，其中0<|c（x）|≤v。

（3）若每個節(jié)點的標簽都和其鄰接點中出現次數最多的標簽相同或者算法達到設定的最大迭代次數，則算法停止，否則回到步驟（2）繼續(xù)執(zhí)行。

（4）根據節(jié)點標簽對社區(qū)進行劃分。

為了評價社區(qū)劃分情況，我們引入模塊度的概念。模塊度Q的意義是Q的值越趨向1，表示產生的社區(qū)劃分結構模塊化程度越明顯。目前為止，評價社區(qū)發(fā)現算法有很多不同的方法。

Q函數：為了判斷社區(qū)劃分優(yōu)劣，一個想法就是保證社區(qū)內部邊盡可能多。Newman等人在這種思想的基礎上，結合了GN算法提出了Q函數。具體模塊度的計算公式是其中eii的值則是指社區(qū)i內邊總數和網絡中總邊數比。

3 改進的標簽傳播算法

標簽傳播算法首先為網絡中所有的節(jié)點分配一個初始標簽，然后對這些標簽進行迭代更新，如果網絡的節(jié)點很多，那么更新所有這些標簽的時間空間開銷就會增大，考慮到在網絡中有很多節(jié)點的度數較小，它們的更新完全依賴于它們鄰節(jié)點的標簽，可以采用較少初始化標簽的量來節(jié)省開銷和算法的不穩(wěn)定性。我們提出節(jié)點度數d0（d0為自然數）這一閾值，對節(jié)點度數小于d0的節(jié)點，其節(jié)點標簽不予考慮，這樣便大大減少了初始化標簽的數目，也減少了此類節(jié)點的更新量，降低了更新復雜度。至于d0的取值問題，可以結合網絡情況，以及實驗結果得出最佳閾值。

在COPRA算法在選擇階段存在隨機選擇性，這樣就很容易造成標簽傳播算法的不穩(wěn)定性。為了解決這些問題，本文引進標簽綜合影響度的概念，決定標簽綜合影響度的因素有標簽從屬系數，節(jié)點的度之和，邊的權重等。根據影響度的排序依次選擇影響度較大的節(jié)點，減少了算法隨機性。針對標簽這些影響因子，綜合考慮對標簽選擇過程的影響程度大小，提出以下標簽綜合影響度的計算公式。假設節(jié)點x的領節(jié)點中的每一個標簽l，其標簽綜合影響度sum（l）計算公式如下：

w（li）代表標簽l的所在頂點邊的權重；b（li，x）代表每一個標簽l的頂點對標簽l的從屬系數；移d（li）代表標簽l的頂點度數總和。

對任一頂點x，對sum（l）進行排序，頂點x標簽為sum（l）排序中前v個l的值，然后對這v個標簽進行歸一化處理，最終得到x的標簽集合。

改進算法完整描述流程圖如圖1所示：

圖1 改進算法流程圖

4 實驗設計與結果分析

本文實驗的硬件為：Intel Core i5-4590處理器3.3GHz，16G內存，算法運行環(huán)境為64位Windows7和64位Ubuntu 14.0.4 LTS，繪圖工具：Visio、Cytoscape。算法實現語言：Java、C++。

數據集一是Karate Club Network數據集，Karate數據集是非官方空手道俱樂部數據集。

圖2 Karate網絡

表1是本文提出的重疊社區(qū)標簽傳播算法在d= 1，v=2時，由于算法的隨機性，重復運行100次后取平均值得到的結果，將該算法與CMP算法，COPRA算法進行對比，算法的模塊度相比其他算法有所提高，但是由于在標簽過濾和標簽選擇階段對標簽排序，故該算法時間復雜度相對較大。

表1 Karate數據集實驗結果

數據集二是Dolphin social network，該數據集是根據海豚群體的交流情況而得到的海豚社會關系網絡。這個網絡具有62個節(jié)點，159條邊。節(jié)點表示海豚，邊表示海豚間的接觸關系。

本實驗設置d=1，v=2時，重復運行100次后取平均值得到的結果，表2為該算法與原算法的模塊度和時間復雜度對比分析，算法的模塊度提高，時間復雜度增大。

表2 Dolphin數據集實驗結果

數據集三是人工合成數據集，選取合成數據集為68個頂點，440條邊，每條邊的權重為1到10之間的正整數的數據集。數據集網絡圖如圖3所示：

圖3 人工合成網絡

針對人工網絡設置d=2，v=2時，重復運行100次后取平均值得到的結果如表3所示：

表3 人工數據集實驗

5 結語

本文從初始化和標簽選擇兩個階段對COPRA算法進行改進。首先針對度數小于設定閾值的節(jié)點進行預處理，以此來提高算法執(zhí)行的效率，最后在多個標簽可選情況下，對節(jié)點影響度進行排序，從而減小算法隨機性，提高了算法的穩(wěn)定性。本文采用了三個數據集進行試驗測試，分別對參數d和v進行設定，重復運行算法多次，對運行結果進行分析處理。結果表明，改進的COPRA算法模塊度和穩(wěn)定性有所提高，但是由于算法在預處理階段和標簽排序方面的改進，使得算法時間復雜度增加，最終算法能夠挖掘出重疊的高質量社區(qū)結構。本文與COPRA算法一樣依然采用同步更新策略，為了使算法更加穩(wěn)定，可以考慮綜合兩種傳播方式進行改進。

[1]Girvan M，Newman M.E.J.Community Structure in Social and Biological Networks[J].PNAS，99（12），2002.

[2]Weiss R.s，E Jaeobson.Am.Soeiol[J].Rev，20，661，1955.

[3]Wu F，Huberman B A.Find Communities in Linear Time:A Physics Approach[J].Euro.Phys.JB，38:331-338，2003.

[4]Santo Fortunato．Community Detcetion in Graphs[J]．Physics．2010.

[5]Newman M．E．J，Girvan M．Finding and Evaluating Community Structure in Networks[J].Phys Rev E 69，026112，2004.

[6]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M]．北京:清華大學出版社，2006，162-191.

[7]PALLA G，DERENYI I，FARKAS I，et al.Uncovering the Over-Lapping Community Structure of Complex Networks in Nature and Society［J］.Nature，2005，435:814-818.

[8]Xie Jie-rui，Szymanski B．k Community Detection Using a Neighborhood Strength Driven Label Propagation Algorithm[C]．Proc of IEEE Network Science Workshop，：188-195，2011.

[9]沈海燕，李星毅．一種新的重疊社區(qū)發(fā)現算法[J]．軟件導刊，2015，14（4），59-62.

[10]Barber M J，Clark JW.Detecting Network Communities by Propagating Labels Under Constraint[J].Physical Review E，2009，80（2）: 129-139.

[11]Wu Zhihao，Lin Youfang，Gregory S．Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J]．JCST，2012，27（3）:468-479.

[12]Gregory S．Finding Overlapping Communities in Networks by Label Propagation[J]．New JPhysics，2010，12（10）:103-118.

Im provement of Overlapping Comm unity Detection Based on Label Propagation Algorithm

WANG Qian，FANG Xu

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

With the development of information technology,more and more attention has been paid to complex network.In real network,overlapping community detection is common,comparing with other algorithm,LPA is simple.Proposes a new algorithm to detect overlapping commu-nity on the basis of the original COPRA algorithm.Experimental results show that the algorithm has highermodularity,it can discover the overlapping community structure effectively.

Complex Network;Overlapping Community Detection;Label Propagation

1007-1423（2017）12-0006-04

10.3969/j.issn.1007-1423.2017.12.002

王茜（1964-），女，重慶人，教授，研究方向為網絡安全、電子商務、數據挖掘

2017-03-14

2017-04-05

方旭（1991-），男，湖北黃岡人，碩士，研究方向為數據挖掘、社區(qū)發(fā)現