復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)及社區(qū)間的結(jié)構(gòu)洞識別

劉世超,朱福喜,馮 曦

(武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢 430072)

?

復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)及社區(qū)間的結(jié)構(gòu)洞識別

劉世超,朱福喜,馮 曦

(武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢 430072)

大數(shù)據(jù)環(huán)境下如何有效地、準(zhǔn)確地識別復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)是近年來學(xué)者關(guān)注的重點(diǎn).本文提出一種基于多標(biāo)簽傳播方式MLPS(Multiple Label Propagation Strategy)的重疊社區(qū)識別算法，該算法首先利用影響力最大化模型選取初始種子集合并賦予它們唯一的標(biāo)簽，然后采用結(jié)點(diǎn)間的相似性和影響傳播特性共同作用于標(biāo)簽的傳播迭代過程，迭代停止后將具有相同標(biāo)簽的結(jié)點(diǎn)劃分為同一社區(qū).通過合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)驗(yàn)證了MLPS算法具有較高的準(zhǔn)確度和模塊度，且具有接近線性的時間復(fù)雜度.另外，在對MLPS算法輸出的重疊結(jié)構(gòu)進(jìn)行分析的基礎(chǔ)上，本文提出社區(qū)間的結(jié)構(gòu)洞識別算法SHCDA(Structural Holes Between Communities Detection Algorithm)，該算法通過分析重疊結(jié)構(gòu)和重疊結(jié)點(diǎn)的位置特征，計(jì)算重疊結(jié)點(diǎn)作為結(jié)構(gòu)洞的得分，最后輸出top-k結(jié)構(gòu)洞.本文在不同特性的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果證明了SHCDA算法具有最好的準(zhǔn)確度.

復(fù)雜網(wǎng)絡(luò)；重疊社區(qū)；多標(biāo)簽傳播；結(jié)構(gòu)洞識別

1 引言

現(xiàn)實(shí)世界的許多網(wǎng)絡(luò)普遍體現(xiàn)了社區(qū)結(jié)構(gòu)特性，即同一社區(qū)內(nèi)的結(jié)點(diǎn)關(guān)系緊密，而不同社區(qū)間的結(jié)點(diǎn)關(guān)系稀疏[1].近年來針對社區(qū)發(fā)現(xiàn)的算法層出不窮，在社區(qū)的層次性和重疊性等方面開展了大量的研究[2～4].本文著重研究社區(qū)的重疊性，尤其是大數(shù)據(jù)環(huán)境下，如何有效地解決重疊社區(qū)挖掘的問題.社區(qū)重疊結(jié)點(diǎn)是社區(qū)間的橋梁即社區(qū)間的結(jié)構(gòu)洞，社區(qū)間的結(jié)構(gòu)洞是兩個或多個社區(qū)之間的非重復(fù)關(guān)系，占據(jù)結(jié)構(gòu)洞的個體擁有更多的機(jī)會獲取信息或資源[5].識別社區(qū)間結(jié)構(gòu)洞的關(guān)鍵在于準(zhǔn)確地挖掘網(wǎng)絡(luò)的重疊結(jié)構(gòu)，從而找出結(jié)構(gòu)洞的候選集合，即社區(qū)重疊結(jié)點(diǎn)的集合.

一些學(xué)者針對結(jié)構(gòu)洞的形成和作用進(jìn)行建模研究[6,7]，而對結(jié)構(gòu)洞的識別算法還比較少.文獻(xiàn)[8]采用拓?fù)鋭莸姆绞阶R別重疊社區(qū)和社區(qū)間的結(jié)構(gòu)洞，但作者直接將重疊結(jié)點(diǎn)作為結(jié)構(gòu)洞，沒有定量地分析結(jié)構(gòu)洞的重要性.在實(shí)際情況中，我們往往更加關(guān)心那些比較重要的結(jié)構(gòu)洞，于是Tang J等[9]提出top-k結(jié)構(gòu)洞挖掘的問題，作者認(rèn)為結(jié)構(gòu)洞的鄰居結(jié)點(diǎn)在一定程度上反映該結(jié)構(gòu)洞的重要性，但忽略了對重疊結(jié)構(gòu)的分析.如圖1(a)中的結(jié)構(gòu)洞A與圖1(b)的結(jié)構(gòu)洞C擁有相同的結(jié)構(gòu)，而圖1(b)中的兩個社區(qū)只存在一個結(jié)構(gòu)洞C，定量計(jì)算時C的重要性應(yīng)大于A.

