基于弱派系的多層社會網(wǎng)絡(luò)重疊社團發(fā)現(xiàn)算法

張月霞，楊瑞琪，康 勁

北京信息科技大學(xué)信息與通信工程學(xué)院, 北京 100101

社團發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究中的一個重要問題．現(xiàn)實生活中人們通常會使用多種社交工具進(jìn)行日常交流與活動，這些不同的社交網(wǎng)絡(luò)與用戶構(gòu)成了一個多層社會網(wǎng)絡(luò)[1]，該網(wǎng)絡(luò)中通常存在一些隱藏的社團結(jié)構(gòu)，其中的用戶往往會有更加緊密的聯(lián)系與接近的興趣．復(fù)雜網(wǎng)絡(luò)中的社團通常分為非重疊社團與重疊社團，非重疊社團中節(jié)點有且僅屬于一個社團，而重疊社團中節(jié)點可屬于多個不同社團，現(xiàn)實中的用戶一般會同時存在于多個社團之中，重疊社團較為接近真實情況[2]，多層社會網(wǎng)絡(luò)中的重疊社團發(fā)現(xiàn)，逐漸成為復(fù)雜網(wǎng)絡(luò)中的一個研究熱點．研究社會網(wǎng)絡(luò)中的社團有利于分析信息傳播與輿論傳播等問題，因此對社會網(wǎng)絡(luò)中社團發(fā)現(xiàn)的研究具有一定的現(xiàn)實意義．

目前，學(xué)者們對多層社會網(wǎng)絡(luò)與多層圖中的社團發(fā)現(xiàn)算法已有了一些研究．FAN等[3]使用局部社團檢測和根據(jù)相似度合并多層社團的方法進(jìn)行多層社會網(wǎng)絡(luò)的社團發(fā)現(xiàn)；CHEN等[4]將復(fù)雜網(wǎng)絡(luò)中的連接分解為多維結(jié)構(gòu)，使用FN(fast Newman)算法構(gòu)建兄弟矩陣挖掘網(wǎng)絡(luò)中隱藏的社團結(jié)構(gòu)；GLIGORIJEVI等[5]通過改進(jìn)非負(fù)矩陣分解的方法對多層圖進(jìn)行融合與聚類來發(fā)現(xiàn)社團結(jié)構(gòu)；PIZZUTI 等[6]將模塊化度作為目標(biāo)函數(shù)結(jié)合多目標(biāo)優(yōu)化算法檢測多層網(wǎng)絡(luò)中的社團．

也有學(xué)者使用不同的方法來挖掘復(fù)雜網(wǎng)絡(luò)中的重疊社團．JIANG等[7]將社會網(wǎng)絡(luò)中的異質(zhì)信息融合構(gòu)建用戶鄰接圖，并執(zhí)行多標(biāo)簽傳播來發(fā)現(xiàn)有效社團；SU等[8]使用結(jié)合局部聚類系數(shù)的種子集擴展方法挖掘社交網(wǎng)絡(luò)中的重疊社團；HUANG等[9]結(jié)合集成學(xué)習(xí)與粒子群優(yōu)化算法避免結(jié)果中冗余的小型社團；ZHANG等[10]提出了一種基于弱派系的算法，解決了傳統(tǒng)派系過濾算法應(yīng)用于大規(guī)模網(wǎng)絡(luò)時復(fù)雜度高的問題；ZHANG等[11]使用基于混合表現(xiàn)的多目標(biāo)進(jìn)化算法檢測復(fù)雜網(wǎng)絡(luò)中的重疊社團．雖然不少學(xué)者在多層網(wǎng)絡(luò)社團發(fā)現(xiàn)和重疊社團發(fā)現(xiàn)上做了很多研究，但針對多層社會網(wǎng)絡(luò)和重疊社團的社團發(fā)現(xiàn)算法較少，且現(xiàn)有算法較難檢測出小型網(wǎng)絡(luò)中的社團．

