一種采用二級影響結(jié)構(gòu)相似度的動態(tài)社團更新算法

張 昕,張 瑜,姚友娟,楚善增,李曉光

(遼寧大學 信息學院,沈陽 110036) E-mail:xgli@lnu.edu.cn

1 引 言

網(wǎng)絡(luò)科學是將現(xiàn)實中的事物及其之間的關(guān)系抽象為網(wǎng)絡(luò)結(jié)構(gòu)進行研究,網(wǎng)絡(luò)模型由早期的規(guī)則網(wǎng)絡(luò)與隨機網(wǎng)絡(luò),發(fā)展到如今的復(fù)雜網(wǎng)絡(luò),其相關(guān)研究的重要性愈加突出.不同研究領(lǐng)域的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)普遍存在著小世界、無標度、社團結(jié)構(gòu)等共性,其中社團結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的一個重要特性,具有較高的理論價值和應(yīng)用前景,在萬維網(wǎng)[1,2]、生物網(wǎng)絡(luò)[3]及社會網(wǎng)絡(luò)[4-6]等領(lǐng)域得到廣泛應(yīng)用.

現(xiàn)有的社團結(jié)構(gòu)算法主要分為兩類:一類是計算機科學中的圖形分割算法;另一類是社會學中的分級聚類算法.圖形分割算法主要包括派系過濾算法[7]、譜平分法[8]、Kernighan-Lin算法[9],該類算法要求事先確定劃分社團的數(shù)量,而在現(xiàn)實網(wǎng)絡(luò)中社團的數(shù)量通常是未知的.分級聚類算法又可以分為兩類:分裂算法和凝聚算法,具有代表性的算法有GN算法[10]、Newman快速算法[11]等.該類算法的復(fù)雜度高,只適用于規(guī)模較小的網(wǎng)絡(luò).

目前研究成果多數(shù)是面向靜態(tài)復(fù)雜網(wǎng)絡(luò)上的社團劃分,而現(xiàn)實網(wǎng)絡(luò)普遍具有動態(tài)演變的特征,因此針對動態(tài)復(fù)雜網(wǎng)絡(luò)上社團發(fā)現(xiàn)的相關(guān)研究得到越來越多的關(guān)注.但由于其起步較晚,相關(guān)研究成果較少,且時間效率及社團劃分質(zhì)量有待提高.

現(xiàn)有動態(tài)社團劃分算法大體上可分為三類:基于傳統(tǒng)靜態(tài)思想的算法、基于進化思想的算法以及基于增量思想的算法.基于傳統(tǒng)靜態(tài)思想的算法是把靜態(tài)算法直接運用到動態(tài)網(wǎng)絡(luò)上,即對于每時刻的網(wǎng)絡(luò)快照,進行一次新的全局社團劃分,其時間復(fù)雜度過高,Scan算法[12]是其中具有代表性的算法.基于進化思想的算法中具有代表性的是Lin等人提出的FacetNet算法[13],該算法綜合考慮當前快照與上一時刻的劃分結(jié)果,通過代價函數(shù)平衡二者的開銷,與基于傳統(tǒng)靜態(tài)思想的算法類似,需要頻繁進行全局社團劃分,時間效率較低.而基于增量思想的算法僅在網(wǎng)絡(luò)變化時考察變化相關(guān)部分,其時間效率較好,如單波等人提出的IC算法[14].但該算法在確定變化相關(guān)集合時,僅考慮了邊的變化對于兩端點的影響,忽略了端點鄰域的關(guān)聯(lián)影響,使得算法的準確率偏低.

由現(xiàn)有研究成果可以看出,增量式的思想更適用于動態(tài)網(wǎng)絡(luò)的社團劃分,但全局式的社團劃分算法雖然劃分質(zhì)量更高,但時間效率不滿足動態(tài)網(wǎng)絡(luò)的實時性,而時間效率較好的局部算法又缺乏足夠的準確率[15].因此,本文在增量式框架下,考察節(jié)點的二級鄰域,采用擴展的局部算法思想,提出了一種適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的動態(tài)社團劃分算法.

2 社團劃分相關(guān)定義

網(wǎng)絡(luò)可抽象為由節(jié)點集V和邊集E組成的圖G,|V|表示節(jié)點數(shù)量(記為N),|E|表示邊數(shù)量(記為M).E中每條邊都有V中一對節(jié)點與之相對應(yīng),若任意節(jié)點對(i,j)與(j,i)對應(yīng)同一條邊,則該網(wǎng)絡(luò)稱為無向網(wǎng)絡(luò),否則稱為有向網(wǎng)絡(luò).若V中每條邊都具有權(quán)值,那么稱該網(wǎng)絡(luò)為加權(quán)網(wǎng)絡(luò),否則(邊權(quán)值均為1)稱無權(quán)網(wǎng)絡(luò).本文的算法主要致力于研究無向無權(quán)網(wǎng)絡(luò).

考慮到當網(wǎng)絡(luò)中的邊產(chǎn)生變化時,不僅會影響到兩端點,同時也可能會影響兩端點鄰域內(nèi)的節(jié)點(點變化同理),本文在余弦相似度[16,17]的基礎(chǔ)上提出基于共同鄰居的二級影響結(jié)構(gòu)相似度(Secondary Influence Structure Similarity,記為SISSim,簡稱相似度).所謂二級影響,即兩節(jié)點的相似度不僅與這兩個節(jié)點的鄰域有關(guān),同時也與其共同鄰居節(jié)點的鄰域有關(guān).令Г(x)表示節(jié)點x的鄰域,則SISSim的形式化表示如式(1)所示:

(1)

式(1)中貢獻值SCon(x→i,j)=2/|Г(x)|,表示節(jié)點x對節(jié)點i、j相似度的影響,其中|Г(x)|表示節(jié)點v包含自身在內(nèi)的鄰居節(jié)點個數(shù).若節(jié)點m為節(jié)點m、n的共同鄰居,則SCon(m→m,n)=1/|Г(m)|.

式(1)體現(xiàn)了共同鄰居的貢獻值,并考慮其在二級鄰域中的影響,對于網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)的節(jié)點相似度具有更準確的體現(xiàn).在此基礎(chǔ)上,進一步提出用于靜態(tài)社團劃分及動態(tài)增量更新的相關(guān)定義.其中參數(shù)ε、μ可由用戶依網(wǎng)絡(luò)具體結(jié)構(gòu)情況進行調(diào)整,以適用于不同的應(yīng)用需求.

定義1.(直接強/弱結(jié)構(gòu)連接)設(shè)存在邊e(i,j)∈E,若SISSim(i,j)≥ε,則稱節(jié)點i、j為直接強結(jié)構(gòu)連接,表示為DSC(i,j),否則為直接弱結(jié)構(gòu)連接,表示為DWC(i,j).

定義2.(ε鄰域)所有與節(jié)點i為直接強結(jié)構(gòu)連接的節(jié)點的集合,稱為節(jié)點i的ε鄰域,表示為Гε(i).

定義3.(核節(jié)點)當|Гε(i)|≥μ時,稱節(jié)點i為核節(jié)點,表示為 IsCore(i).

對于大規(guī)模動態(tài)網(wǎng)絡(luò),全局社團發(fā)現(xiàn)算法時間效率低下,因此本文采取局部分析思路.考慮到網(wǎng)絡(luò)中相似度大的節(jié)點應(yīng)歸屬同一社團,提出連接偏好概念,具體定義如下:

定義4.(連接偏好)節(jié)點v的鄰域中與其相似度最大的節(jié)點,稱為節(jié)點v的連接偏好,記為ConPre(v).

顯然,除孤立點外,其他節(jié)點的連接偏好一定存在.若節(jié)點與多個節(jié)點的相似度相等,且為該節(jié)點的最大相似度,則該節(jié)點的連接偏好不止一個.

3 靜態(tài)局部社團劃分算法-LBS算法

LBS算法采用局部的思想,依據(jù)二級影響范圍內(nèi)的判斷決定歸屬社團.首先由節(jié)點的局部信息判斷其是否為核節(jié)點及連接偏好,進而由連接偏好形成連接偏好鏈,并根據(jù)相應(yīng)情況合并相關(guān)偏好鏈.然后發(fā)現(xiàn)不同偏好鏈核節(jié)點之間的直接強結(jié)構(gòu)連接,進一步整合多個偏好鏈,最終迭代形成社團.為便于表示及后續(xù)處理,將這種形如<核節(jié)點-直接強結(jié)構(gòu)連接-核節(jié)點>的結(jié)構(gòu)記作CDSCC(L1,L2),其中L1與L2表示兩端核節(jié)點所在偏好鏈.并在算法中以圖結(jié)構(gòu)的形式為每個社團保存關(guān)鍵連接數(shù)據(jù),其中連接偏好鏈抽象為節(jié)點,CDSCC抽象為邊,顯然每條抽象邊可能對應(yīng)不止一條原始網(wǎng)絡(luò)的邊,抽象邊中保存所有對應(yīng)的原始邊的信息.LBS算法的具體步驟如下:

算法1.LBS(G,ε,μ)

Input:圖G(V,E),參數(shù)ε、μ

Output:社團集合CS

1. for eache(i,j)∈E{

compute SISSim(i,j);}

2.for eachi∈V{

compute ConPre(i),IsCore(i);

if ( |ConPre(i)|>1 )i→PCon;} //連接偏好不唯一

3.I=任意i∈V;標記i;

k=1;新建listk;

listk→List;//List為連接偏好鏈集合

I→listk;

while (V包含未標記節(jié)點){

// 偏好不唯一時則任選其一

if ConPre(I) 不包含于listk且未標記{

ConPre(I)→listk;

標記 ConPre(I);

I= ConPre(I);}

else{

if ConPre(I)已標記

listk→ConPre(I)所在鏈;

I=任意未標記i∈V;

k++;新建listk;

I→listk;}

}

4.for each (i∈PCon)

for each (j∈ConPre(i))

合并i所在鏈與j所在鏈;

5.CS=List;//初始每個社團僅包含一個list

for each(L1∈List)

for each (L2∈List且L2!=L1)

if (存在CDSCC(L1,L2)){

L1所在社團與L2所在社團合并;

全部CDSCC(L1,L2) 保存于合并后的社團;}

6.ReturnCS;

LBS算法中步驟1與步驟2為初始化過程,包括計算每條邊端點對間的相似度、判斷節(jié)點是否為核節(jié)點以及計算其連接偏好.對于連接偏好不唯一的節(jié)點,記錄在集合PCon中.顯然步驟1的時間復(fù)雜度為O(M),步驟2的時間復(fù)雜度為O(N).