本文的主要貢獻(xiàn)：提出一種基于多標(biāo)簽傳播方式(MLPS)的重疊社區(qū)挖掘算法，算法的輸出結(jié)果擁有較高的準(zhǔn)確度和模塊度；分析社區(qū)重疊結(jié)構(gòu)，提出社區(qū)間的結(jié)構(gòu)洞識別算法(SHCDA)，能有效地挖掘top-k結(jié)構(gòu)洞.

2 標(biāo)簽傳播的相關(guān)工作

Raghavan等[10]提出的標(biāo)簽傳播算法LPA(Label Propagation Algorithm)，首次將標(biāo)簽傳播應(yīng)用于社區(qū)發(fā)現(xiàn)，具有接近線性的時間復(fù)雜度.Barber等人[11,12]將標(biāo)簽傳播算法轉(zhuǎn)化為優(yōu)化問題，Xie J[13]結(jié)合了路徑衰減的思想擴(kuò)展了對結(jié)點(diǎn)鄰居的計(jì)算，提高了社區(qū)劃分結(jié)果的精度.COPRA(Community Overlap Propagation Algorithm)算法[14]是LPA算法的擴(kuò)展，可以解決重疊社區(qū)挖掘的問題.初始化時每個結(jié)點(diǎn)被賦予一組標(biāo)簽對(c,b)，c是標(biāo)簽，b是結(jié)點(diǎn)擁有標(biāo)簽c的概率；在標(biāo)簽更新過程中設(shè)置閾值v，刪除b小于v的標(biāo)簽對.文獻(xiàn)[15]指出COPRA算法的閾值應(yīng)根據(jù)結(jié)點(diǎn)所處的位置不同而變化，并通過平衡閾值的選擇來提高生成社區(qū)的質(zhì)量.SLPA(Speaker-listener Label Propagation Algorithm)[16]通過模擬人類交流的行為特性，定義了動態(tài)的交互規(guī)則來指導(dǎo)結(jié)點(diǎn)的標(biāo)簽更新.文獻(xiàn)[17]提出了MLPA(Multi-label Propagation Algorithm)算法，該算法根據(jù)結(jié)點(diǎn)間的相似性來確定傳播概率，具有較高的準(zhǔn)確度，但是同COPRA算法一樣，算法容易產(chǎn)生大量的社區(qū)，導(dǎo)致模塊度較低.

3 多標(biāo)簽傳播方式的重疊社區(qū)識別算法

3.1 算法主要思想

COPRA是經(jīng)典的標(biāo)簽傳播算法，在該算法的標(biāo)簽傳播過程中，結(jié)點(diǎn)直接接受鄰居結(jié)點(diǎn)的標(biāo)簽，本文定義這種標(biāo)簽傳播的方式為DA(Directly Accept)，即

Pij=bi

(1)

其中,Pij表示標(biāo)簽ci從結(jié)點(diǎn)i傳播到鄰居結(jié)點(diǎn)j的概率，bi是結(jié)點(diǎn)i擁有標(biāo)簽ci的概率.這種直接接受標(biāo)簽的方式并不能真實(shí)地反應(yīng)社會網(wǎng)絡(luò)中信息和資源的傳播，可能會降低算法的準(zhǔn)確度.

MLPA算法假定兩個結(jié)點(diǎn)擁有越多的共同鄰居，標(biāo)簽在結(jié)點(diǎn)間傳播的概率就越大，定義這種標(biāo)簽傳播的方式為SS(Structural Similarity)，即

(2)

(3)

其中,Sij表示結(jié)點(diǎn)i和j的相似性，Γ(i)是結(jié)點(diǎn)i的鄰居結(jié)點(diǎn)集合.在相關(guān)工作中[17]已經(jīng)提到，MLPA算法同COPRA算法一樣，容易產(chǎn)生大量的社區(qū)，導(dǎo)致輸出結(jié)果的模塊度較低.因此，如何在保證準(zhǔn)確度的情況下提高算法的模塊度和穩(wěn)定性，是本文研究的重點(diǎn).