本研究提出一種基于弱派系的多層社會網(wǎng)絡(luò)重疊社團發(fā)現(xiàn)算法(weak clique based community detection algorithm, WC-CDA)，利用弱派系細(xì)粒度的特性，挖掘網(wǎng)絡(luò)中更小的社團結(jié)構(gòu)，并同時支持無向與有向網(wǎng)絡(luò)．通過檢測不同社會網(wǎng)絡(luò)中的弱派系，挖掘用戶在不同場景下的隱含關(guān)系，進(jìn)一步合并不同網(wǎng)絡(luò)的弱派系來得到多層社會網(wǎng)絡(luò)中的重疊社團結(jié)構(gòu)．

1 相關(guān)知識

1.1 多層社會網(wǎng)絡(luò)與重疊社團

目前的多層或多維社會網(wǎng)絡(luò)[3-4，6]中，重疊社團發(fā)現(xiàn)的一般步驟是先檢測不同層或不同維度網(wǎng)絡(luò)的重疊社團，再對檢測結(jié)果進(jìn)行融合，最終得到劃分結(jié)果．

1.2 基于局部社團的多層在線網(wǎng)絡(luò)重疊社團發(fā)現(xiàn)算法

FAN等[3]提出的基于局部社團的多層在線網(wǎng)絡(luò)重疊社團發(fā)現(xiàn)算法(local community based community detection algorithm, LC-CDA)是一種較新的多層社會網(wǎng)絡(luò)重疊社團發(fā)現(xiàn)算法．該算法步驟為

1)檢測每層網(wǎng)絡(luò)中的局部社團，對于網(wǎng)絡(luò)中的每個節(jié)點，將其與鄰居節(jié)點劃分進(jìn)局部社團c中， 對于c中的每個節(jié)點，計算其社團內(nèi)和社團外節(jié)點連接數(shù)的差值，即

(1)

其中，若節(jié)點i與節(jié)點j之間有連接，則aij=1．

3)計算所有局部社團中兩兩的重疊系數(shù)(ci∩cj)/min{ci,cj}， 與閾值β(0<β<1)進(jìn)行比較，若大于閾值則對兩個局部社團進(jìn)行合并，得到社團劃分結(jié)果．

LC-CDA算法將根據(jù)數(shù)據(jù)集中喜好信息所劃分的社團結(jié)果作為正確結(jié)果，并與算法所劃分的社團結(jié)果進(jìn)行比較，即通過式(2)計算兩種結(jié)果的相似度對算法進(jìn)行評價．

(2)

(3)

S的取值范圍是[0, 1]．S值越大，表示該算法所劃分的社團與使用喜好信息劃分的社團越接近，算法性能越好．

該算法中局部社團僅考慮了社團整體與外部的聯(lián)系，未考慮社團內(nèi)部節(jié)點間的拓?fù)鋵傩?，因此無法發(fā)現(xiàn)更多細(xì)粒度的小社團，且經(jīng)本研究實驗發(fā)現(xiàn)，LC-CDA用于小型多層社會網(wǎng)絡(luò)時，很難有效地檢測出多個重疊社團結(jié)構(gòu)．為此，本研究提出一種基于弱派系的多層社會網(wǎng)絡(luò)重疊社團發(fā)現(xiàn)算法．

2 多層社會網(wǎng)絡(luò)重疊社團發(fā)現(xiàn)算法

WC-CDA首先計算不同社會網(wǎng)絡(luò)層的弱派系，然后將這些弱派系根據(jù)相似度進(jìn)行合并，得到社團劃分結(jié)果，最后通過綜合考慮節(jié)點度和鄰居連接屬性的弱派系來發(fā)現(xiàn)小型網(wǎng)絡(luò)中的社團結(jié)構(gòu)．

2.1 弱派系

在一個網(wǎng)絡(luò)G=(V,E)中，其中V為節(jié)點集合，E為節(jié)點間的邊集合，假設(shè)u和v是G中的兩個相鄰節(jié)點，則由節(jié)點u和v所決定的弱派系定義為

Guv=(Vuv,Euv)

(4)

