楊貴，徐乾

（山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006）

0 引言

復(fù)雜系統(tǒng)中個體間通過相互作用形成功能模塊，因此通常將現(xiàn)實(shí)中的復(fù)雜系統(tǒng)抽象為復(fù)雜網(wǎng)絡(luò)，節(jié)點(diǎn)表示系統(tǒng)個體，邊表示個體間的相互作用［1］。個體間相互作用所形成的功能模塊對應(yīng)復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，社區(qū)內(nèi)節(jié)點(diǎn)間通常存在特殊的連接模式，利用這些特殊連接模式進(jìn)行社區(qū)結(jié)構(gòu)發(fā)現(xiàn)是目前的研究熱點(diǎn)之一。大量社區(qū)發(fā)現(xiàn)算法已被廣泛應(yīng)用到商品推薦、社會關(guān)系分析、疾病網(wǎng)絡(luò)分析等諸多領(lǐng)域［1-3］。

早期的社區(qū)發(fā)現(xiàn)算法側(cè)重于進(jìn)行非重疊社區(qū)發(fā)現(xiàn)，即任意兩個聚類間不存在公共節(jié)點(diǎn)。實(shí)際上，重疊社區(qū)在真實(shí)網(wǎng)絡(luò)社區(qū)分布中普遍存在，如在線社交網(wǎng)絡(luò)不同社交群體間可能存在相同的用戶［4］、科研協(xié)作網(wǎng)絡(luò)中的不同研究群體可能存在交叉合作的科學(xué)家［5］、復(fù)雜生物網(wǎng)絡(luò)中的不同生物過程可能包含相同的生物要素［6］。重疊社區(qū)發(fā)現(xiàn)算法根據(jù)網(wǎng)絡(luò)中社區(qū)內(nèi)節(jié)點(diǎn)間特殊的拓?fù)溥B接模式對其中的復(fù)雜社區(qū)歸屬關(guān)系進(jìn)行解析。

2005 年 Palla等［7］提出了派系過濾算法CPM，將k-團(tuán)作為構(gòu)成社區(qū)的主要連接模式進(jìn)行重疊社區(qū)發(fā)現(xiàn)。k-團(tuán)是網(wǎng)絡(luò)中包含k個節(jié)點(diǎn)的完全子圖，以稠密子圖作為社區(qū)典型連接模式，可發(fā)現(xiàn)內(nèi)部連邊非常稠密的社區(qū)結(jié)構(gòu)。除k-團(tuán)外，現(xiàn)有工作也提出了極大團(tuán)、準(zhǔn)團(tuán)等多種稠密子圖的定義方式［8］?；诔砻苓B接模式的社區(qū)檢測算法通常假設(shè)社區(qū)內(nèi)部節(jié)點(diǎn)間存在大量連接，這種假設(shè)不利于發(fā)現(xiàn)實(shí)際網(wǎng)絡(luò)中普遍存在的內(nèi)部連接不夠稠密的社區(qū)。此外，由于不同網(wǎng)絡(luò)連接密度差異較大，度量這些網(wǎng)絡(luò)中子結(jié)構(gòu)的連接稠密程度耗時較多，無法通過遍歷大規(guī)模網(wǎng)絡(luò)中的子結(jié)構(gòu)發(fā)現(xiàn)其中的社區(qū)。

基于信息傳播機(jī)制的重疊社區(qū)發(fā)現(xiàn)COPRA算法［9］假設(shè)社區(qū)內(nèi)節(jié)點(diǎn)間更容易進(jìn)行信息傳播，因此其基于信息傳播影響力最大化原理，根據(jù)鄰域社區(qū)標(biāo)簽信息迭代更新節(jié)點(diǎn)的社區(qū)歸屬。由于僅考慮直接鄰居對社區(qū)標(biāo)簽的影響，COPRA算法可能會產(chǎn)生較多規(guī)模偏小的社區(qū)。已有工作對其進(jìn)行改進(jìn)，包括基于歷史標(biāo)簽信息傳播算法SLPA［10］，基于局部結(jié)構(gòu)的標(biāo)簽傳播算法DEMON［11］等。該類算法基于信息在網(wǎng)絡(luò)上的傳播模式進(jìn)行社區(qū)發(fā)現(xiàn)，節(jié)點(diǎn)更新順序和標(biāo)簽更新過程存在較大的隨機(jī)性，因此發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)通常不穩(wěn)定；且社區(qū)發(fā)現(xiàn)結(jié)果與網(wǎng)絡(luò)中影響力大的節(jié)點(diǎn)關(guān)系密切，這些影響力大的節(jié)點(diǎn)對應(yīng)于網(wǎng)絡(luò)中存在較多連接的節(jié)點(diǎn)。這類算法往往將這些節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)分配到一個巨大社區(qū)中［12］。