分析現(xiàn)實(shí)的網(wǎng)絡(luò)，結(jié)點(diǎn)影響(標(biāo)簽)的傳播在一定程度上取決于結(jié)點(diǎn)所處的位置，具有較高影響力的結(jié)點(diǎn)往往處于社區(qū)的核心位置，能夠影響周圍影響力較低的結(jié)點(diǎn)[18].于是，本文定義了一種新的基于影響傳播的標(biāo)簽傳播方式ID(Influence Diffusion)，即

(4)

(5)

其中,lij為標(biāo)簽從結(jié)點(diǎn)i傳播到j(luò)的度量，φi表示結(jié)點(diǎn)i在其鄰域結(jié)構(gòu)的相對影響能力，即

(6)其中,Nbi為結(jié)點(diǎn)i及其鄰居結(jié)點(diǎn)的集合；Infi是結(jié)點(diǎn)i的影響力值，可用LeaderRank算法[19]計(jì)算獲得；Z是平滑因子，取結(jié)點(diǎn)鄰域結(jié)構(gòu)的影響力均值，其計(jì)算公式為：

(7)

由式(6)可知結(jié)點(diǎn)i的相對影響能力φi取值區(qū)間為(0,1]，且φi值越大，結(jié)點(diǎn)i的標(biāo)簽傳播能力越強(qiáng).結(jié)合式(5)和式(6)可得標(biāo)簽從結(jié)點(diǎn)i傳播到j(luò)的度量lij取值區(qū)間為(0,1)，且φi與φj的差值越大，標(biāo)簽越容易傳播.由于大部分網(wǎng)絡(luò)結(jié)點(diǎn)的相對影響力有明顯的差異，導(dǎo)致標(biāo)簽在網(wǎng)絡(luò)中不均衡地流動，降低了原有算法的隨機(jī)性，使得算法能夠很快收斂且輸出的結(jié)果較為穩(wěn)定.

于是本文提出一種基于多標(biāo)簽傳播方式(MLPS)的重疊社區(qū)識別算法，綜合SS和ID兩種方式進(jìn)行標(biāo)簽傳播，那么結(jié)點(diǎn)i的標(biāo)簽傳播到鄰居結(jié)點(diǎn)j的概率Pij表示為：

(8)

目前的標(biāo)簽傳播算法對網(wǎng)絡(luò)進(jìn)行初始化時，為每個結(jié)點(diǎn)都賦予一個獨(dú)立的標(biāo)簽，這會導(dǎo)致輸出結(jié)果出現(xiàn)大量孤立的小社區(qū)，從而降低輸出社區(qū)的質(zhì)量.為此，本文采用文獻(xiàn)[20]提出的影響力最大化模型，選取網(wǎng)絡(luò)中一組初始傳播結(jié)點(diǎn)，使得這些結(jié)點(diǎn)能輻射到網(wǎng)絡(luò)大部分結(jié)點(diǎn)，且盡可能的散落在每一個可能的社區(qū)，可以減少在傳播時不需要的判斷開銷.

3.2 重疊社區(qū)發(fā)現(xiàn)的MLPS算法

為了提升算法運(yùn)行的準(zhǔn)確性和穩(wěn)定性，本節(jié)提出一種基于多標(biāo)簽傳播方式(MLPS)的重疊社區(qū)識別算法，算法邏輯流程如圖2所示.

MLPS算法的迭代停止條件和后處理沿用COPRA算法的設(shè)定，因此本文只給出改進(jìn)的標(biāo)簽傳播方式和閾值選擇策略的部分代碼，即算法1.算法設(shè)置兩個標(biāo)簽向量：old和new，old.x(new.x)表示結(jié)點(diǎn)x更新前(后)的標(biāo)簽，每個結(jié)點(diǎn)都擁有一組標(biāo)簽對(c,b)，c是標(biāo)簽，b是結(jié)點(diǎn)擁有標(biāo)簽c的概率，N(x)是結(jié)點(diǎn)x的鄰居集合，算法的唯一參數(shù)是閾值選擇參數(shù)p.