其中，Vuv={u,v}∪{Nu,Nv}，Vuv分別為節(jié)點u和v及其鄰居節(jié)點構(gòu)成的節(jié)點集合，Nu和Nv為節(jié)點u和v的鄰居節(jié)點集合；Euv={(x,y)∈E}x，y∈Vuv}，Euv為Vuv中節(jié)點間屬于邊集E中的連邊所構(gòu)成的邊集合．節(jié)點u和v分別通過計算節(jié)點優(yōu)先級與節(jié)點相似度得出．

2.2 節(jié)點優(yōu)先級

在一個網(wǎng)絡(luò)G=(V,E)中，其中，V為節(jié)點集合，E為節(jié)點間的邊集合，假設(shè)u為G中的一個節(jié)點，則節(jié)點u的優(yōu)先級定義為

(5)

其中，mu為節(jié)點u的所有鄰居節(jié)點之間的邊數(shù)；k為節(jié)點u的度．對于有向圖，使用節(jié)點u的入度計算優(yōu)先級Pu， 即

(6)

其中，mu為節(jié)點u的所有鄰居節(jié)點之間的邊數(shù)；kin為節(jié)點u的入度．

式(5)與式(6)綜合了僅考慮節(jié)點度的度中心性，與僅考慮鄰居節(jié)點連接數(shù)量的局部聚類系數(shù)．兩個公式同時利用了度與鄰居節(jié)點間的連接數(shù)，有利于估計節(jié)點鄰居間連接的緊密程度，優(yōu)先級越大則表明節(jié)點鄰居間的連接越緊密．

選擇網(wǎng)絡(luò)中優(yōu)先級最大的節(jié)點作為構(gòu)建弱派系中的一個節(jié)點，另一節(jié)點是與優(yōu)先級最大節(jié)點的鄰居節(jié)點中相似度最大的節(jié)點．

2.3 節(jié)點相似度

在一個網(wǎng)絡(luò)G=(V,E)中，其中V為節(jié)點集合，E為節(jié)點間的邊集合，假設(shè)u和v是G中的兩個鄰接節(jié)點，則這兩個節(jié)點的相似度定義為

(7)

其中，Nu和Nv分別為節(jié)點u和節(jié)點v的鄰居節(jié)點集；Nu和Nv分別為集合Nu和Nv中的元素數(shù)．本算法中計算節(jié)點相似度采用的是Slaton指標(biāo)[14]，在基于共同鄰居的相似性指標(biāo)中，常用的還有Jaccard指標(biāo)[15]和Sorenson指標(biāo)[16]等．

2.4 弱派系相似度

在一個網(wǎng)絡(luò)G=(V,E)中，其中，V為節(jié)點集合，E為節(jié)點間的邊集合，假設(shè)C1和C2是G中的兩個弱派系，則定義弱派系C1和C2間的相似度為

(8)

對于弱派系C1和C2， 有0≤SCC1C2≤max(V(C1),V(C2))． 對于一個網(wǎng)絡(luò)中的弱派系設(shè)置相同的閾值β， 若兩個弱派系的相似度大于閾值時則合并為一個社團，因此本算法也具有可調(diào)重疊社團相似性的特點．文獻(xiàn)[10]提出的相似度計算考慮到了兩者共同的節(jié)點與邊，而本算法僅考慮共同的節(jié)點以便合并多個網(wǎng)絡(luò)層的弱派系．

2.5 評價指標(biāo)

社團劃分結(jié)果的評價指標(biāo)一般有歸一化互信息(normalized mutual information，NMI)[17]指標(biāo)與調(diào)整蘭德系數(shù)(adjusted Rand index，ARI)[18]指標(biāo)等．由于大多數(shù)真實網(wǎng)絡(luò)數(shù)據(jù)集無事先標(biāo)記好的社團劃分結(jié)果，因此無法使用這兩種指標(biāo)進(jìn)行評價．對于未知結(jié)果的重疊社團評估，目前主要使用擴展模塊化度Qov[19]， 即

(9)

其中，A為網(wǎng)絡(luò)的鄰接矩陣；Ci為一個社團(1≤i≤l，l為社團個數(shù))；m為網(wǎng)絡(luò)的邊數(shù)；Qv為節(jié)點v所屬社團個數(shù)；kv為節(jié)點v的度．Qov越大表明社團劃分的效果越好．