基于局部核心擴(kuò)展策略的重疊社區(qū)發(fā)現(xiàn)算法對網(wǎng)絡(luò)中局部拓?fù)浣Y(jié)構(gòu)的連接特征進(jìn)行解析，首先確定社區(qū)代表性強(qiáng)的節(jié)點(diǎn)作為社區(qū)核心，設(shè)計(jì)合理的核函數(shù)計(jì)算網(wǎng)絡(luò)其他部分與社區(qū)核心的相似性，選取相似性高的子結(jié)構(gòu)對社區(qū)核心進(jìn)行擴(kuò)展，以發(fā)現(xiàn)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)。該類算法的關(guān)鍵在于社區(qū)核心選取及核函數(shù)定義。早期的核心擴(kuò)展策略通常為每個可能的社區(qū)選擇單個節(jié)點(diǎn)作為社區(qū)核心進(jìn)行擴(kuò)展，也稱為“種子擴(kuò)展”策略。算法LFM［13］在網(wǎng)絡(luò)中無社區(qū)歸屬的節(jié)點(diǎn)中采用隨機(jī)方式選取種子節(jié)點(diǎn)，隨著網(wǎng)絡(luò)規(guī)模的增大，種子選取過程中的隨機(jī)性更容易導(dǎo)致不穩(wěn)定的社區(qū)發(fā)現(xiàn)結(jié)果。重疊節(jié)點(diǎn)一旦被選為種子節(jié)點(diǎn)，算法傾向于將兩個重疊社區(qū)識別為一個社區(qū)。算法CFCD［14］選擇k核中心性高的節(jié)點(diǎn)作為種子，算法LOCD［15］假設(shè)不同社區(qū)的種子節(jié)點(diǎn)具有較高的連接度且不同社區(qū)的種子節(jié)點(diǎn)相距較遠(yuǎn)。算法GCE［16］選取網(wǎng)絡(luò)中k-團(tuán)作為初始種子進(jìn)行擴(kuò)展，在一定程度上提高了算法穩(wěn)定性。算法LFM和GCE對比社區(qū)內(nèi)外連邊比例評價一個社區(qū)的顯著性，選擇可增大社區(qū)內(nèi)外連邊差異的節(jié)點(diǎn)擴(kuò)展初始社區(qū)；算法LOCD選擇可增大社區(qū)內(nèi)部節(jié)點(diǎn)間Salton相似性的節(jié)點(diǎn)擴(kuò)展社區(qū)；算法CFCD選擇可增加社區(qū)內(nèi)節(jié)點(diǎn)的k核中心性的節(jié)點(diǎn)擴(kuò)展社區(qū)。這些社區(qū)擴(kuò)展方式所定義的社區(qū)適應(yīng)度函數(shù)可發(fā)現(xiàn)網(wǎng)絡(luò)中內(nèi)部連接相對稠密的社區(qū)結(jié)構(gòu)，但對大規(guī)模網(wǎng)絡(luò)中內(nèi)部結(jié)構(gòu)差異較大的不同社區(qū)結(jié)構(gòu)識別效率不高。

個性化PageRank的社區(qū)擴(kuò)展算法NISE［17］對采用導(dǎo)電性對種子節(jié)點(diǎn)鄰域的信息傳遞能力進(jìn)行度量，發(fā)現(xiàn)社區(qū)間信息傳播最小化的社區(qū)結(jié)構(gòu)。算法Node_Perception［15］在各節(jié)點(diǎn)局部鄰域子圖內(nèi)利用標(biāo)簽傳播算法發(fā)現(xiàn)局部社區(qū)結(jié)構(gòu)，將連邊較多的局部社區(qū)合并最終社區(qū)發(fā)現(xiàn)結(jié)果。以上方法在種子節(jié)點(diǎn)選擇及擴(kuò)展過程中考慮的節(jié)點(diǎn)鄰域的連接模式，通過合理的社區(qū)擴(kuò)展過程更好地檢測重疊社區(qū)。