3.3 算法的復(fù)雜度分析

4 社區(qū)間的結(jié)構(gòu)洞識別算法

本節(jié)根據(jù)MLPS算法的輸出結(jié)果，提出社區(qū)間的結(jié)構(gòu)洞識別算法(SHCDA).算法首先將所有重疊結(jié)點(diǎn)加入結(jié)構(gòu)洞的候選集合，然后分析社區(qū)重疊結(jié)構(gòu)和重疊結(jié)點(diǎn)的位置特征，輸出重要性得分top-k的結(jié)構(gòu)洞.

(9)

其中,n為結(jié)點(diǎn)i的鄰居數(shù)，Infj表示結(jié)點(diǎn)j的重要性；wij=pi,c為結(jié)構(gòu)洞i與其鄰居結(jié)點(diǎn)j的關(guān)系權(quán)重，c是結(jié)點(diǎn)j歸屬的社區(qū).

本文觀測真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)，發(fā)現(xiàn)部分結(jié)構(gòu)洞連接的只是一些普通結(jié)點(diǎn)，因受到鄰居結(jié)點(diǎn)的影響，導(dǎo)致結(jié)構(gòu)洞的得分過低.此外，結(jié)構(gòu)洞所處的結(jié)構(gòu)特性也會影響其重要性得分，令Ci表示重疊結(jié)點(diǎn)i歸屬的社區(qū)集合，OCi為結(jié)點(diǎn)i所處的重疊結(jié)構(gòu)，即OCi={oc|oc=Ci1∩Ci2∩…∩Cim}其中，Ci={Ci1,Ci2,…,Cim}，m是集合Ci的大小，m=|Ci|且m≥2.然后加入懲罰系數(shù)ε來衡量重疊結(jié)構(gòu)的影響，這樣算法輸出的結(jié)果將更加符合真實(shí)的情況.根據(jù)實(shí)驗(yàn)結(jié)果，設(shè)置ε的經(jīng)驗(yàn)值為0.1.最終結(jié)構(gòu)洞i的重要性得分計(jì)算公式如下：

(10)

SHCDA算法描述如算法2.

一般的，k取值較小，因此時間復(fù)雜度近似為O(d·r2)，其中d為重疊結(jié)點(diǎn)的平均度，r是重疊結(jié)點(diǎn)的個數(shù).在大數(shù)據(jù)的稀疏網(wǎng)絡(luò)環(huán)境下，d和r都較小，所以算法能夠有效地處理大規(guī)模網(wǎng)絡(luò).

5 實(shí)驗(yàn)分析

5.1 MLPS實(shí)驗(yàn)

MLPS算法的參數(shù)p取值根據(jù)數(shù)據(jù)集的不同而變化.給定數(shù)據(jù)集D，本文定義p在[0,1]范圍內(nèi)以步長0.05搜索，取使得算法輸出結(jié)果最優(yōu)的值作為算法在數(shù)據(jù)集D上的參數(shù).

5.1.1 評價方法

NMI(Normalized Mutual Information)[21]廣泛應(yīng)用于重疊社區(qū)挖掘的實(shí)驗(yàn)中，NMI值越接近1說明算法輸出的結(jié)果越接近真實(shí)的情況.對于合成網(wǎng)絡(luò)數(shù)據(jù)，存在標(biāo)準(zhǔn)的社區(qū)劃分結(jié)果，而大部分的真實(shí)網(wǎng)絡(luò)并沒有標(biāo)準(zhǔn)的結(jié)果，因此實(shí)驗(yàn)采用模塊度Qov[22]來分析算法在真實(shí)網(wǎng)絡(luò)中運(yùn)行的效果.

5.1.2 合成網(wǎng)絡(luò)實(shí)驗(yàn)

