吳 春 國， 李 艷 振， 李 瑛， 高 瑞， 時 小 虎*

(1.吉林大學(xué) 符號計算與知識工程教育部重點實驗室， 吉林 長春 130012；2.吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 吉林 長春 130012；3.吉林大學(xué)珠海學(xué)院 計算機學(xué)院， 廣東 珠海 519041 )

0 引 言

現(xiàn)實世界中的許多問題都可以簡化為復(fù)雜網(wǎng)絡(luò)進行研究.因此，越來越多的研究者熱衷于研究復(fù)雜網(wǎng)絡(luò)，挖掘其隱藏價值.復(fù)雜網(wǎng)絡(luò)擁有很多特性，如小世界性(small world)[1]、無標度性(scale-free)[2]和高聚集特性等.此外，復(fù)雜網(wǎng)絡(luò)還呈現(xiàn)出明顯的社區(qū)結(jié)構(gòu)[3-4].社區(qū)結(jié)構(gòu)也可稱作網(wǎng)絡(luò)簇結(jié)構(gòu).在社區(qū)結(jié)構(gòu)中，同一個社區(qū)內(nèi)邊數(shù)很多，節(jié)點之間連接稠密，而跨社區(qū)相連的邊相對比較稀疏.那些具有相似功能或?qū)傩缘墓?jié)點組成相同的社區(qū)，而不同的社區(qū)相互連接構(gòu)成完整的復(fù)雜網(wǎng)絡(luò).相對于整個系統(tǒng)，社區(qū)就像人體結(jié)構(gòu)中的一個器官或者組織，為了更好地解釋和了解復(fù)雜系統(tǒng)功能，需要對社區(qū)的結(jié)構(gòu)進行分析和研究.自從Girvan等[3]提出了社區(qū)發(fā)現(xiàn)的概念以來，復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的研究成果不斷涌現(xiàn)，主要可以分為譜方法、模塊度優(yōu)化方法、層次聚類方法和邊預(yù)測方法等[5].

在實際生活中，復(fù)雜網(wǎng)絡(luò)中的節(jié)點可以同時存在于多個社區(qū)中，因此這些社區(qū)之間會有重疊部分.在社交網(wǎng)絡(luò)中，每個個體通常具有多個不同的社區(qū)屬性，可能同時屬于多個社會團體，如家庭、朋友圈、同事圈.同樣，社區(qū)重疊現(xiàn)象廣泛存在于生物分子網(wǎng)絡(luò)中.比如在基因調(diào)控網(wǎng)絡(luò)或者蛋白質(zhì)相互作用網(wǎng)絡(luò)中，單個基因或者蛋白質(zhì)往往參與多個生物功能表達過程.因此，研究復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)或者重疊節(jié)點具有非常重要的意義.又比如在網(wǎng)絡(luò)謠言的傳播中，那些處于重疊節(jié)點位置的個體對于謠言的擴散傳播起了決定性的作用.研究重疊節(jié)點的性質(zhì)有助于深入理解謠言的傳播機制.在生物網(wǎng)絡(luò)中，不同的生物功能之間相互關(guān)聯(lián)，并非完全割裂，重疊節(jié)點往往預(yù)示著關(guān)鍵信息，對于人類疾病的治療、農(nóng)作物抗病性的研究都具有重要意義.

