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

吳 春 國(guó)， 李 艷 振， 李 瑛， 高 瑞， 時(shí) 小 虎*

(1.吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室， 吉林 長(zhǎng)春 130012；2.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 吉林 長(zhǎng)春 130012；3.吉林大學(xué)珠海學(xué)院 計(jì)算機(jī)學(xué)院， 廣東 珠海 519041 )

0 引 言

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

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

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

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

1 SpeakEasy算法簡(jiǎn)介

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

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

(1)

當(dāng)Wv C大于給定閾值γ時(shí)，認(rèn)定v為C的重疊節(jié)點(diǎn).

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

2 OCPLP算法

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

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

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

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

(2)標(biāo)簽傳播

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

(2)

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

(3)

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

(4)

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

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

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

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

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

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

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

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

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

(5)

(6)

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

(5)識(shí)別重疊社區(qū)節(jié)點(diǎn)

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

(7)

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

OCPLP-識(shí)別重疊社區(qū)節(jié)點(diǎn)

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

： 最優(yōu)劃分C，圖中全部節(jié)點(diǎn)集合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ū)合并

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

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

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

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

： 最優(yōu)劃分C，圖中全部節(jié)點(diǎn)集合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í) 驗(yàn)

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

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

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

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

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

(8)

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

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

(9)

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

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

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

γr=nT/(nT+nN)

(10)

γp=nT/(nT+nP)

(11)

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

(12)

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

表3給出了在LFR1、LFR2、LFR3人工數(shù)據(jù)集上重疊節(jié)點(diǎn)識(shí)別的比較結(jié)果.由表3可以看出，在LFR1上，3種算法在3個(gè)指標(biāo)的綜合表現(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個(gè)指標(biāo)上全面優(yōu)于SpeakEasy算法，而SpeakEasy算法又明顯強(qiáng)于SLPA算法.

表3 重疊節(jié)點(diǎn)識(shí)別的對(duì)比結(jié)果

3.2 公開標(biāo)準(zhǔn)測(cè)試集對(duì)比

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

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

(a) pol.books

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

(c) netscience

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

Fig.2 Comparison results on the classical network datasets

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

3.3 大豆基因共表達(dá)網(wǎng)絡(luò)對(duì)比實(shí)驗(yàn)

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

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

圖4 大豆基因共表達(dá)網(wǎng)絡(luò)實(shí)驗(yàn)可視化效果

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

4 結(jié) 語

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