LFR網(wǎng)絡(luò)[21]通過模擬不同特性的真實(shí)網(wǎng)絡(luò)，可從多個角度測試算法的性能.實(shí)驗(yàn)選取LFR網(wǎng)絡(luò)的三個參數(shù)(om、μ和on/N)來驗(yàn)證算法的NMI值，其中om為重疊結(jié)點(diǎn)擁有的標(biāo)簽數(shù)；μ表示結(jié)點(diǎn)與社區(qū)外部結(jié)點(diǎn)鏈接的概率，隨著μ值增大，結(jié)點(diǎn)的社區(qū)外部鏈接增多，導(dǎo)致合成網(wǎng)絡(luò)結(jié)構(gòu)變得更加復(fù)雜，社區(qū)發(fā)現(xiàn)的難度也隨之增加；on/N表示重疊結(jié)點(diǎn)占網(wǎng)絡(luò)結(jié)點(diǎn)的比例.當(dāng)實(shí)驗(yàn)觀測其中某參數(shù)變化時，其他參數(shù)不變.實(shí)驗(yàn)結(jié)果如圖3(a)、3(b)、3(c)所示，MLPS算法的NMI值最優(yōu)，表明MLPS算法在處理不同特性的網(wǎng)絡(luò)時能夠取得較好的準(zhǔn)確度.圖3(d)分析了三種算法在網(wǎng)絡(luò)邊數(shù)從104增長到106時的運(yùn)行效率，結(jié)果顯示了這三種算法都具有接近線性的時間復(fù)雜度.

5.1.3 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)

本文選取7個不同的真實(shí)網(wǎng)絡(luò)，如表1所示，其中C-DBLP1和C-DBLP2是從WAMDM實(shí)驗(yàn)室提供的數(shù)據(jù)庫中抽取得到的兩個不同規(guī)模的學(xué)者合著網(wǎng)絡(luò).表1比較了MLPS、MLPA和COPRA算法取最優(yōu)參數(shù)時的平均模塊度Qov和方差Std.，結(jié)果顯示本文提出的MLPS算法能夠取得較好的效果.

表1 三種算法在真實(shí)網(wǎng)絡(luò)上運(yùn)行的模塊度比較

5.2 SHCDA實(shí)驗(yàn)

本節(jié)實(shí)驗(yàn)包含Coauthor實(shí)驗(yàn)和新浪微博實(shí)驗(yàn).Coauthor數(shù)據(jù)集[9]存在可對比的實(shí)驗(yàn)結(jié)果，能夠驗(yàn)證SHCDA算法的準(zhǔn)確度；新浪微博數(shù)據(jù)集通過爬蟲程序抓取，從一個特定用戶開始，抓取最近發(fā)表的微博中轉(zhuǎn)發(fā)數(shù)較高的微博及轉(zhuǎn)發(fā)該微博的用戶，并以廣度優(yōu)先的策略循環(huán)抓取數(shù)據(jù)，最后整理出63,641個用戶及1,391,718條用戶關(guān)系，其中包含27,759條微博轉(zhuǎn)發(fā)關(guān)系.

5.2.1 Coauthor實(shí)驗(yàn)

Coauthor數(shù)據(jù)集包含28個計(jì)算機(jī)相關(guān)的會議，涉及六個研究領(lǐng)域，如表2所示.每個領(lǐng)域都擁有一組程序委員會成員，我們認(rèn)為不同領(lǐng)域間的共同委員會成員即為這些領(lǐng)域間的結(jié)構(gòu)洞.該數(shù)據(jù)集包含1718個委員會成員，其中擁有107個結(jié)構(gòu)洞.

根據(jù)上述六個領(lǐng)域的相關(guān)性，本文選取三對領(lǐng)域(AI-DM，DB-DM和DP-NC)來驗(yàn)證算法的準(zhǔn)確度.同時實(shí)驗(yàn)選取PageRank[28]、COPRA和MLPA算法進(jìn)行對比分析，如圖4、圖5和圖6所示.本文提出的SHCDA算法在top-30之前都能取得最好的效果，而且從三個圖中可以發(fā)現(xiàn)，PageRank選取的重要結(jié)點(diǎn)大部分都不是結(jié)構(gòu)洞，因此結(jié)構(gòu)洞在網(wǎng)絡(luò)中可能只是一些普通結(jié)點(diǎn)，卻扮演著極其重要的角色.

表2 Coauthor數(shù)據(jù)集

5.2.2 新浪微博實(shí)驗(yàn)