近年來，重疊社區(qū)發(fā)現(xiàn)算法研究取得了很大進展，典型的算法大致可以分為5類[6]：派系過濾算法、邊劃分算法、局部擴展與優(yōu)化算法、模糊發(fā)現(xiàn)算法、標簽傳播算法.Palla等于2005年提出了派系過濾算法的代表方法——CPM(clique percolation method)[7]，其基本思想是復(fù)雜網(wǎng)絡(luò)中多個派系(完全子圖)之間相互重疊，構(gòu)成了復(fù)雜網(wǎng)絡(luò)中的社區(qū).派系過濾算法通過尋找相互連通k-派系的方法確定社區(qū)結(jié)構(gòu).派系過濾算法也可以實現(xiàn)重疊節(jié)點的社區(qū)發(fā)現(xiàn)，因為在派系過濾算法中的單個節(jié)點可能屬于不同k-派系.邊劃分算法將復(fù)雜網(wǎng)絡(luò)中的邊進行劃分，從而對復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)進行挖掘.如果一個節(jié)點連接在一條邊上，而且這條邊被劃分到多個邊聚簇中，則此節(jié)點被判定為重疊節(jié)點[8-9].局部擴展與優(yōu)化算法的社區(qū)發(fā)現(xiàn)過程是利用局部擴展與優(yōu)化算法完成的.在社區(qū)發(fā)現(xiàn)的過程中，這種算法使用局部社區(qū)或者已發(fā)現(xiàn)社區(qū)組成種子社區(qū)，而節(jié)點之間連接的緊密程度往往通過局部密度函數(shù)進行度量[10-11].模糊發(fā)現(xiàn)算法在每一個節(jié)點上計算歸屬因子向量(belonging factor)[12]，以此來計算社區(qū)與社區(qū)的聯(lián)系強度和節(jié)點對的聯(lián)系強度.標簽傳播算法的主要思想是用標簽傳播的方式來確定每一個節(jié)點所屬的社區(qū)，這是比較流行的一類算法.Gregory等在非重疊節(jié)點社區(qū)發(fā)現(xiàn)的標簽傳播算法LPA基礎(chǔ)上將每個節(jié)點的標簽用多個類標簽標識，并引入隸屬度的概念，提出了COPRA算法進行重疊節(jié)點社區(qū)發(fā)現(xiàn)[13-14].SLPA算法也是一種標簽傳播的重疊社區(qū)發(fā)現(xiàn)算法，它通過模擬演講者-收聽者來完成標簽傳播過程[15].在LPA算法中，復(fù)雜網(wǎng)絡(luò)中的節(jié)點不會記住在某一時刻接收到的標簽信息.與之不同的是，SLPA算法會保存節(jié)點曾經(jīng)收到的所有標簽，為每一個節(jié)點設(shè)立一個用于存儲對應(yīng)標簽概率分布的存儲區(qū)，其中的存儲概率分布表示了當前節(jié)點的歸屬強度.文獻[16]介紹了一種完全不一樣的標簽傳播算法SpeakEasy.該算法運行速度快，適合不同種類的網(wǎng)絡(luò)，但存在的問題是在識別重疊節(jié)點過程中可能出現(xiàn)重疊節(jié)點比重過大的現(xiàn)象.

本文借鑒SpeakEasy算法的思想，首先通過標簽傳播算法得到初始的無重疊社區(qū)劃分，然后通過設(shè)計新的節(jié)點識別算法確定重疊節(jié)點，最后再對社區(qū)進行合并，提出OCPLP(overlapping community partitioning based on label propagation)算法.通過在LFR人工數(shù)據(jù)集、3個標準公開測試集以及真實的大豆基因共表達網(wǎng)絡(luò)上對本文提出的算法與已有算法進行對比.

1 SpeakEasy算法簡介

SpeakEasy與COPRA、SLPA等算法一樣，都是以標簽傳播為基礎(chǔ)，通過標簽傳播把每個節(jié)點劃分到對應(yīng)的社區(qū)中.不同的是，SpeakEasy同時考慮整個網(wǎng)絡(luò)的全局標簽分布情況與局部標簽分布情況，結(jié)合了自頂而下策略與自底而上策略對標簽進行傳播.自頂而下策略主要是依據(jù)當前復(fù)雜網(wǎng)絡(luò)中的全局標簽分布情況來決定標簽的傳播，自底而上策略則主要考慮當前節(jié)點與鄰居節(jié)點組成的局部子圖中的標簽分布信息.