步驟3到步驟4為連接偏好鏈構(gòu)造過程.其中步驟3依據(jù)節(jié)點的連接偏好,以任意節(jié)點為起始構(gòu)造連接偏好鏈,當偏好鏈末端節(jié)點的連接偏好為鏈中節(jié)點時,當前鏈構(gòu)造完畢,并以任意未訪問節(jié)點為起始構(gòu)造新鏈,直至遍歷所有節(jié)點.當存在ConPre(i)= ConPre(j)時,合并節(jié)點i和j的連接偏好鏈.偏好鏈構(gòu)造過程中,對于連接偏好不唯一的節(jié)點,任選其連接偏好之一作為鏈節(jié)點.步驟3對每個節(jié)點標記1次,且不會重復(fù)訪問,因此時間復(fù)雜度為O(N).步驟4通過遍歷集合PCon,將同一節(jié)點的多個連接偏好所在鏈合并,其時間復(fù)雜度遠低于其他步驟,可以忽略.

步驟5進一步合并偏好鏈得到社團結(jié)構(gòu).初始每條偏好鏈為一個社團,遍歷步驟4所得偏好鏈,在不同偏好鏈核節(jié)點之間,查找直接強結(jié)構(gòu)連接,即發(fā)現(xiàn)CDSCC結(jié)構(gòu),進行社團間的合并.最終所得即為社團發(fā)現(xiàn)的結(jié)果,由步驟6返回.該步驟沿偏好鏈遍歷節(jié)點,并判斷節(jié)點是否為核節(jié)點以及核節(jié)點間是否存在直接強結(jié)構(gòu)連接,最終對每個節(jié)點標記其社團歸屬,因此時間復(fù)雜度為O(N).

以圖1所示網(wǎng)絡(luò)G為例說明算法社團劃分結(jié)果.該網(wǎng)絡(luò)由25個節(jié)點和76條連邊組成，節(jié)點依字母升序的連接偏好計算結(jié)果依次為：d、c、b、a、a、d、b、b、a、e、f、f、c、n、t、r、q、w、p、p、t、s、r、x、q.

圖1 網(wǎng)絡(luò)G的拓撲結(jié)構(gòu)Fig.1 Topology structure of G

算法輸入?yún)?shù)值分別為ε=1.25,μ=3,計算所得核節(jié)點為a、b、c、d、p、q、r、s、t.

構(gòu)造所得連接偏好鏈集為:{l,f,d,a,d}、{h,b,c,b}、{i,b,c,b}、{j,a,d,a}、{k,e,a,d,a}、{m,f,d,a,d}、{o,n,c,b,c}、{u,p,t,p}、{v,t,p,t}、{w,s,w}、{y,x,r,q,r}、{z,q,r,q}.

同一節(jié)點的多個連接偏好所在鏈進一步合并所得為:{a,d,e,f,j,k,l,m}、{b,c,h,i,n,o}、{p,t,u,v}、{q,r,x,y,z}、{s,w}.

對不同偏好鏈核節(jié)點間存在直接強結(jié)構(gòu)的情況,合并形成社團,最終該網(wǎng)絡(luò)社團劃分結(jié)果為:

{(a,d,e,f,j,k,l,m,b,c,h,i,n,o)、(p,t,u,v,q,r,x,y,z,s,w)}.

4 動態(tài)復(fù)雜網(wǎng)絡(luò)上的社團更新算法-IU-LBS算法

以靜態(tài)LBS算法為基礎(chǔ),提出適用于動態(tài)復(fù)雜網(wǎng)絡(luò)的社團發(fā)現(xiàn)算法IU-LBS算法.IU-LBS算法隨網(wǎng)絡(luò)變化更新相關(guān)節(jié)點信息,如相似度、連接偏好以及是否為核節(jié)點等,并利用LBS算法處理結(jié)果,包括連接偏好鏈構(gòu)造與社團劃分,更新偏好鏈以及鏈間關(guān)鍵連接CDSCC,進而更新社團劃分結(jié)果.

4.1 更新變化節(jié)點的屬性域

網(wǎng)絡(luò)變化的類型包括點增加、點刪除、邊增加、邊刪除.按照網(wǎng)絡(luò)變化的不同類型,記錄其影響范圍,即變化相關(guān)節(jié)點集.同時,變化相關(guān)節(jié)點的屬性值也可能會發(fā)生變化,需要對其進行更新,使其與當前的網(wǎng)絡(luò)結(jié)構(gòu)保持一致.為便于處理,設(shè)置如下3個標志位記錄節(jié)點關(guān)鍵信息的變化.

? flag 1.值為1表示核節(jié)點演變?yōu)榉呛斯?jié)點,值為2表示非核節(jié)點演變?yōu)楹斯?jié)點,值為0表示無變化.

? flag 2.二元組,第一屬性值為1表示連接由強變?nèi)?值為2表示連接由弱變強,值為0表示無變化;第二屬性表示連接邊的另一端點.

? flag 3.值為1表示連接偏好發(fā)生變化,值為0表示無變化.