在微博、Twitter等社交網(wǎng)絡(luò)中，社區(qū)間的結(jié)構(gòu)洞是不同群體進(jìn)行信息傳播的橋梁，一般存在于微博的轉(zhuǎn)發(fā)路徑中[9].因此，本文定義Precision來衡量SHCDA算法的準(zhǔn)確性：

(11)

其中,Nsh(k)表示SHCDA算法輸出的top-k結(jié)構(gòu)洞，Nf(k)是Nsh(k)中存在轉(zhuǎn)發(fā)微博行為的結(jié)點(diǎn)集合.實(shí)驗(yàn)結(jié)果如圖7所示，顯示出本文提出的SHCDA算法取得了最優(yōu)的準(zhǔn)確性，能夠有效地挖掘出社區(qū)間的結(jié)構(gòu)洞.

本文還考察了結(jié)構(gòu)洞的重要性對社區(qū)間的信息傳播的影響.針對算法輸出的top-k結(jié)構(gòu)洞，定義Rg表示在固定步長下存在轉(zhuǎn)發(fā)行為的結(jié)點(diǎn)相對增長數(shù)：

Rg=|Nf(k+C)|-|Nf(k)|

(12)

其中,C為增長步長，本節(jié)實(shí)驗(yàn)中C取50.從圖8中可以看出SHCDA算法在top-200前有較快的增幅，而后趨于穩(wěn)定，說明重要度較高的結(jié)構(gòu)洞更容易進(jìn)行社區(qū)間的信息傳播，這對社會網(wǎng)絡(luò)的信息傳播機(jī)制研究和輿情監(jiān)控具有重要的指導(dǎo)意義.

6 結(jié)論

為提高大數(shù)據(jù)環(huán)境下重疊社區(qū)發(fā)現(xiàn)的效果，本文結(jié)合結(jié)點(diǎn)間的相似性傳播和影響傳播兩種方式，提出了基于多標(biāo)簽傳播方式的重疊社區(qū)發(fā)現(xiàn)算法(MLPS)，實(shí)驗(yàn)驗(yàn)證了該算法取得了較高的準(zhǔn)確度和模塊度，且具有接近線性的時間復(fù)雜度；同時,基于MLPS算法的輸出結(jié)果，本文針對重疊結(jié)構(gòu)進(jìn)行分析，提出了社區(qū)間的結(jié)構(gòu)洞識別算法(SHCDA)，在不同特性數(shù)據(jù)集的實(shí)驗(yàn)顯示了該算法擁有較高的準(zhǔn)確度.

[1]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[2]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.

[3]Shi C,Cai Y,Fu D,et al.A link clustering based overlapping community detection algorithm[J].Data & Knowledge Engineering,2013,87:394-404.

[4]Whang J J,Gleich D F,Dhillon I S.Overlapping community detection using seed set expansion[A].CIKM 2013[C].San Francisco,CA,USA,ACM,2013.2099-2108.

[5]Burt R S.Structural Holes:The Social Structure of Competition[M].MA,Harvard University Press,1992.

[6]Kleinberg J,Suri S,Tardos é,et al.Strategic network formation with structural holes[A].Proceedings of the 9th ACM Conference on Electronic Commerce[C].Chicago,Illinois,USA,ACM,2008.284-293.

[7]Buskens V,Van de Rijt A.Dynamics of networks if everyone strives for structural holes[J].American Journal of Sociology,2008,114(2):371-407.

[8]李泓波,等.基于拓?fù)鋭莸闹丿B社區(qū)及社區(qū)間結(jié)構(gòu)洞識別.電子學(xué)報(bào),2014,42(1):62-69.

Li H B,et al.Identification of overlapping communities and structural holes between communities based on topological potential[J].Acta Electronica Sinica,2014,42(1):62-69.(in Chinese)

[9]Lou T,Tang J.Mining structural hole spanners through information diffusion in social networks[A].WWW 2013[C].Rio de Janeiro,Brazil,International World Wide Web Conferences Steering Committee,2013.825-836.

[10]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.

[11]Barber M J,Clark J W.Detecting network communities by propagating labels under constraints[J].Physical Review E,2009,80(2):026129.

[12]Liu X,Murata T.Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J].Physica A:Statistical Mechanics and its Applications,2010,389(7):1493-1500.