然而，網(wǎng)絡(luò)中往往存在一些特定的模體來行使特定功能，這些模體表現(xiàn)為節(jié)點(diǎn)子集內(nèi)特定的連接模式。模體結(jié)構(gòu)體現(xiàn)了網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)間連接的高階特征，一個社區(qū)內(nèi)往往存在一種或少數(shù)幾種典型的模體結(jié)構(gòu)。利用模體信息對網(wǎng)絡(luò)功能模塊進(jìn)行分析和挖掘有助于深入理解網(wǎng)絡(luò)功能和演化機(jī)制。本文提出了一種基于局部模體相似性的重疊社區(qū)發(fā)現(xiàn)算法SLMD，首先統(tǒng)計(jì)網(wǎng)絡(luò)中3-模體和4-模體的分布信息，基于k-WL核計(jì)算基于局部模體信息的節(jié)點(diǎn)中心性，發(fā)現(xiàn)網(wǎng)絡(luò)中模體相對集中的一些局部拓?fù)浣Y(jié)構(gòu)作為初始社區(qū)種子；根據(jù)鄰域結(jié)構(gòu)內(nèi)模體分布的一致性定義了子結(jié)構(gòu)間的相似性，選擇相似性較高的子結(jié)構(gòu)對初始社區(qū)進(jìn)行擴(kuò)展；最后，合并重疊度較大的社區(qū)得到最終社區(qū)發(fā)現(xiàn)結(jié)果。

基于網(wǎng)絡(luò)局部模體分布的高階信息可以選擇相對穩(wěn)定的社區(qū)核心，因此所提算法SLMD具有良好的穩(wěn)定性；基于模體分布一致性進(jìn)行社區(qū)擴(kuò)展，算法可以發(fā)現(xiàn)網(wǎng)絡(luò)中內(nèi)部連接差異較大的社區(qū)結(jié)構(gòu)。在7個有真實(shí)社區(qū)標(biāo)簽、4個無標(biāo)簽的網(wǎng)絡(luò)上的對比實(shí)驗(yàn)表明了所提算法的有效性。

1 背景知識

1.1 基本概念與術(shù)語

給定一個包含n個節(jié)點(diǎn)的圖G=（V，E），其 中 節(jié) 點(diǎn) 集 V={v1，v2，…，vn}，邊 集 E={(vi，vj)|1≤ i≠ j≤ n}。令 A∈ Rn×n為圖 G 的相鄰矩陣。若邊(vi，vj)∈E，則Aij=1，稱u和v互為相鄰節(jié)點(diǎn)。令 Nv={u|(u，v)∈E∧u∈V}表示節(jié)點(diǎn)v的相鄰節(jié)點(diǎn)集合，也稱v的直接鄰域。記節(jié)點(diǎn)vi的度di=|Nvi|，也可以記作di=。對圖G'=(V'，E')，若V'?V，E'?E，則G'是G的一個子圖，記作G'?G。若V'?V且邊E'={(vi，vj)|vi，vj∈ V'∧(vi，vj)∈ E}，則 稱 子 圖 G'是圖G的導(dǎo)出子圖，記為G[V']，簡記為[V']。頂點(diǎn)子集S(?V)的體積為Vol(S)=∑v∈Sdv，表示S中所有節(jié)點(diǎn)的度數(shù)和。

對兩個圖 G1=(V1，E1)與 G2=(V2，E2)，如果存在雙射函數(shù)f：V1→V2，且對于V1中的任意 兩 個 頂 點(diǎn) u 和 v，若 (u，v)∈E1當(dāng) 且 僅 當(dāng)(f(u)，f(v))∈ E2，則圖 G1和 G2是同構(gòu)的，記作G1?G2。設(shè)頂點(diǎn)子集S(?V)的導(dǎo)出子圖為［S］，若圖G中與［S］同構(gòu)的子圖出現(xiàn)頻率遠(yuǎn)高于在隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的頻率，則［S］稱作圖G的一種模體。模體是網(wǎng)絡(luò)中一些具有特定結(jié)構(gòu)的小規(guī)模子圖，刻畫了網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)間連接存在的特定模式。