若變化相關(guān)節(jié)點i對新增邊端點的相似度不小于原相似度,表示出現(xiàn)新的連接偏好,更新ConPre(i),置flag3為1;若相似度不小于閾值ε,表示節(jié)點i的ε鄰域擴充,Гε(i)增加節(jié)點,置flag 2為2;若由原|Гε(i)|<μ且邊增加后|Гε(i)|≥μ,表示節(jié)點i由非核節(jié)點演變?yōu)楹斯?jié)點,更新IsCore(i)為ture,置flag1為2.

與邊增加類似,若變化相關(guān)節(jié)點i對刪除邊端點的相似度為最大相似度,表示原連接偏好被移除,更新ConPre(i),置flag3為1;若相似度不小于ε,表示節(jié)點i的ε鄰域縮減,Гε(i)移除節(jié)點,置flag2為1;若原|Гε(i)|≥μ且邊刪除后|Гε(i)|<μ,表示節(jié)點i由核節(jié)點演變?yōu)榉呛斯?jié)點,更新IsCore(i)為false,置flag1為1.

部分節(jié)點雖然其鄰域內(nèi)沒有邊增加或刪除,但可能受二級影響導(dǎo)致相關(guān)屬性IsCore(i)、Гε(i)以及ConPre(i)發(fā)生變化,其更新與上述類似,不再贅述.另外,節(jié)點增加/刪除必然伴隨邊的增加/刪除,僅需要為新增節(jié)點建立存儲結(jié)構(gòu),無需額外處理.

算法2.updateNode(changeset)

Input:變化相關(guān)節(jié)點集changeset

Output:更新后節(jié)點的域信息

while(changeset!=NULL) {

if(增加邊e(i,j)){

j→Г(i);

if(SISSim(i,j)≥max(SISSim(i,x))) //x∈Г(i)

{update ConPre(i);i.flag3=1;}

if(SISSim(i,j)≥ε)

{j→Гε(i);<2,j>→i.flag2;}

if(原 |Гε(i)|<μ&& 邊增加后|Гε(i)|≥μ)

{ IsCore(i)=ture;i.flag1=2;}

}

if(邊刪除 || 受二級影響)

{這兩種情況的更新參照以上代碼,不再詳述;}

}

算法2對每個變化相關(guān)節(jié)點處理的時間復(fù)雜度為常量,因此算法整體的時間復(fù)雜度取決于變化相關(guān)節(jié)點集的大小,通常為O(D),其中D表示節(jié)點平均度.最壞情況下要考慮二級影響節(jié)點,即時間復(fù)雜度最高為O(D2).

4.2 社團更新

依據(jù)所得變化節(jié)點關(guān)鍵信息,對社團劃分進行更新.根據(jù)節(jié)點連接偏好的變化,更新連接偏好鏈.綜合考慮節(jié)點核心性及連接強弱的變化,決定偏好鏈的合并或分裂,由此得到社團合并或分裂的結(jié)果.

對于連接偏好變化的節(jié)點i,其所在偏好鏈由節(jié)點i處分裂為兩條新鏈,一條包含節(jié)點i的原連接偏好,另一條包含節(jié)點i,后者與節(jié)點i的新連接偏好所在鏈合并.

不同偏好鏈是否屬于同一社團,取決于它們之間是否存在CDSCC結(jié)構(gòu),顯然節(jié)點是否為核節(jié)點以及節(jié)點間連接是否為直接強結(jié)構(gòu)連接均能夠?qū)Υ私Y(jié)構(gòu)產(chǎn)生影響,因此綜合考慮節(jié)點核心性與強弱連接性的變化.這種結(jié)構(gòu)的消失累積到一定程度,將導(dǎo)致社團分裂;若隨網(wǎng)絡(luò)變化產(chǎn)生出偏好鏈之間原本不存在的這種結(jié)構(gòu),則社團合并(或偏好鏈原本屬于同一社團,可看作社團與自身合并的特殊情況).其他情況下,偏好鏈的社團歸屬保持不變.

算法3.updateCommunity(CSt,changeset)

Input:t時刻社團劃分CSt,變化相關(guān)節(jié)點集changeset

Output:t+1時刻社團劃分CSt+1

for(所有i∈changeset) {

if(i.flag3==1){

分裂i所在鏈;

i所在鏈→ConPre(i)所在鏈;}

if(i.flag1==1 ||i.flag2中第一屬性存在值為1的情況){

i所在社團中去除所有包含i的CDSCC;}

if (社團的抽象圖結(jié)構(gòu)不再連通)

//連接偏好鏈為抽象節(jié)點,CDSCC為抽象邊

社團分裂;

if (i.flag1==2){

for each (j∈Г(i) && IsCore(j)==ture)

if(e(i,j)為CDSCC){

合并i,j所在社團;//i,j可能屬于同一社團

CDSCC(i,j) 保存于合并后的社團;}

}

for (i.flag2中所有第一屬性值為2的元組){

if(e(i,j)為CDSCC){ //j為元組中第二屬性

合并i,j所在社團;//i,j可能屬于同一社團

CDSCC(i,j) 保存于合并后的社團;}

}

}