[13]Xie J,Szymanski B K.Community detection using a neighborhood strength driven label propagation algorithm[A].NSW 2011[C].New York,USA,IEEE,2011.188-195.

[14]Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):103018.

[15]Wu Z H,Lin Y F,Gregory S,et al.Balanced multi-label propagation for overlapping community detection in social networks[J].Journal of Computer Science and Technology,2012,27(3):468-479.

[16]Xie J,Szymanski B K,Liu X.Slpa:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[A].ICDMW 2011[C].Vancouver,BC,Canada,IEEE,2011.344-349.

[17]Dai Q,Guo M,Liu Y,et al.MLPA:Detecting overlapping communities by multi-label propagation approach[A].CEC 2013[C].Cancun,Mexico,IEEE,2013.681-688.

[18]Aral S,Walker D.Identifying influential and susceptible members of social networks[J].Science,2012,337(6092):337-341.

[19]Li Q,et al.Identifying influential spreaders by weighted LeaderRank[J].Physica A:Statistical Mechanics and its Applications,2014,404:47-55.

[20]Wang Y,Feng X.A Potential-Based Node Selection Strategy for Influence Maximization in a Social Network[M].Advanced Data Mining and Applications.Springer Berlin Heidelberg,2009.350-361.

[21]Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.

[22]Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory and Experiment,2009,2009(03):P03024.

[23]Zachary W.An information flow model for conflict and fission in small groups1[J].Journal of anthropological research,1977,33(4):452-473.

[24]Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.

[25]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[26]Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical review E,2006,74(3):036104.

[27]Newman M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409.

[28]Page L,Brin S,Motwani R,et al.The PageRank citation ranking:Bringing order to the web[R].Stanford InfoLab,1999-66.

劉世超 男，1989年2月出生，河南周口人.武漢大學(xué)計(jì)算機(jī)學(xué)院博士生，研究方向?yàn)樯鐣W(wǎng)絡(luò)分析和Web數(shù)據(jù)挖掘.

E-mail:nani@whu.edu.cn

朱福喜(通訊作者) 男，1957年7月出生，湖北武漢人.武漢大學(xué)計(jì)算機(jī)學(xué)院教授、博士生導(dǎo)師，主要從事人工智能和Web數(shù)據(jù)挖掘.

E-mail:fxzhu@whu.edu.cn

馮 曦 女，1991年11月出生，陜西西安人.武漢大學(xué)計(jì)算機(jī)學(xué)院碩士生,研究方向?yàn)樯鐣W(wǎng)絡(luò)分析和數(shù)據(jù)挖掘.

E-mail:fengxiwhu@outlook.com

Identifying Overlapping Communities and Structural Holes Between Communities in Complex Networks

LIU Shi-chao,ZHU Fu-xi,FENG Xi

(ComputerSchoolofWuhanUniversity，Wuhan,Hubei430072,China)

Many researchers focus on how to detect overlapping communities effectively and accurately when coping with large-scale networks in recent years.This paper proposes a novel overlapping community detection algorithm based on a multiple label propagation strategy,called MLPS algorithm.Firstly,MLPS selects a set of nodes as initial seeds by using Influence Maximization Model,each of which is assigned a unique label;Inspired by strategy based on similarity and influence diffusion,MLPS incorporates with these two strategies to guide the process of label propagation;Finally,nodes with the same tag are divided into one community after propagation.Experimental results on synthetic datasets and real networks illustrate that MLPS has both high accuracy and modularity at the same time.In addition,another algorithm named Structural Holes between Communities Detection Algorithm (SHCDA) is presented on the basis of the output of MLPS.SHCDA computes the scores of overlapping nodes who serve as structural holes by analyzing the overlapping structure and position feature of overlapping nodes,and then selects top-kstructural holes as the output.Experimental results on different datasets show that SHCDA gets the best accuracy.

complex networks；overlapping community；multiple label propagation；structural holes detection

2015-05-12;

2015-11-09;責(zé)任編輯：馬蘭英

國家自然科學(xué)基金(No.61272277);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金(No.274742)

TP391

A

0372-2112 (2016)11-2600-07

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.006