SpeakEasy算法可以分為兩個階段：第1個階段是非重疊社區(qū)劃分，首先進行標簽傳播過程，待標簽傳播收斂以后，可以提取到一個完整的非重疊社區(qū)劃分結(jié)果，重復(fù)此過程Nt次，得到Nt個非重疊劃分，從Nt個劃分中篩選出一個最優(yōu)劃分.如果不考慮重疊節(jié)點的話，此時已經(jīng)得到了社區(qū)劃分的結(jié)果.第2個階段是重疊節(jié)點識別，即在最優(yōu)劃分基礎(chǔ)上識別重疊節(jié)點.首先根據(jù)得到的Nt個劃分結(jié)果計算共生矩陣A，A中的元素aij表示節(jié)點vi和vj在Nt次劃分中被聚為同一個社區(qū)的次數(shù).如果最優(yōu)劃分某個社區(qū)C之外的某個節(jié)點v與C中的節(jié)點的共生次數(shù)大于給定閾值，則可以認定v為C的重疊節(jié)點.定義節(jié)點v和社區(qū)C的平均權(quán)值為

(1)

當Wv C大于給定閾值γ時，認定v為C的重疊節(jié)點.

SpeakEasy算法的優(yōu)勢在于較少人工設(shè)定參數(shù)，適合不同種類的網(wǎng)絡(luò)圖，快速完成擁有大量節(jié)點的網(wǎng)絡(luò)圖的處理任務(wù).不足之處是此算法在識別重疊節(jié)點時會有重疊節(jié)點比重過大的現(xiàn)象.

2 OCPLP算法

SpeakEasy算法存在兩個問題.首先，當網(wǎng)絡(luò)圖規(guī)模較大且圖中重疊節(jié)點較多時，兩個社區(qū)之間會有大量的重合區(qū)域.其次，小社區(qū)對大社區(qū)內(nèi)的節(jié)點吸引力過大，會存在“蛇吞象”現(xiàn)象.為了解決這兩個問題，本文分別設(shè)計了新的重疊社區(qū)發(fā)現(xiàn)算法，并在最后增加了社區(qū)合并過程，提出了OCPLP算法，具體如下：

(1)隨機初始化網(wǎng)絡(luò)圖

設(shè)整個網(wǎng)絡(luò)圖G包含n個節(jié)點，以每個節(jié)點的ID作為社區(qū)的標簽信息.首先為每個節(jié)點i建立大小為Nb的緩沖區(qū)，記為bi，用以保存最近Nb次更新的標簽.初始化時從該節(jié)點的鄰居節(jié)點中隨機抽取Nb次，將選中的鄰居節(jié)點ID填入緩沖區(qū)，如圖1所示.

圖1 隨機初始化網(wǎng)絡(luò)圖

(2)標簽傳播

①計算標簽的全局概率分布，即計算所有標簽在圖G中全部節(jié)點緩沖區(qū)中的概率分布：

(2)

其中ni為第i個標簽在圖G中所有節(jié)點緩沖區(qū)出現(xiàn)的次數(shù)總和.

(3)

③計算每個節(jié)點的標簽局部特異性，即該節(jié)點的鄰居節(jié)點緩沖區(qū)中標簽的實際分布與期望分布之差.記第i個標簽在第j個節(jié)點的局部特異性為sji，則其計算公式為

(4)

④更新節(jié)點的緩沖區(qū).對于第j個節(jié)點的緩沖區(qū)bj，選擇最大的sji所對應(yīng)的標簽作為該節(jié)點的新增標簽，即刪除bj中的第1個元素，在隊尾插入所選擇的標簽.

⑤重復(fù)②～④，遍歷圖G中所有節(jié)點.

⑥重復(fù)①～⑤，直到所有節(jié)點的緩沖區(qū)收斂.

例如在圖1中一共有8個標簽a、b、c、d、g、h、i、j，其全局概率分布依次為3/40、5/40、6/40、7/40、7/40、4/40、5/40、3/40.以節(jié)點d為例，其鄰居節(jié)點的緩沖區(qū)的標簽a、b、c、d、g、h、i、j的實際數(shù)量分布為2、2、3、6、2、2、2、1，總數(shù)為20.而按照全局概率分布，這8個標簽的期望數(shù)分別為1.5、2.5、3.0、3.5、3.5、2.0、2.5、1.5.因此8個標簽的特異程度分別為0.5、-0.5、0、2.5、-1.5、0、-0.5、-0.5，最大的為標簽d的2.5.因此對節(jié)點d的緩沖區(qū)進行更新時首先刪除其第1個位置的d，其余4個位置的c、b、h、g分別前移1位，末尾補充特異性最大的標簽d.