算法3根據(jù)變化相關(guān)節(jié)點的關(guān)鍵信息變化情況,判斷社團是否需要分裂或合并.設(shè)D表示節(jié)點平均度,C表示社團平均大小,當節(jié)點弱化時(核節(jié)點變?yōu)榉呛?或連接由強變?nèi)?最壞情況會導(dǎo)致社團分裂,更新其所在社團節(jié)點歸屬,即處理弱化一個節(jié)點的時間復(fù)雜度最高為O(C).當節(jié)點強化時(非核節(jié)點變?yōu)楹?或連接由弱變強),最壞情況會導(dǎo)致節(jié)點鄰域所有社團合并,更新其所在社團節(jié)點歸屬,則處理一個強化節(jié)點的時間復(fù)雜度最高為O(DC).顯然,除非網(wǎng)絡(luò)發(fā)生大范圍變化,上述最壞情況極少發(fā)生,通常情況下算法的時間復(fù)雜度為常量,時間效率較佳.

4.3 IU-LBS算法示例

IU-LBS算法首先確定變化相關(guān)節(jié)點集,縮小處理范圍,然后更新變化相關(guān)節(jié)點的關(guān)鍵信息,最后根據(jù)更新后的信息所體現(xiàn)的各類變化情況,獲得社團劃分的最新結(jié)果.

仍以第3節(jié)圖1所示拓撲為例,設(shè)當前時刻為t,在圖G上添加動態(tài)變化如下:

?t+1時刻:增加邊(d,p).

?t+2時刻:增加邊(c,p).

?t+3時刻:增加節(jié)點g,增加邊(d,g)、(p,g).

圖2 t+1時刻網(wǎng)絡(luò)G的拓撲結(jié)構(gòu)Fig.2 Topology structure of G on time t+1

t+1時刻,變化相關(guān)節(jié)點集為:

Г(d)∪Г(p)={a,b,c,e,f,o,q,r,s,t,u}

此時刻集合中的節(jié)點連接偏好、強弱連接性以及核心性均未發(fā)生改變,因此社團結(jié)構(gòu)沒有改變.

圖3 t+2時刻網(wǎng)絡(luò)G的拓撲結(jié)構(gòu)Fig.3 Topology structure of G on time t+2

t+2時刻變化相關(guān)節(jié)點集為:

Г(c)∪Г(p)={b,d,f,h,n,o,q,r,s,t,u}

此時刻集合中的節(jié)點連接偏好、強弱連接性以及核心性仍未發(fā)生改變,因此社團結(jié)構(gòu)仍沒有改變.

t+3時刻變化相關(guān)節(jié)點集為:

Г(g)∪Г(d)∪Г(p)={a,b,c,e,f,g,o,q,r,s,t,u,d,p}

此時刻節(jié)點d與節(jié)點p仍為核節(jié)點,其核心性未改變,但它們之間的連接由t+2時刻的弱結(jié)構(gòu)連接變?yōu)閺娊Y(jié)構(gòu)連接.由于它們歸屬于不同的社團,因此社團合并,即此時刻社團劃分結(jié)果為:

{(a,d,e,f,j,k,l,m,b,c,h,i,n,o,p,t,u,v,q,r,x,y,z,s,w)}.

圖4 t+3時刻網(wǎng)絡(luò)G的拓撲結(jié)構(gòu)Fig.4 Topology structure of G on time t+3

5 實 驗

本文所采用的實驗環(huán)境如表1所示.

表1 實驗環(huán)境
Table 1 Experimental environment

實驗環(huán)境 環(huán)境信息處理器Intel(R)Pentium(R)G645主頻2.90GHz內(nèi)存4G操作系統(tǒng)Windows7編程語言Java編譯環(huán)境MyEclipse

5.1 劃分質(zhì)量評價標準

社團劃分質(zhì)量的評價指標選擇歸一化互信息(Normalized Mutual Information),其形式化表示如式(2)所示.

(2)

式(2)中A、B分別表示原社團劃分與算法所得劃分,Nij表示A中i社團與B中j社團之間重疊的節(jié)點數(shù).A與B之間相似的程度由NMI(A,B)表示,其取值范圍在0與1之間.若A與B相似程度越高,NMI(A,B)值越接近1,表明算法具有更準確的社團劃分能力.顯然,選取NMI(A,B)值作為劃分質(zhì)量評價標準,需要一個參照比較對象,即式(2)中的A劃分,且該劃分應(yīng)為標準劃分結(jié)果.因此,該標準通常用于已知劃分結(jié)果的網(wǎng)絡(luò)上,如由模型生成的人工網(wǎng)絡(luò)或經(jīng)典的小型現(xiàn)實網(wǎng)絡(luò).

5.2 靜態(tài)LBS算法實驗分析

5.2.1 現(xiàn)實網(wǎng)絡(luò)實驗結(jié)果及分析

對比算法選擇Newman快速算法(FN算法),在現(xiàn)實網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上運行FN算法及LBS算法,通過對比驗證LBS算法具備較高的劃分質(zhì)量和效率.實驗數(shù)據(jù)選取經(jīng)典的復(fù)雜網(wǎng)絡(luò)分析數(shù)據(jù)集:Zachary空手道俱樂部成員關(guān)系網(wǎng)與美國大學橄欖球聯(lián)賽網(wǎng).Zachary空手道俱樂部成員關(guān)系網(wǎng)[18]體現(xiàn)了美國某大學的空手道俱樂部會員之間的社交關(guān)系(以下簡稱空手道數(shù)據(jù)集),包含34個節(jié)點以及78條邊,是復(fù)雜網(wǎng)絡(luò)社團劃分算法準確性衡量的一個代表性數(shù)據(jù)集.美國大學橄欖球網(wǎng)[10]體現(xiàn)了美國大學生橄欖球聯(lián)賽某個賽季的比賽情況(以下簡稱橄欖球數(shù)據(jù)集),網(wǎng)絡(luò)中包含115個節(jié)點以及613條邊,其中節(jié)點表示一支球隊,邊代表球隊間的比賽,也是常用于復(fù)雜網(wǎng)絡(luò)社團分析的代表性數(shù)據(jù)集.