式(9)并不適用于多層網(wǎng)絡(luò)社團的劃分，考慮到網(wǎng)絡(luò)密度與連邊數(shù)對社團發(fā)現(xiàn)的影響，將網(wǎng)絡(luò)的邊數(shù)比例作為網(wǎng)絡(luò)權(quán)重，構(gòu)建新的指標(biāo)Qmov， 用于評價多層社會網(wǎng)絡(luò)重疊社團劃分結(jié)果．Qmov值越大表明社團劃分結(jié)果越好．

定義多層網(wǎng)絡(luò)重疊社團的評價指標(biāo)Qmov為

(10)

其中，Qi為第i層網(wǎng)絡(luò)的擴展模塊化度；wi為第i層網(wǎng)絡(luò)的權(quán)重，定義為

(11)

其中，Ei為第i層網(wǎng)絡(luò)的邊數(shù)．

從式(11)可見，網(wǎng)絡(luò)邊數(shù)比例越大，即相對網(wǎng)絡(luò)密度越大，則模塊化度的權(quán)重越大．

2.6 算法步驟

算法的輸入為多層社會網(wǎng)絡(luò)Gml和相似度閾值β， 輸出為社團集合S， 具體步驟為：

1) 初始化S， 設(shè)定閾值β， 輸入多層網(wǎng)絡(luò)數(shù)據(jù)，對每一層網(wǎng)絡(luò)G執(zhí)行步驟 2)至步驟 4)，得到弱派系結(jié)果，然后執(zhí)行步驟5)．

2) 初始化弱派系集合WC．

3) 根據(jù)式(5)或式(6)計算當(dāng)前網(wǎng)絡(luò)G中所有節(jié)點的優(yōu)先級， 并選取優(yōu)先級最大的節(jié)點u， 根據(jù)式(7)計算節(jié)點u的鄰居節(jié)點中與u相似度最大的節(jié)點v， 使用節(jié)點u與節(jié)點v根據(jù)式(4)構(gòu)建弱派系wc并保存至WC．

4) 將步驟 3)中弱派系wc的節(jié)點從G中移除，若G中節(jié)點非空則回到步驟3)；

5) 根據(jù)每一層的弱派系結(jié)果構(gòu)建弱派系集合WClique，并將所有弱派系標(biāo)記為未訪問，對WClique中的所有弱派系執(zhí)行步驟 6)至步驟8)．

6) 若所選的弱派系C1未被訪問，則執(zhí)行步驟 7)，否則選擇下一個弱派系執(zhí)行步驟 6)至步驟8)；

7) 將C1標(biāo)記為已訪問，對與弱派系C1有重合節(jié)點的弱派系集合N(C1)中的弱派系執(zhí)行步驟8)．

8) 計算弱派系C1與鄰居弱派系C2的相似度，將C2標(biāo)記為已訪問．若大于β則合并為一個社團，保存檢測出的社團至社團集合S中，否則，不進(jìn)行合并．

9) 返回社團集合S．

3 仿 真

3.1 數(shù)據(jù)集

本研究采用tailorshop、AUCS和FF-TW-YT三種真實的多層社會網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行仿真實驗，如表1．其中，tailorshop數(shù)據(jù)集是由KAPFERER[20]收集的服裝廠內(nèi)39名員工工作與朋友關(guān)系的雙層網(wǎng)絡(luò)數(shù)據(jù)；AUCS數(shù)據(jù)集是由ROSSI等[21]收集的某大學(xué)61名雇員不同線上線下關(guān)系的網(wǎng)絡(luò)數(shù)據(jù)，該數(shù)據(jù)集分為lunch、facebook、coauthor、leisure和work五層，均為無向無權(quán)網(wǎng)絡(luò)；FF-TW-YT數(shù)據(jù)集是由MAGNANI等[22]采集的500名用戶在多個在線社交網(wǎng)站上的關(guān)系網(wǎng)絡(luò)數(shù)據(jù)，每個用戶都擁有多個不同社交網(wǎng)站的賬號，并在每一層具有不同關(guān)系網(wǎng)．該數(shù)據(jù)集包含F(xiàn)riendFeed、Twitter和YouTube三層，且均為無權(quán)網(wǎng)絡(luò)，其中FriendFeed與Twitter層為有向網(wǎng)絡(luò)，YouTube層為無向網(wǎng)絡(luò)．