復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)通過連接形成不同的團(tuán)簇行使特定的功能，這些團(tuán)簇也稱為社區(qū)，分析網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)分析的重要任務(wù)之一。對一個圖G和它的k個若干節(jié)點(diǎn)子集，滿足V=C1∪C2…∪Ck，則稱 Ω={C1，C2，…，Ck}是 G的一種社區(qū)結(jié)構(gòu)，k為社區(qū)個數(shù)。若對任意的1≤i，j≤k，有 Ci∩Cj=?，則 稱 Ω 是 非 重 疊的；否則Ω為一種重疊社區(qū)結(jié)構(gòu)［18］。

節(jié)點(diǎn)間連接稠密是社區(qū)結(jié)構(gòu)內(nèi)最常見的連接特征之一，在已有社區(qū)發(fā)現(xiàn)算法中被廣泛使用。然而，除連接相對稠密之外，社區(qū)內(nèi)節(jié)點(diǎn)間往往還存在一些特殊的連接模式而形成特定類型的模體。發(fā)現(xiàn)網(wǎng)絡(luò)中具有統(tǒng)計(jì)意義的模體信息，并有效利用模體與網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的關(guān)聯(lián)關(guān)系，可以發(fā)現(xiàn)網(wǎng)絡(luò)中連接模式差異較大的社區(qū)結(jié)構(gòu)。

1.2 基于種子擴(kuò)展策略的社區(qū)發(fā)現(xiàn)算法

早期的社區(qū)發(fā)現(xiàn)算法往往需要網(wǎng)絡(luò)的全局結(jié)構(gòu)信息，因此當(dāng)網(wǎng)絡(luò)規(guī)模急劇增大時，遍歷網(wǎng)絡(luò)全局結(jié)構(gòu)的計(jì)算代價過高。而“種子擴(kuò)展”策略在社區(qū)發(fā)現(xiàn)過程中不需要對網(wǎng)絡(luò)全局結(jié)構(gòu)進(jìn)行遍歷，僅需分析節(jié)點(diǎn)或子結(jié)構(gòu)的局部鄰域內(nèi)的拓?fù)涮卣?，因此，基于種子擴(kuò)展策略的局部社區(qū)發(fā)現(xiàn)算法可以更有效發(fā)現(xiàn)大規(guī)模網(wǎng)絡(luò)或未知全局信息的動態(tài)網(wǎng)絡(luò)中的社區(qū)。其中一個關(guān)鍵點(diǎn)是確定候選社區(qū)的初始種子，早期的基于種子擴(kuò)展策略的社區(qū)發(fā)現(xiàn)算法過程通常首先選擇一個中心性較高的節(jié)點(diǎn)作為社區(qū)種子，再根據(jù)一定的相似性度量方法計(jì)算其他節(jié)點(diǎn)與社區(qū)種子的距離或相似性，選擇與種子較近（或相似性較高）的節(jié)點(diǎn)對社區(qū)種子進(jìn)行擴(kuò)展，最后對未聚類節(jié)點(diǎn)或聚類模糊的節(jié)點(diǎn)進(jìn)行后處理。

在網(wǎng)絡(luò)規(guī)模較小，且社區(qū)內(nèi)部連接稠密的情況下，選擇單個節(jié)點(diǎn)作為社區(qū)種子在實(shí)際應(yīng)用中取得了比較好的效果。然而，當(dāng)社區(qū)中無中心節(jié)點(diǎn)時，無法找到合適社區(qū)種子進(jìn)行擴(kuò)展，則應(yīng)根據(jù)社區(qū)內(nèi)節(jié)點(diǎn)間特定的連接模式進(jìn)行社區(qū)發(fā)現(xiàn)。GCE算法利用社區(qū)中稠密連接所形成的團(tuán)派連接模式進(jìn)行社區(qū)發(fā)現(xiàn)，但不易發(fā)現(xiàn)內(nèi)部不存在完全連接的社區(qū)結(jié)構(gòu)。ATCO算法利用社區(qū)內(nèi)三角形連接情況發(fā)現(xiàn)社區(qū)［19］。