圖5 不同ε下的NMI值Fig.5 NMI with different ε

LBS算法中需要輸入ε與μ兩個參數(shù),分別用于判斷節(jié)點是否為核節(jié)點,以及節(jié)點之間的連接為強/弱結(jié)構(gòu),因此參數(shù)值的選擇對于算法劃分社團的質(zhì)量有一定影響.下面以橄欖球數(shù)據(jù)集為例,說明通過觀察參數(shù)ε、μ對NMI值的影響來進行取值選擇的過程.

由參數(shù)ε和μ定義以及在LBS算法中的作用可以看出,二者對算法效果的影響是獨立的,因此可以采取將兩個參數(shù)分別設(shè)為變量和常量的方式,來觀察其對實驗所用網(wǎng)絡(luò)數(shù)據(jù)的適應(yīng)性.圖5給出參數(shù)μ設(shè)為4時,不同ε取值情況下算法所得到NMI值,圖6給出參數(shù)ε設(shè)為1.2時,不同μ取值情況下算法所得到NMI值.由圖中可以看出,在橄欖球網(wǎng)絡(luò)上參數(shù)值為ε=1.3,μ=4時NMI達到峰值,即算法效果最佳.類似,可以通過實驗得出空手道數(shù)據(jù)集中選取ε=1.2,μ=3時算法效果最佳.在空手道數(shù)據(jù)集與橄欖球數(shù)據(jù)集上分別選取最適合的參數(shù)ε和μ運行LBS算法,與FN算法進行對比,結(jié)果如表2所示.

圖6 不同μ下的NMI值Fig.6 NMI with different μ

由表2可以看出,在相同數(shù)據(jù)集上運行FN算法和LBS算法,NMI值較為接近.說明LBS算法可以給出比較高質(zhì)量的社團劃分結(jié)果,但由于數(shù)據(jù)集較小,運行時間的對比意義不明顯,需要在更大規(guī)模的數(shù)據(jù)集上進行進一步的對比.

表2 算法在不同數(shù)據(jù)集上的劃分效果比較(NMI)
Table 2 NMI on different dataset

數(shù)據(jù)集LBSFN空手道0.8530.894橄欖球0.9220.813

5.2.2 人工網(wǎng)絡(luò)實驗結(jié)果及分析

由于現(xiàn)實經(jīng)典網(wǎng)絡(luò)規(guī)模通常較小且沒有標準的社團劃分結(jié)果作為參照,為了驗證大規(guī)模網(wǎng)絡(luò)的條件下LBS算法的劃分效果和執(zhí)行效率,本文利用網(wǎng)絡(luò)生成程序建立了不同規(guī)模的人工數(shù)據(jù)集,并在其上對比FN算法和LBS算法的運行效果.

表3 LFR模型參數(shù)
Table 3 Parameter of LFR

參數(shù)取值意義N10000～90000網(wǎng)絡(luò)節(jié)點總數(shù)k25節(jié)點平均度數(shù)Maxk50網(wǎng)絡(luò)中節(jié)點的最大度數(shù)Γ2網(wǎng)絡(luò)節(jié)點度冪律分布指數(shù)Β1網(wǎng)絡(luò)中社區(qū)規(guī)模冪律分布指數(shù)Maxc50最大社團所包含的節(jié)點數(shù)Minc25最小社團所包含的節(jié)點數(shù)

網(wǎng)絡(luò)生成程序LFR是由Lancichinetti等人[19]提出的,該程序生成的人工網(wǎng)絡(luò)包含明確的社團劃分情況, 便于比較不同算法的社團劃分質(zhì)量.LFR通過設(shè)定不同的參數(shù)值來調(diào)整人工網(wǎng)絡(luò)的規(guī)模與結(jié)構(gòu),方便在不同的數(shù)據(jù)集上比較算法的性能.本小節(jié)中LFR生成程序需要設(shè)定的參數(shù)意義及取值如表3所示.

圖7 靜態(tài)算法運行時間對比Fig.7 Runtime of static algorithm

圖7與圖8分別給出其他參數(shù)設(shè)定相同的情況下,不同規(guī)模網(wǎng)絡(luò)上FN算法與LBS算法運行時間與劃分質(zhì)量的對比.其中LBS算法參數(shù)取值為ε=1.3,μ=10.

由圖7可以看出,當網(wǎng)絡(luò)規(guī)模較小時,FN算法與LBS算法運行時間比較接近,但隨著網(wǎng)絡(luò)規(guī)模不斷增大,LBS算法的優(yōu)勢愈加明顯.原因是FN算法采用全局思想,為進行社團劃分所收集的信息涉及整個網(wǎng)絡(luò),其運行時間隨網(wǎng)絡(luò)規(guī)模的增大呈指數(shù)增長的趨勢,而采用局部思想的LBS算法僅收集二級影響范圍內(nèi)的信息,在網(wǎng)絡(luò)規(guī)模較大的時候依舊能夠保持較少的運行時間.