表1 多層社會網(wǎng)絡(luò)數(shù)據(jù)集

3.2 結(jié)果與分析

為評估WC-CDA的有效性，將其與LC-CDA比較．兩種算法的執(zhí)行順序都是先檢測單層網(wǎng)絡(luò)的結(jié)果，然后根據(jù)β進(jìn)行社團的合并，通過比較不同相似度下社團發(fā)現(xiàn)結(jié)果的屬性與評價指標(biāo)來進(jìn)行評估．由于LC-CDA所用的評估方法只適用于已有結(jié)果的數(shù)據(jù)集，不具有通用性，因此，本研究在仿真過程中使用Qmov指標(biāo)對兩種算法進(jìn)行評價．

圖1 Tailorshop數(shù)據(jù)集上的仿真結(jié)果Fig.1 Result of simulation on Tailsorshop data set

圖1是將WC-CDA用于tailorshop數(shù)據(jù)集時的仿真結(jié)果．從圖1(a)可見，WC-CDA在0.5≤β≤0.9時可挖掘出更多的社團，而LC-CDA在β≥0.7時僅挖掘出少量社團．由圖1(b)可見，WC-CDA所發(fā)現(xiàn)的社團尺寸較?。蓤D1(c)可見，在有社團發(fā)現(xiàn)結(jié)果的β區(qū)間內(nèi)，WC-CDA算法的Qmov值明顯優(yōu)于LC-CDA算法的Qmov值．

圖2 AUCS數(shù)據(jù)集上的仿真結(jié)果Fig.2 Result of simulation on AUCS data set

圖2是在丹麥奧胡斯大學(xué)計算機科學(xué)系(The Department of Computer Science at Aarhus University，AUCS)數(shù)據(jù)集上的仿真結(jié)果．從圖2(a)和圖2(b)可見，兩種算法在不同β值下的社團發(fā)現(xiàn)結(jié)果與Tailorshop數(shù)據(jù)集上的仿真結(jié)果變化趨勢相同．WC-CDA在0.5≤β≤0.9時可檢測出更多的社團，而LC-CDA在β≥0.7時檢測出少量社團，且WC-CDA所發(fā)現(xiàn)的社團平均尺寸較小．由圖2(c)可見，WC-CDA的Qmov值高于LC-CDA的Qmov值．

圖3是用于FF-TW-YT數(shù)據(jù)集的仿真結(jié)果．從圖3(a)可見，WC-CDA在β≥0.5時可檢測出大量社團，而LC-CDA所檢測的社團數(shù)量緩慢增長，且從圖1(b)可見，WC-CDA所檢測的社團平均尺寸較小．由圖3(c)可見，當(dāng)0.1≤β<0.5時，WC-CDA的Qmov優(yōu)于LC-CDA；當(dāng)0.5≤β≤0.9時，LC-CDA的Qmov優(yōu)于WC-CDA．

圖3 FF-TW-YT數(shù)據(jù)集上的仿真結(jié)果Fig.3 Result of simulation on FF-TW-YT data set

結(jié) 語

本研究引入弱派系概念使得多層社會網(wǎng)絡(luò)中的社團劃分結(jié)果具有更加細(xì)粒度的特點．在無向的tailorshop數(shù)據(jù)集與AUCS數(shù)據(jù)集網(wǎng)絡(luò)中，WC-CDA在同一閾值范圍內(nèi)與LC-CDA相比，能挖掘出更多細(xì)粒度的社團，可有效發(fā)現(xiàn)這種小型網(wǎng)絡(luò)中的社團．同時，在有向的FF-TW-YT數(shù)據(jù)集網(wǎng)絡(luò)中WC-CDA也能挖掘出比LC-CDA更多且規(guī)模更小的社團．WC-CDA的提出對于多層社會網(wǎng)絡(luò)中重疊社團的社團發(fā)現(xiàn)具有一定的參考借鑒價值．