基于標(biāo)簽傳播算法在重疊社區(qū)發(fā)現(xiàn)中的改進(jìn)

王茜，方旭

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

基于標(biāo)簽傳播算法在重疊社區(qū)發(fā)現(xiàn)中的改進(jìn)

王茜，方旭

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

隨著信息技術(shù)的發(fā)展，復(fù)雜網(wǎng)絡(luò)越來越被廣泛關(guān)注。在真實(shí)網(wǎng)絡(luò)中，重疊社區(qū)發(fā)現(xiàn)也越來越普遍,與算法相比，標(biāo)簽傳播算法簡(jiǎn)單。在原有COPRA算法的基礎(chǔ)上，對(duì)標(biāo)簽初始化和標(biāo)簽選擇進(jìn)行改進(jìn)，提出一種新的重疊社區(qū)發(fā)現(xiàn)算法。實(shí)驗(yàn)表明，該算法挖掘的重疊社區(qū)具有更高的模塊度，能夠更加有效地發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu)。

復(fù)雜網(wǎng)絡(luò)；重疊社區(qū)發(fā)現(xiàn)；標(biāo)簽傳播

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

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

重疊社區(qū)與非重疊社區(qū)比較具有更現(xiàn)實(shí)的意義，首先重疊節(jié)點(diǎn)是必然是社區(qū)中重要的節(jié)點(diǎn)，其次重疊社區(qū)反映了更加真實(shí)的社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)。那么重疊社區(qū)的發(fā)現(xiàn)及其算法研究已經(jīng)成為目前一個(gè)熱點(diǎn)問題。

2 標(biāo)簽傳播算法相關(guān)

2.1 標(biāo)簽傳播思想

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

2.2 LPA算法

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

（1）初始化，為節(jié)點(diǎn)分配標(biāo)簽，x節(jié)點(diǎn)標(biāo)簽為Cx（0）=x；

（2）隨機(jī)排列網(wǎng)絡(luò)中的節(jié)點(diǎn)，排列為X；

（3）對(duì)X中每個(gè)節(jié)點(diǎn)x，根據(jù)公式Cx（t）=f（C（x1）（t-1），…，Cxm（t-1），Cxm+1（t-1））對(duì)x節(jié)點(diǎn)的標(biāo)簽進(jìn)行更新。

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

2.3 COPRA算法

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

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

COPRA算法的流程是：

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

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

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

（4）根據(jù)節(jié)點(diǎn)標(biāo)簽對(duì)社區(qū)進(jìn)行劃分。

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

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

3 改進(jìn)的標(biāo)簽傳播算法

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

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

w（li）代表標(biāo)簽l的所在頂點(diǎn)邊的權(quán)重；b（li，x）代表每一個(gè)標(biāo)簽l的頂點(diǎn)對(duì)標(biāo)簽l的從屬系數(shù)；移d（li）代表標(biāo)簽l的頂點(diǎn)度數(shù)總和。

對(duì)任一頂點(diǎn)x，對(duì)sum（l）進(jìn)行排序，頂點(diǎn)x標(biāo)簽為sum（l）排序中前v個(gè)l的值，然后對(duì)這v個(gè)標(biāo)簽進(jìn)行歸一化處理，最終得到x的標(biāo)簽集合。

改進(jìn)算法完整描述流程圖如圖1所示：

圖1 改進(jìn)算法流程圖

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

數(shù)據(jù)集一是Karate Club Network數(shù)據(jù)集，Karate數(shù)據(jù)集是非官方空手道俱樂部數(shù)據(jù)集。

圖2 Karate網(wǎng)絡(luò)

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

表1 Karate數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

數(shù)據(jù)集二是Dolphin social network，該數(shù)據(jù)集是根據(jù)海豚群體的交流情況而得到的海豚社會(huì)關(guān)系網(wǎng)絡(luò)。這個(gè)網(wǎng)絡(luò)具有62個(gè)節(jié)點(diǎn)，159條邊。節(jié)點(diǎn)表示海豚，邊表示海豚間的接觸關(guān)系。

本實(shí)驗(yàn)設(shè)置d=1，v=2時(shí)，重復(fù)運(yùn)行100次后取平均值得到的結(jié)果，表2為該算法與原算法的模塊度和時(shí)間復(fù)雜度對(duì)比分析，算法的模塊度提高，時(shí)間復(fù)雜度增大。

表2 Dolphin數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

數(shù)據(jù)集三是人工合成數(shù)據(jù)集，選取合成數(shù)據(jù)集為68個(gè)頂點(diǎn)，440條邊，每條邊的權(quán)重為1到10之間的正整數(shù)的數(shù)據(jù)集。數(shù)據(jù)集網(wǎng)絡(luò)圖如圖3所示：

圖3 人工合成網(wǎng)絡(luò)

針對(duì)人工網(wǎng)絡(luò)設(shè)置d=2，v=2時(shí)，重復(fù)運(yùn)行100次后取平均值得到的結(jié)果如表3所示：

表3 人工數(shù)據(jù)集實(shí)驗(yàn)

5 結(jié)語

本文從初始化和標(biāo)簽選擇兩個(gè)階段對(duì)COPRA算法進(jìn)行改進(jìn)。首先針對(duì)度數(shù)小于設(shè)定閾值的節(jié)點(diǎn)進(jìn)行預(yù)處理，以此來提高算法執(zhí)行的效率，最后在多個(gè)標(biāo)簽可選情況下，對(duì)節(jié)點(diǎn)影響度進(jìn)行排序，從而減小算法隨機(jī)性，提高了算法的穩(wěn)定性。本文采用了三個(gè)數(shù)據(jù)集進(jìn)行試驗(yàn)測(cè)試，分別對(duì)參數(shù)d和v進(jìn)行設(shè)定，重復(fù)運(yùn)行算法多次，對(duì)運(yùn)行結(jié)果進(jìn)行分析處理。結(jié)果表明，改進(jìn)的COPRA算法模塊度和穩(wěn)定性有所提高，但是由于算法在預(yù)處理階段和標(biāo)簽排序方面的改進(jìn)，使得算法時(shí)間復(fù)雜度增加，最終算法能夠挖掘出重疊的高質(zhì)量社區(qū)結(jié)構(gòu)。本文與COPRA算法一樣依然采用同步更新策略，為了使算法更加穩(wěn)定，可以考慮綜合兩種傳播方式進(jìn)行改進(jì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]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]．北京:清華大學(xué)出版社，2006，162-191.

[7]PALLA G，DERENYI I，F(xiàn)ARKAS 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ā)現(xiàn)算法[J]．軟件導(dǎo)刊，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，F(xiàn)ANG 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-），女，重慶人，教授，研究方向?yàn)榫W(wǎng)絡(luò)安全、電子商務(wù)、數(shù)據(jù)挖掘

2017-03-14

2017-04-05

方旭（1991-），男，湖北黃岡人，碩士，研究方向?yàn)閿?shù)據(jù)挖掘、社區(qū)發(fā)現(xiàn)