團(tuán)派和三角形在一定程度上刻畫了社區(qū)內(nèi)節(jié)點(diǎn)間特殊的連接模式，然而不同網(wǎng)絡(luò)內(nèi)有統(tǒng)計(jì)意義的模體各不相同，即使同一網(wǎng)絡(luò)中的不同社區(qū)內(nèi)可能也存在不同的模體。如何有效利用網(wǎng)絡(luò)中的模體信息及模體結(jié)構(gòu)間的連接方式進(jìn)行社區(qū)發(fā)現(xiàn)是本文的重點(diǎn)研究問題。

2 基于局部模體分布相似性的節(jié)點(diǎn)中心性度量

本節(jié)利用網(wǎng)絡(luò)中的模體信息及模體結(jié)構(gòu)間的連接方式進(jìn)行社區(qū)發(fā)現(xiàn)，首先給出網(wǎng)絡(luò)模體相鄰矩陣，統(tǒng)計(jì)網(wǎng)絡(luò)中節(jié)點(diǎn)鄰域結(jié)構(gòu)內(nèi)的模體及模體間連接關(guān)系；基于模體分布計(jì)算節(jié)點(diǎn)間的局部鄰域結(jié)構(gòu)的相似性，并給出了基于模體分布的節(jié)點(diǎn)中心性度量指標(biāo)。

2.1 節(jié)點(diǎn)k鄰域模體分布熵

對v∈V(G)，定義Ht(v)表示由其t步閉鄰域內(nèi)所有節(jié)點(diǎn)導(dǎo)出的子圖，即Ht(v)=[Nt(v)∪{v}]。本節(jié)利用鄰域內(nèi)包含3個節(jié)點(diǎn)和4個節(jié)點(diǎn)的連通模體度量節(jié)點(diǎn)鄰域模體分布的相似性。節(jié)點(diǎn)個數(shù)為3或4的連通模體共有8種，如圖1所示。k-模體分布Γk：V→R|T|為節(jié)點(diǎn)集到|T|維歐氏空間的映射，其中T為模體集合，表示節(jié)點(diǎn)的k步鄰域內(nèi)模體分布情況。對節(jié)點(diǎn)v∈V(G)，，其 中 γi(v)表示節(jié)點(diǎn)v的k步鄰域內(nèi)模體Ti的出現(xiàn)次數(shù)，本文僅考慮圖1所示的8種連通的3-模體和4-模體。

圖1 連通的3-模體和4-模體Fig.1 Connected 3-motifs and 4-motifs

計(jì)算模體分布Γk(v)的香農(nóng)熵來度量節(jié)點(diǎn)的第k步鄰域內(nèi)模體分布的分散程度，稱節(jié)點(diǎn)v的模體分布熵，如公式（1）所示。

由于度數(shù)較低的節(jié)點(diǎn)周圍通常模體較少，可能出現(xiàn)其模體分布向量為0，或某些分量為0的情形。因此在公式（1）中規(guī)定，若Γk(v)為0向 量 ，則 規(guī) 定 其 Sk(v)=0；若 Γk(v)的 分 量，則令。節(jié)點(diǎn)度數(shù)大且模體分布熵越高，說明節(jié)點(diǎn)v局部鄰域內(nèi)的模體分布越豐富，可能位于社區(qū)中心或者處于社區(qū)的重疊部分；否則，若節(jié)點(diǎn)度數(shù)低或模體分布熵偏低，說明節(jié)點(diǎn)v的局部鄰域內(nèi)模體結(jié)構(gòu)比較單一，成為社區(qū)中心的可能性較低。

2.2 基于k-WL核的節(jié)點(diǎn)特征序列生成