(3)抽取社區(qū)劃分結(jié)果

根據(jù)上述得到的標簽分布結(jié)果進行社區(qū)劃分，具體過程如下：

①統(tǒng)計第j個節(jié)點所有鄰居緩沖區(qū)中的標簽數(shù).將數(shù)目最多的標簽作為該節(jié)點的所屬社區(qū)ID.該社區(qū)若已經(jīng)存在，則將第j個節(jié)點劃分到此社區(qū)中；若不存在，則以該ID新建社區(qū)，并添加第j個節(jié)點為該社區(qū)元素.

②重復(fù)①，遍歷圖中所有節(jié)點，假設(shè)共建立了k個社區(qū)，也就是說得到了一個包含k個社區(qū)的劃分結(jié)果P={C1，C2，…，Ck}.

(4)選擇最優(yōu)劃分

(5)

(6)

選擇最大評價一致性的劃分為最優(yōu)劃分.如果不考慮重疊節(jié)點的話，該劃分就是最終社區(qū)劃分的結(jié)果.

(5)識別重疊社區(qū)節(jié)點

計算Nt個劃分的共生矩陣A，元素aij表示節(jié)點vi和vj在Nt次劃分中被聚為同一個社區(qū)的次數(shù).定義節(jié)點v和社區(qū)Ci的平均權(quán)值為

(7)

若Wv Ci>γ1，則節(jié)點v為社區(qū)Ci的重疊節(jié)點，γ1為設(shè)定的閾值.需要指出的是，式(7)中不僅考慮了社區(qū)Ci的規(guī)模，而且也考慮了社區(qū)Cj的規(guī)模，這樣就在很大程度上避免了將大量大類節(jié)點計入小類的重疊節(jié)點，從而導(dǎo)致重疊節(jié)點比例過大的問題.識別重疊社區(qū)節(jié)點算法的偽代碼如下：

OCPLP-識別重疊社區(qū)節(jié)點

： 重疊節(jié)點的閾值γ1，共生矩陣A

： 最優(yōu)劃分C，圖中全部節(jié)點集合G

1： function FindOverlapNodes(γ1，A，G，C)

2： forv∈Gdo

3： forci∈Cdo

5： ifWv Ci>γ1then

6：Ci←Ci∪{v}

7： end if

8： end for

9： end for

10： end function

(6)社區(qū)合并

如果兩個社區(qū)之間重合部分占比達到設(shè)定閾值，則合并這兩個社區(qū)，即

其中γ2為設(shè)定的閾值.算法偽代碼描述如下：

OCPLP-社區(qū)合并算法

： 合并社區(qū)的閾值γ2，共生矩陣A

： 最優(yōu)劃分C，圖中全部節(jié)點集合G

1： function MergeCommunities(γ2，A，C，G)

2： forCi∈Cdo

3： forCj∈CandCj≠Cido

4： if |Ci∩Cj|/|Cj|>γ2then

5： forv∈Cjdo //合并Cj到Ci

ifv?Cithen

Ci←Ci∪{v}

6： end if

7： end for

8： deleteCj

9： end if

10： end for

11： end for

12： end function

3 實 驗

為驗證本文算法的有效性，共設(shè)計了3個實驗.首先利用LFR benchmark算法[17]生成虛擬的重疊網(wǎng)絡(luò)，在人工數(shù)據(jù)集上將本文提出的OCPLP 與SLPA[15]、SpeakEasy[16]兩種當前主流重疊社區(qū)劃分算法進行對比.在第2個實驗中選擇幾種常用的公開標準測試集，比較OCPLP與兩種比較算法的性能.最后一個實驗選擇了實際的大豆基因共表達網(wǎng)絡(luò)，分別使用SpeakEasy和OCPLP算法對基因共表達網(wǎng)絡(luò)進行重疊社區(qū)劃分，并且比較兩種算法的結(jié)果.

3.1 LFR benchmark數(shù)據(jù)集對比