圖8 靜態(tài)算法NMI值對比Fig.8 NMI of static algorithm

由圖8可以看出,當網(wǎng)絡(luò)規(guī)模較小時,FN算法與LBS算法均具有很高的NMI值.隨著網(wǎng)絡(luò)規(guī)模增大,二者NMI值均有下降,但差異很小,說明LBS算法雖然采取局部思想,但仍能夠與經(jīng)典全局算法一樣,具有較準確的社團劃分能力.

以上的實驗對比證明,本文提出的靜態(tài)局部社團劃分算法-LBS算法在保證準確性的同時,具有時間效率上的優(yōu)勢,且算法的伸縮性優(yōu)于傳統(tǒng)算法.

5.3 動態(tài)IU-LBS算法的實驗分析

以LFR程序生成的人工網(wǎng)絡(luò)數(shù)據(jù)為基礎(chǔ), 隨機進行增加或刪除操作, 模擬網(wǎng)絡(luò)動態(tài)變化. 模型生成人工網(wǎng)絡(luò)的參數(shù)取值與5.2.2小節(jié)相同, 每組模擬動態(tài)變化包括如下4種操作:

? 添加10個節(jié)點,并將其隨機連接至當前已有節(jié)點;

? 隨機刪除10個節(jié)點,同時刪除與其連接的邊;

? 添加10條邊,其兩端點均為當前網(wǎng)絡(luò)中已存在且不相鄰的隨機節(jié)點;

? 隨機刪除10條邊,其兩端點度均大于1(避免刪除邊后形成孤立點).

圖9 動態(tài)算法運行時間對比Fig.9 Runtime of dynamic algorithm

對比算法選取傳統(tǒng)動態(tài)框架的Scan算法、 基于進化的Facetnet算法以及基于增量的IC算法. 考慮到Scan算法與Facetnet算法均重復(fù)進行全網(wǎng)計算, 運行時間取決于網(wǎng)絡(luò)規(guī)模; 而IC算法與本文IU-LBS算法僅計算變化相關(guān)的部分網(wǎng)絡(luò), 運行時間則取決于網(wǎng)絡(luò)動態(tài)變化影響范圍. 因此在不同規(guī)模網(wǎng)絡(luò)上執(zhí)行相同的1組模擬動態(tài)操作, 由此對比不同動態(tài)變化程度下算法的執(zhí)行時間. 實驗結(jié)果如圖9所示.

由圖9可以看出,與非增量式的Scan算法和Facetnet算法相比,增量式的IC算法和IU-LBS算法具有明顯的時間效率優(yōu)勢.特別是當網(wǎng)絡(luò)規(guī)模增大,而模擬動態(tài)操作不變,即網(wǎng)絡(luò)變化程度逐漸減弱時,增量式算法的時間效率優(yōu)勢愈加明顯.這是因為非增量式算法重復(fù)執(zhí)行全網(wǎng)絡(luò)計算,其運行時間隨網(wǎng)絡(luò)規(guī)模的增大呈線性增長,不適用于大規(guī)模動態(tài)網(wǎng)絡(luò)環(huán)境.而IC算法計算變化節(jié)點相關(guān)社團內(nèi)的節(jié)點,IU-LBS算法計算變化節(jié)點的二級影響鄰域,由于實驗中模擬動態(tài)操作不變,即變化節(jié)點數(shù)目固定,因此隨著網(wǎng)絡(luò)規(guī)模的增大,兩種增量式算法的運行時間基本保持不變,并且二者計算范圍的大小比較接近,時間效率差別不大.

作為動態(tài)網(wǎng)絡(luò)社團發(fā)現(xiàn)算法,不僅應(yīng)具有較高的準確度,而且還應(yīng)隨網(wǎng)絡(luò)的不斷變化保持穩(wěn)定.為對比算法準確度及其穩(wěn)定性,在同一網(wǎng)絡(luò)上重復(fù)執(zhí)行模擬動態(tài)操作,以體現(xiàn)網(wǎng)絡(luò)的不斷變化.仍以LFR程序生成的人工網(wǎng)絡(luò)數(shù)據(jù)為基礎(chǔ),節(jié)點數(shù)設(shè)為10000,其他參數(shù)不變,重復(fù)執(zhí)行模擬動態(tài)操作100組,每10組操作計算1次NMI值,實驗結(jié)果如圖10所示.其中算法劃分質(zhì)量的對比標準選取FN算法,即以FN算法劃分結(jié)果為參照比較基準來計算4個對比算法的NMI值.

圖10 動態(tài)算法NMI對比Fig.10 NMI of dynamic algorithm

由圖10可以看出, Scan算法與Facetnet算法在每個時刻都要重新進行全網(wǎng)絡(luò)社團劃分, 其準確性較為穩(wěn)定. 而增量式的IC算法與IU-LBS算法考慮了充分的變化相關(guān)信息, 其穩(wěn)定程度也得到了保證. 其中IC算法收集變化相關(guān)信息時, 僅考慮了變化邊的兩端點, 而IU-LBS算法考慮了節(jié)點的二級影響, 使得算法的準確率優(yōu)于IC算法, 僅比Facetnet算法略低.綜合看來, IU-LBS算法的時間效率與社團劃分質(zhì)量上都較為優(yōu)秀, 更適用于大規(guī)模的動態(tài)復(fù)雜網(wǎng)絡(luò)上的社團劃分.