Weisfeiler-Lehman（WL）方法是 Boris等提出的圖同構(gòu)檢測方法，將節(jié)點(diǎn)的特征信息和結(jié)構(gòu)信息映射相結(jié)合，對節(jié)點(diǎn)進(jìn)行重標(biāo)簽，在同一同構(gòu)軌道的節(jié)點(diǎn)被賦予相同標(biāo)簽。本文基于節(jié)點(diǎn)v鄰域內(nèi)的3-模體和4-模體分布情況，采用WL核方法對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行重標(biāo)簽，生成節(jié)點(diǎn)特征序列。算法1給出了基于k-WL核的節(jié)點(diǎn)特征序列生成方法。

2.3 基于模體分布的社區(qū)適應(yīng)度

社區(qū)內(nèi)節(jié)點(diǎn)間連邊相對社區(qū)間較多，社區(qū)結(jié)構(gòu)的顯著性通常利用社區(qū)內(nèi)節(jié)點(diǎn)間的連接稠密程度來衡量，但這無法體現(xiàn)模體結(jié)構(gòu)對社區(qū)的影響。社區(qū)內(nèi)的連邊往往會形成一些特殊的連接模式以行使特定社區(qū)功能，社區(qū)內(nèi)存在某種模體的出現(xiàn)頻率會高于隨機(jī)連接情況。基于此，用社區(qū)內(nèi)某種模體的顯著性定義社區(qū)適應(yīng)度，如公式（2）所示。

其中，Nt表示C中模體t的出現(xiàn)次數(shù)，和σt分別表示與C具有相同節(jié)點(diǎn)數(shù)和邊數(shù)的隨機(jī)零模型中模體t的出現(xiàn)次數(shù)和方差。

3 基于局部模體分布相似性的社區(qū)發(fā)現(xiàn)算法

基于以上提出的基于鄰域模體分布的度量指標(biāo)及節(jié)點(diǎn)特征表示，本節(jié)給出基于局部模體分布相似性的重疊社區(qū)發(fā)現(xiàn)算法（overlapping community detection method according to Similarity of Local Motifs Distribution，SLMD），算法基于中心擴(kuò)展策略進(jìn)行社區(qū)發(fā)現(xiàn)，首先根據(jù)模體分布情況確定初始社區(qū)核心，再利用模體分布相似性的對初始社區(qū)核心進(jìn)行擴(kuò)展，最終將存在較多連邊的社區(qū)進(jìn)行合并。

3.1 初始社區(qū)核心確定

對圖G=（V，E）中的每個頂點(diǎn)v，首先計(jì)算節(jié)點(diǎn)v的k步鄰域內(nèi)各類3-模體和4-模體的出現(xiàn)頻次，再根據(jù)公式（1）計(jì)算節(jié)點(diǎn)v的k步鄰域內(nèi)模體分布熵。一個節(jié)點(diǎn)度越大且模體分布熵越高，成為社區(qū)中心的可能性也偏大。因此本節(jié)結(jié)合節(jié)點(diǎn)度與模體分布熵定義節(jié)點(diǎn)的社區(qū)中心性，如公式（3）所示。

將G中節(jié)點(diǎn)按照中心性非遞增排列，假設(shè)排序后結(jié)點(diǎn)編號為 V={v1，v2，…，vn}。 對于1≤i＜j≤ n，有 DSk(vi)≥ DSk(vj)。選擇中心性高于平均值的節(jié)點(diǎn)作為初始社區(qū)中心節(jié)點(diǎn)集，其中為圖G中節(jié)點(diǎn)中心性平均值。首先獲取中心性高于平均值的節(jié)點(diǎn)集導(dǎo)出子圖的連通分支，每個連通分支作為一個社區(qū)的初始中心節(jié)點(diǎn)集。將連通分支作為初始中心節(jié)點(diǎn)集，可以避免兩個不同社區(qū)中心節(jié)點(diǎn)相鄰而導(dǎo)致的過大社區(qū)，同時，可以無需用戶預(yù)先確定社區(qū)個數(shù)，導(dǎo)出子圖的連通分支個數(shù)即為社區(qū)個數(shù)。初始社區(qū)中心節(jié)點(diǎn)選擇過程如算法2所示。

3.2 社區(qū)擴(kuò)展階段