LFR benchmark引入網(wǎng)絡(luò)度分布和社區(qū)大小分布的指數(shù)等參數(shù)來生成重疊網(wǎng)絡(luò)，所生成的網(wǎng)絡(luò)能夠模擬現(xiàn)實網(wǎng)絡(luò)中的重要性質(zhì)[17].LFR benchmark中提供了多種參數(shù)以控制生成網(wǎng)絡(luò)的拓撲結(jié)構(gòu).本文利用LFR benchmark工具生成了3個人工網(wǎng)絡(luò)圖：LFR1、LFR2、LFR3.表1列出了生成3個網(wǎng)絡(luò)圖時所使用的參數(shù)，各個參數(shù)的定義如下：N為節(jié)點數(shù)，m為邊數(shù)，k為平均度，kmax為最大度，μ為混合程度，non為重疊節(jié)點數(shù)，noc為每個重疊節(jié)點從屬的社區(qū)個數(shù).

表1 生成LFR benchmark網(wǎng)絡(luò)圖的參數(shù)

復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法的性能常用模塊度Q[18]作為評價指標，其定義如下：

(8)

式中：m為網(wǎng)絡(luò)中總的邊數(shù)；Oi表示節(jié)點i所屬社區(qū)個數(shù)；Nij=1代表節(jié)點i和節(jié)點j之間存在連邊，否則不存在連邊；ki為節(jié)點i度數(shù)；li為節(jié)點i屬于某個社區(qū)的標號；δ(li，lj)=1當且僅當li=lj.

評價復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法的性能的另一個常用指標為標準化互信息，對兩個劃分P(i)和P(j)，其標準化互信息為[11]

(9)

OCPLP與兩種比較算法的模塊度Q和標準化互信息In的對比結(jié)果如表2所示.緩沖區(qū)大小對結(jié)果整體影響不大，在本文實驗中該參數(shù)取值為5.從表2可以看出，在人工數(shù)據(jù)集的兩個指標上，OCPLP算法比SLPA、SpeakEasy兩種算法表現(xiàn)略好.

表2 LFR benchmark數(shù)據(jù)集上的對比結(jié)果

下面重點考察對重疊節(jié)點的識別情況，將識別重疊節(jié)點的過程理解為二分類問題，將重疊節(jié)點理解為正樣本，將非重疊節(jié)點理解為負樣本，用召回率γr、精確率γp、F1度量3個評估指標來評價OCPLP算法與兩種比較算法的優(yōu)劣.

γr=nT/(nT+nN)

(10)

γp=nT/(nT+nP)

(11)

F1=2×(γr×γp)/(γr+γp)

(12)

其中nT為真陽性樣本數(shù)，即對正類樣本預(yù)測正確的樣本數(shù)；nP為假陽性樣本數(shù)，即把負類樣本預(yù)測為正類的樣本數(shù)；nN為假陰性樣本數(shù)，即把正類樣本預(yù)測為負類的樣本數(shù).

表3給出了在LFR1、LFR2、LFR3人工數(shù)據(jù)集上重疊節(jié)點識別的比較結(jié)果.由表3可以看出，在LFR1上，3種算法在3個指標的綜合表現(xiàn)差異不大，其中OCPLP的表現(xiàn)最好.在LFR2和LFR3上，3種算法的表現(xiàn)差異明顯，其中SLPA表現(xiàn)最差，而OCPLP的表現(xiàn)明顯優(yōu)于其他兩種比較算法.在LFR1、LFR2、LFR3人工數(shù)據(jù)集上的平均精確率，OCPLP分別比SLPA和SpeakEasy 提高了83%和42%，而平均召回率則分別提高了55%和22%，F(xiàn)1度量分別提高了84%和40%.可以看出，OCPLP算法在這3個指標上全面優(yōu)于SpeakEasy算法，而SpeakEasy算法又明顯強于SLPA算法.

表3 重疊節(jié)點識別的對比結(jié)果

3.2 公開標準測試集對比

本文選擇pol.books[19]、arxiv廣義相對論學(xué)者合作網(wǎng)絡(luò)(general relativity and quantum cosmology collaboration network)[20]和netscience[19]3個較為流行的公開數(shù)據(jù)集進行對比實驗.