6 總 結(jié)

本文采取局部思想,定義二級影響結(jié)構(gòu)相似度,并進一步定義節(jié)點強/弱結(jié)構(gòu)連接、核心性及連接偏好.提出LBS算法,通過連接偏好構(gòu)造偏好鏈,考察偏好鏈核節(jié)點之間的強結(jié)構(gòu)連接,據(jù)此進行偏好鏈合并形成社團.通過在實際網(wǎng)絡(luò)數(shù)據(jù)集與人工網(wǎng)絡(luò)數(shù)據(jù)集上進行對比試驗,驗證了LBS算法社團劃分的準確性,并說明其時間效率上的優(yōu)勢.

在LBS算法的基礎(chǔ)上,進一步提出動態(tài)社團增量更新算法-IU-LBS算法.算法隨著網(wǎng)絡(luò)的動態(tài)變化,計算變化相關(guān)節(jié)點的關(guān)鍵信息,結(jié)合LBS算法結(jié)果,及時更新偏好鏈及其連接關(guān)系,從而獲得社團的實時劃分.通過在人工模擬動態(tài)網(wǎng)絡(luò)上的對比試驗,說明了IU-LBS算法具有較好的社團劃分準確性以及優(yōu)秀的時間效率,對大規(guī)模動態(tài)網(wǎng)絡(luò)社團劃分具有更好的適用性.

[1] Ino H,Kudo M,Nakamura A.Partitioning of web graphs by community topology[C].Proceedings of the 14th International Conference on World Wide Web,ACM,2005:661-669.

[2] Sun Da-ming,Zhang Bin,Zhang Shu-bo,et al.A popularity versus similarity query recommendation strategy [J].Journal of Chinese Computer Systems,2016,37(6):1121-1125.

[3] Liu Y,Moser J,Aviyente S.Network community structure detection for directional neural networks inferred from multichannel multisubject EEG data[J].IEEE Transactions on Bio-medical Engineering,2014,61(7):1919-1930.

[4] Li Hui-jia,Li Ai-hua,Li Hui-ying.Fast community detection algorithm via dynamical iteration[J].Chinese Journal of Computers,2017,40(4):970-984.

[5] Xie Yi,Sun Yu-qing,Shen Lei.Theme and community evolution in complex social network[J].Journal of Chinese Computer Systems,2016,37(11):2402-2408.

[6] Xu Gang,Jin Hai-he,Liu Jing.Community detection based on the opportunistic networks uncertain social[J].Journal of Chinese Computer Systems,2016,37(11):2473-2477.

[7] Palla G,Derenyi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society [J].Nature,2005,435(7043):814-818.

[8] Pothen A,Simon H,Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J].SLAM Journal on Matrix Analysis and Applications,1990,11(3):430-452.

[9] Kernighan B W,Lin S.A efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,2014,49(2):291-307.

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

[11] Newman M E.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.

[12] Xu X,Yuruk N,Feng Z,et al.SCAN:a structural clustering algorithm for networks[C].Proceedings of the 2007 International Conference on Knowledge Discovery and Data Mining，San Jose,California,ACM Press,2007:824-833.

[13] Lin Y R,Chi Y,Zhu S,et al.Facetnet:a framework for analyzing communities and their evolutions in dynamic networks[C].Proceedings of the 2008 International Conference on World Wide Web,2008:685-694.

[14] Shan Bo,Jiang Shou-xu,Zhang Shuo,et al.IC:incremental algorithm for community identification in dynamic social networks [J].Journal of Sofeware,2009,20 (11):184-192.

[15] Han Zhong-ming,Tan Xu-sheng,Chen Yan,et al.NCSS:an effective and efficient complex network community detection algorithm[J].Scientia Sinica Informationis,2016,46(4):431-444.

[16] Luo Q.A new community structure detection method based on structural similarity[C].Proceedings of the 7th International Conference on Computational Intelligence and Security，IEEE,2012:1260-1262.

[17] Opsahl T.Triadic closure in two-mode networks:redefining the global and local clustering coefficients[J].Social Networks,2013,35(2):159-167.

[18] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.

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

附中文參考文獻：

[2] 孫達明,張 斌,張書波,等.一種流行性與相似性結(jié)合查詢推薦策略[J].小型微型計算機系統(tǒng),2016,37(6):1121-1125.

[4] 李慧嘉,李愛華,李慧穎.社團結(jié)構(gòu)迭代快速探測算法[J].計算機學報,2017,40(4):970-984.

[5] 謝 翌,孫宇清,沈 雷.復(fù)雜社會網(wǎng)絡(luò)中主題驅(qū)動的社團演化[J].小型微型計算機系統(tǒng),2016,37(11):2402-2408.

[6] 許 崗,金海和,劉 靖.機會網(wǎng)絡(luò)的不確定社會關(guān)系社團發(fā)現(xiàn)[J].小型微型計算機系統(tǒng),2016,37(11):2473-2477.

[14] 單 波,姜守旭,張 碩,等.IC:動態(tài)社會關(guān)系網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的增量識別算法[J].軟件學報,2009,20(11):184-192.

[15] 韓忠明,譚旭升,陳 炎,等.NCSS:一種快速有效的復(fù)雜網(wǎng)絡(luò)社團劃分算法[J].中國科學:信息科學,2016,46(4):431-444.