在社區(qū)擴(kuò)展階段，利用第2.2節(jié)定義的基于k-WL的節(jié)點(diǎn)特征分布序列，比較當(dāng)前節(jié)點(diǎn)與初始社區(qū)中心節(jié)點(diǎn)間的距離，將其分配至距離最近的社區(qū)。由于每個社區(qū)可能有多個初始中心節(jié)點(diǎn)，因此用節(jié)點(diǎn)與社區(qū)中心節(jié)點(diǎn)集的平均距離作為社區(qū)分配的依據(jù)。采用相對熵計(jì)算節(jié)點(diǎn)u和v間節(jié)點(diǎn)特征分布的相似性，如公式（4）所示。

為確保兩點(diǎn)間相似性計(jì)算的對稱性，本文采用公式（5）計(jì)算節(jié)點(diǎn)間相似性。

初始中心節(jié)點(diǎn)集擴(kuò)展為社區(qū)的過程如算法3所示。

3.3 合并重疊度高的社區(qū)

采用以上步驟進(jìn)行重疊社區(qū)發(fā)現(xiàn)，通常會產(chǎn)生很多重疊度較大的社區(qū)，導(dǎo)致發(fā)現(xiàn)過多社區(qū)。因此，算法最終將所發(fā)現(xiàn)社區(qū)的構(gòu)成進(jìn)行比較，若兩個社區(qū)間的公共節(jié)點(diǎn)比例高于設(shè)定閾值，則將這兩個社區(qū)進(jìn)行合并。合并重疊度較高的社區(qū)可以更準(zhǔn)確的識別網(wǎng)絡(luò)中重疊社區(qū)。兩個社區(qū)重疊度的計(jì)算如公式（6）所示，其中 CC={C1，…，Ck}為圖 G 的一種社區(qū)發(fā)現(xiàn)結(jié)果，Ci和Cj為其中兩個不同社區(qū)。

本文中合并重疊度大于0.8的社區(qū)。

4 實(shí)驗(yàn)結(jié)果

為驗(yàn)證所提算法性能，本節(jié)將在7個帶標(biāo)簽網(wǎng)絡(luò)和4個無標(biāo)簽網(wǎng)絡(luò)上，將本文算法SLMD與6個經(jīng)典重疊社區(qū)發(fā)現(xiàn)算法SLPA［10］、DEMON［11］、CPM［7］、節(jié) 點(diǎn) 感 知 算 法（Node_Perception）［20］、Ego_Networks［21］、Ego_Splitter［21］進(jìn)行比較實(shí)驗(yàn)。表1給出了實(shí)驗(yàn)數(shù)據(jù)集的基本信息。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息Table 1 Information of experimental datasets

4.1 評價指標(biāo)

對帶標(biāo)簽網(wǎng)絡(luò)，本節(jié)首先采用由McDaid等［22］提出的重疊標(biāo)準(zhǔn)互信息ONMI指標(biāo)對算法性能進(jìn)行比較。假設(shè) Ω ={C1，C2，…，Cm}和O={O1，O2，…，Om'}分別表示兩種不同的社區(qū)結(jié)構(gòu)，重疊標(biāo)準(zhǔn)互信息通過比較兩種社區(qū)結(jié)構(gòu)中各社區(qū)的重疊程度來衡量其一致性。此外，本節(jié)還采用Rossetti等［23］提出的F1分?jǐn)?shù)對無標(biāo)簽網(wǎng)絡(luò)進(jìn)行算法性能比較。ONMI和F1分?jǐn)?shù)的取值范圍都是［0，1］，符合網(wǎng)絡(luò)真實(shí)社區(qū)劃分結(jié)果的ONMI值和F1分?jǐn)?shù)更接近1。

采用文獻(xiàn)［24］提出的擴(kuò)展模塊度EQ對無標(biāo)簽網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)質(zhì)量進(jìn)行評價，如公式（7）所示：

其中，v和w代表網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)；m代表社區(qū)個數(shù)；Ov表示在所發(fā)現(xiàn)包含節(jié)點(diǎn)v的社區(qū)數(shù)；若節(jié)點(diǎn)v和w間存在邊，則avw=1，否則avw=0。所發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)越顯著，對應(yīng)的擴(kuò)展模塊度值EQ越接近1。

4.2 帶標(biāo)簽網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)比較結(jié)果

