一種采用二級影響結構相似度的動態社團更新算法

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

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

1 引 言

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

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

目前研究成果多數是面向靜態復雜網絡上的社團劃分,而現實網絡普遍具有動態演變的特征,因此針對動態復雜網絡上社團發現的相關研究得到越來越多的關注.但由于其起步較晚,相關研究成果較少,且時間效率及社團劃分質量有待提高.

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

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

2 社團劃分相關定義

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

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

(1)

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

式(1)體現了共同鄰居的貢獻值,并考慮其在二級鄰域中的影響,對于網絡結構相關的節點相似度具有更準確的體現.在此基礎上,進一步提出用于靜態社團劃分及動態增量更新的相關定義.其中參數ε、μ可由用戶依網絡具體結構情況進行調整,以適用于不同的應用需求.

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

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

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

對于大規模動態網絡,全局社團發現算法時間效率低下,因此本文采取局部分析思路.考慮到網絡中相似度大的節點應歸屬同一社團,提出連接偏好概念,具體定義如下:

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

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

3 靜態局部社團劃分算法-LBS算法

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

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

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

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包含未標記節點){

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

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

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

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

以圖1所示網絡G為例說明算法社團劃分結果.該網絡由25個節點和76條連邊組成，節點依字母升序的連接偏好計算結果依次為：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 網絡G的拓撲結構Fig.1 Topology structure of G

算法輸入參數值分別為ε=1.25,μ=3,計算所得核節點為a、b、c、d、p、q、r、s、t.

構造所得連接偏好鏈集為:{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}.

同一節點的多個連接偏好所在鏈進一步合并所得為:{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}.

對不同偏好鏈核節點間存在直接強結構的情況,合并形成社團,最終該網絡社團劃分結果為:

{(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 動態復雜網絡上的社團更新算法-IU-LBS算法

以靜態LBS算法為基礎,提出適用于動態復雜網絡的社團發現算法IU-LBS算法.IU-LBS算法隨網絡變化更新相關節點信息,如相似度、連接偏好以及是否為核節點等,并利用LBS算法處理結果,包括連接偏好鏈構造與社團劃分,更新偏好鏈以及鏈間關鍵連接CDSCC,進而更新社團劃分結果.

4.1 更新變化節點的屬性域

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

? flag 1.值為1表示核節點演變為非核節點,值為2表示非核節點演變為核節點,值為0表示無變化.

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

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

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

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

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

算法2.updateNode(changeset)

Input:變化相關節點集changeset

Output:更新后節點的域信息

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對每個變化相關節點處理的時間復雜度為常量,因此算法整體的時間復雜度取決于變化相關節點集的大小,通常為O(D),其中D表示節點平均度.最壞情況下要考慮二級影響節點,即時間復雜度最高為O(D2).

4.2 社團更新

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

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

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

算法3.updateCommunity(CSt,changeset)

Input:t時刻社團劃分CSt,變化相關節點集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 (社團的抽象圖結構不再連通)

//連接偏好鏈為抽象節點,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根據變化相關節點的關鍵信息變化情況,判斷社團是否需要分裂或合并.設D表示節點平均度,C表示社團平均大小,當節點弱化時(核節點變為非核,或連接由強變弱)最壞情況會導致社團分裂,更新其所在社團節點歸屬,即處理弱化一個節點的時間復雜度最高為O(C).當節點強化時(非核節點變為核,或連接由弱變強),最壞情況會導致節點鄰域所有社團合并,更新其所在社團節點歸屬,則處理一個強化節點的時間復雜度最高為O(DC).顯然,除非網絡發生大范圍變化,上述最壞情況極少發生,通常情況下算法的時間復雜度為常量,時間效率較佳.

4.3 IU-LBS算法示例

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

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

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

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

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

圖2 t+1時刻網絡G的拓撲結構Fig.2 Topology structure of G on time t+1

t+1時刻,變化相關節點集為:

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

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

圖3 t+2時刻網絡G的拓撲結構Fig.3 Topology structure of G on time t+2

t+2時刻變化相關節點集為:

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

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

t+3時刻變化相關節點集為:

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

此時刻節點d與節點p仍為核節點,其核心性未改變,但它們之間的連接由t+2時刻的弱結構連接變為強結構連接.由于它們歸屬于不同的社團,因此社團合并,即此時刻社團劃分結果為:

{(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時刻網絡G的拓撲結構Fig.4 Topology structure of G on time t+3

5 實 驗

本文所采用的實驗環境如表1所示.

表1 實驗環境
Table 1 Experimental environment

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

5.1 劃分質量評價標準

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

(2)

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

5.2 靜態LBS算法實驗分析

5.2.1 現實網絡實驗結果及分析

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

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

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

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

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

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

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

數據集LBSFN空手道0.8530.894橄欖球0.9220.813

5.2.2 人工網絡實驗結果及分析

由于現實經典網絡規模通常較小且沒有標準的社團劃分結果作為參照,為了驗證大規模網絡的條件下LBS算法的劃分效果和執行效率,本文利用網絡生成程序建立了不同規模的人工數據集,并在其上對比FN算法和LBS算法的運行效果.

表3 LFR模型參數
Table 3 Parameter of LFR

參數取值意義N10000～90000網絡節點總數k25節點平均度數Maxk50網絡中節點的最大度數Γ2網絡節點度冪律分布指數Β1網絡中社區規模冪律分布指數Maxc50最大社團所包含的節點數Minc25最小社團所包含的節點數

網絡生成程序LFR是由Lancichinetti等人[19]提出的,該程序生成的人工網絡包含明確的社團劃分情況, 便于比較不同算法的社團劃分質量.LFR通過設定不同的參數值來調整人工網絡的規模與結構,方便在不同的數據集上比較算法的性能.本小節中LFR生成程序需要設定的參數意義及取值如表3所示.

圖7 靜態算法運行時間對比Fig.7 Runtime of static algorithm

圖7與圖8分別給出其他參數設定相同的情況下,不同規模網絡上FN算法與LBS算法運行時間與劃分質量的對比.其中LBS算法參數取值為ε=1.3,μ=10.

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

圖8 靜態算法NMI值對比Fig.8 NMI of static algorithm

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

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

5.3 動態IU-LBS算法的實驗分析

以LFR程序生成的人工網絡數據為基礎, 隨機進行增加或刪除操作, 模擬網絡動態變化. 模型生成人工網絡的參數取值與5.2.2小節相同, 每組模擬動態變化包括如下4種操作:

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

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

? 添加10條邊,其兩端點均為當前網絡中已存在且不相鄰的隨機節點;

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

圖9 動態算法運行時間對比Fig.9 Runtime of dynamic algorithm

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

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

作為動態網絡社團發現算法,不僅應具有較高的準確度,而且還應隨網絡的不斷變化保持穩定.為對比算法準確度及其穩定性,在同一網絡上重復執行模擬動態操作,以體現網絡的不斷變化.仍以LFR程序生成的人工網絡數據為基礎,節點數設為10000,其他參數不變,重復執行模擬動態操作100組,每10組操作計算1次NMI值,實驗結果如圖10所示.其中算法劃分質量的對比標準選取FN算法,即以FN算法劃分結果為參照比較基準來計算4個對比算法的NMI值.

圖10 動態算法NMI對比Fig.10 NMI of dynamic algorithm

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

6 總 結

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

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

[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] 孫達明,張 斌,張書波,等.一種流行性與相似性結合查詢推薦策略[J].小型微型計算機系統,2016,37(6):1121-1125.

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

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

[6] 許 崗,金海和,劉 靖.機會網絡的不確定社會關系社團發現[J].小型微型計算機系統,2016,37(11):2473-2477.

[14] 單 波,姜守旭,張 碩,等.IC:動態社會關系網絡社區結構的增量識別算法[J].軟件學報,2009,20(11):184-192.

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