pol.books是基于亞馬遜網(wǎng)站的美國政治類型書籍購買信息而構(gòu)造的網(wǎng)絡(luò)，有105個節(jié)點，441條邊；arxiv廣義相對論學(xué)者合作網(wǎng)絡(luò)包括5 242 個節(jié)點和28 980條邊；netscience是復(fù)雜網(wǎng)絡(luò)學(xué)者合作網(wǎng)絡(luò)，由1 461個節(jié)點和2 742條邊構(gòu)成.在3.1節(jié)的實驗中可以看出SpeakEasy算法明顯優(yōu)于SLPA算法，所以在后面的實驗部分只選擇SpeakEasy算法與OCPLP算法進行對比.

(a) pol.books

(b) arxiv廣義相對論學(xué)者合作網(wǎng)絡(luò)

(c) netscience

圖2 典型網(wǎng)絡(luò)數(shù)據(jù)集的對比結(jié)果

Fig.2 Comparison results on the classical network datasets

圖2給出了OCPLP算法和SpeakEasy算法在3個數(shù)據(jù)集上的對比結(jié)果.從圖中可以看出，在3個真實數(shù)據(jù)集上OCPLP算法在不同閾值下的模塊度Q都明顯高于SpeakEasy算法.其中，在pol.books數(shù)據(jù)集上平均提高了34.53%，在arxiv廣義相對論學(xué)者合作網(wǎng)絡(luò)上平均提高了84.16%，而在netscience網(wǎng)絡(luò)上平均提高了6.30%.

3.3 大豆基因共表達網(wǎng)絡(luò)對比實驗

為了進一步驗證所提算法的有效性，本文利用大豆基因共表達網(wǎng)絡(luò)構(gòu)造了社區(qū)發(fā)現(xiàn)算法的測試算例.實驗數(shù)據(jù)源于GEO數(shù)據(jù)庫GPL4592平臺下的6組大豆銹病相關(guān)的數(shù)據(jù)(GSE7108[21]、GSE8432[22]、GSE29740[23]、GSE29741、GSE33410[24]、GSE41724).通過計算基因之間的皮爾森相關(guān)系數(shù)構(gòu)建了一個大豆基因共表達網(wǎng)絡(luò).該網(wǎng)絡(luò)包含4 169個基因，21 135條邊，每兩個基因之間的相似度作為對應(yīng)邊的權(quán)重，平均度為10，平均聚類系數(shù)為0.56.針對所構(gòu)建的大豆基因共表達網(wǎng)絡(luò)，分別采用SpeakEasy算法和OCPLP算法對該網(wǎng)絡(luò)進行社區(qū)劃分.

圖3 大豆基因共表達網(wǎng)絡(luò)對比結(jié)果

圖4 大豆基因共表達網(wǎng)絡(luò)實驗可視化效果

從圖3可以看出，OCPLP算法在不同閾值下得到的模塊度Q都較高，社區(qū)劃分結(jié)果更好.圖4給出了OCPLP算法對大豆基因共表達網(wǎng)絡(luò)進行社區(qū)劃分的可視化效果.對社區(qū)劃分結(jié)果做進一步分析有助于研究在銹病環(huán)境下大豆的基因共表達現(xiàn)象，并為大豆育種提供幫助.

4 結(jié) 語

針對重疊節(jié)點社區(qū)發(fā)現(xiàn)問題，本文通過設(shè)計新的重疊社區(qū)發(fā)現(xiàn)算法，增加社區(qū)合并過程，提出了OCPLP算法.為驗證所提算法的有效性，分別針對LFR benchmark人工數(shù)據(jù)集、3個典型標準數(shù)據(jù)集以及實際的大豆基因共表達網(wǎng)絡(luò)設(shè)計了3個實驗，將本文提出的算法與現(xiàn)有算法進行了對比.實驗結(jié)果表明，本文提出的OCPLP算法性能明顯優(yōu)于對比算法，并極大改善了重疊節(jié)點比重過大的問題，使得結(jié)果更加符合問題的實際特征，也驗證了OCPLP算法的有效性.