表 2 和表 3 分別給出了在 Karate［25］、Dolphin［26］、Football［27］、Polbooks［28］、Cora、Citeceer、DBLP等7個帶標(biāo)簽網(wǎng)絡(luò)上所發(fā)現(xiàn)社區(qū)的對比實(shí)驗(yàn)結(jié)果?？梢钥闯?，本文算法SLMD在ONMI和F1分?jǐn)?shù)方面明顯優(yōu)于對比算法，傳統(tǒng)的重疊社區(qū)發(fā)現(xiàn)算法通常發(fā)現(xiàn)了大量的重疊社區(qū)，導(dǎo)致其與真實(shí)社區(qū)結(jié)構(gòu)相比，ONMI和F1分?jǐn)?shù)性能較低。由于本文算法SLMD在社區(qū)擴(kuò)展過程和合并過程，可以將重疊度較高的社區(qū)進(jìn)行合并，避免產(chǎn)生大量重疊度高的社區(qū)，因此在這些網(wǎng)絡(luò)上表現(xiàn)良好。

表2 帶標(biāo)簽網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)的ONMI比較實(shí)驗(yàn)結(jié)果Table 2 Comparative results of detected communities at ONMI on labeled networks

表3 帶標(biāo)簽網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)的F1分?jǐn)?shù)比較實(shí)驗(yàn)結(jié)果Table 3 Comparative results of detected communities at F1Score on labeled networks

4.3 無標(biāo)簽網(wǎng)絡(luò)的實(shí)驗(yàn)比較結(jié)果

表 4 給出了在 NetScience、Email［29］、Usair、Power等4個無標(biāo)簽網(wǎng)絡(luò)上的對比實(shí)驗(yàn)結(jié)果?？梢钥闯觯跓o標(biāo)簽網(wǎng)絡(luò)上，所提算法SLMD發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)比較穩(wěn)定具有較好的重疊模塊度。與SLPA算法相比，由于標(biāo)簽傳播機(jī)制中的隨機(jī)性較大，導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定。而本文算法利用節(jié)點(diǎn)間連接所形成的特殊模體，選擇模體相對集中的一些局部拓?fù)浣Y(jié)構(gòu)作為社區(qū)核心，并利用模體分布對社區(qū)結(jié)構(gòu)進(jìn)行評價，這可使算法得到比較穩(wěn)定的社區(qū)結(jié)構(gòu)且具有較高的模塊度。

表4 無標(biāo)簽網(wǎng)絡(luò)上各算法的擴(kuò)展模塊度（EQ）比較Table 4 Comparisons on unlabeled networks on EQ

5 結(jié)論

本文基于社區(qū)節(jié)點(diǎn)間特殊的連接模式信息，提出了一種基于局部模體分布相似性的重疊社區(qū)發(fā)現(xiàn)算法SLMD，首先統(tǒng)計(jì)網(wǎng)絡(luò)中3-模體和4-模體的分布信息，基于k-WL核計(jì)算基于局部模體信息的節(jié)點(diǎn)中心性，發(fā)現(xiàn)網(wǎng)絡(luò)中模體相對集中的一些局部拓?fù)浣Y(jié)構(gòu)作為初始社區(qū)種子；根據(jù)鄰域結(jié)構(gòu)內(nèi)模體分布的一致性定義了子結(jié)構(gòu)間的相似性，將相似性較高的子結(jié)構(gòu)對初始社區(qū)進(jìn)行擴(kuò)展；最后，計(jì)算所得社區(qū)間的重疊度，得到重疊度不超過0.8的社區(qū)作為最終社區(qū)發(fā)現(xiàn)結(jié)果。在11個網(wǎng)絡(luò)上將所提算法SLMD與6個經(jīng)典算法的比較實(shí)驗(yàn)表明，所提算法SLMD在帶標(biāo)簽網(wǎng)絡(luò)上具有較好的重疊NMI和F1分?jǐn)?shù)，在無標(biāo)簽網(wǎng)絡(luò)上算法SLMD在重疊模塊度上有明顯優(yōu)勢，可發(fā)現(xiàn)具有特定連接模式的社區(qū)結(jié)構(gòu)。