離散Jaya算法的復雜網絡社區發現①

李劍雄,鮑志強

(華南師范大學 計算機學院，廣州 510631)

許多現實世界中的復雜系統都可以使用復雜網絡來描述,例如社交網、生物網、萬維網、交通網等.復雜網絡可建模為圖,其中節點表示網絡中的對象,邊表示對象間的關系.大量研究結果表明:復雜網絡通常具有小世界性和無標性等統計特性,并呈現出社區結構等拓撲特性.一個網絡可以分成若干社區,社區內部的節點連接相對緊密,不同社區之間的節點連接相對稀疏[1,2].社區發現的目的是找出復雜網絡的社區結構,提取社區結構中的信息.

來自不同領域的研究中提出了許多不同的社發現算法,這些算法可大致分為:圖劃分的分割算法[3]、聚類算法[4-6]、基于網絡動力學特性的算法[7-9]和基于目標函數的優化算法[10-14].其中以模塊度函數(Modularity,Q)的為目標函數的優化算法是目前較為普遍的一類算法.模塊度函數Q是Newman 提出的評價社區結構優劣的指標[6],借助于該函數可將社區發現問題轉化為優化問題.如Duch[15]提出了基于模塊度的極值優化算法,Guimera 等[16]基于模擬退火的GA(Genetic algorithm)算法,2008年Blondel 等[17]提出的BGLL 算法.然而求最優模塊度的社區結構是NP 難問題,常常用啟發式算法求解.許多啟發式算法屬于貪心法,一般很難求得滿意的社區劃分結果,且需要預先設定網絡的社區數目.智能優化元啟發式算法作為社區發現問題的一種有效解決手段,目前已被廣泛應用求解[18-20].Talbi 等[21]提出了一種求解圖劃分問題的并行遺傳算法,該算法具有超線性加速特性.Bui 等[22]提出了基于圖劃分的預處理模式從而提高遺傳算法的空間搜索能力.Tasgin等[23]基于模塊度使用了遺傳算法進行社區發現.Gog 等[24]基于種群中個體的信息分享機制提出了一種協同進化算法用于社區發現.Pizzuti[25]提出了GANet 遺傳算法,利用了locus-based 表示法和交叉操作,該方法在操作時只考慮了該點的實際連接關系,有效的減少了無效搜索.Gong 等[26]提出了一種文化基因算法用于優化模塊密度進行社區發現.Duch 等[15]通過對標準差分進化算法的交叉操作進行離散化,提出了離散差分進化算法用于社區發現.Change 等[27]采用最大最小蟻群算法,通過信息素的揮發和路徑的選擇進行社區的劃分.金弟等[13]通過分析模塊度函數的局部單調性,以及改進遺傳算法的變異策略,提出一種基于局部搜索的改進遺傳算法.張英杰等[14]提出了一種基于免疫差分進化算法IDDE (Immune Discrete Differential Evolutiona).Said 等[28]提出了基于聚類協同系數的CC-GA (Clustering Coefficient based Genetic Algorithm)算法,該算法可用于稠密網絡和稀疏網絡的社區發現.

Jaya 算法[29]是由Rao RV 提出的一種元啟發式算法,適用于求解連續型最優化問題.與其它元啟發式算法相比,Jaya 算法簡單,需要輸入的參數少,只需設置種群大小和迭代次數.該算法通過離散化,近年來已被應用在許多不同的組合優化問題上[30,31].本文針對復雜網絡社區發現問題,遵循Jaya 算法的基本思想,提出了一種離散化的算法形式稱作DJaya (Discrete Jaya algorithm),其核心思想是針對種群中個體不同的傾向性,采取不同的更新方式,平衡全局探索性和局部搜索性來提高搜索的有效性.在標準人造網絡數據集GN Benchmark 和幾個典型的真實網絡算例上的實驗分析表明,DJaya 算法能自動確定社區的數目,且在模塊度、互信息等方面表現出良好的性能[32].

1 相關工作

1.1 模塊度函數

不同的社區發現算法在同一復雜網絡上進行社區劃分時結果通常是不同的.為了統一評價標準,Newman等提出了社區結構的模塊度函數.模塊度函數易于理解且計算簡單,被廣泛用來評價社區劃分質量[5].一個社區結構的模塊度Q定義如下:

其中,ki表示節點i的 度,kikj/2m表示節點i與 節點j之間的連接概率,Aij表示圖的鄰接矩陣,如果節點i與節點j有邊相連,則Aij=1,否則Aij=0.ci表示節點i所屬的社區,如果ci=cj,則δ (ci,cj)=1,否則δ (ci,cj)=0.通常,Q值的范圍是[-0.5,1),越接近于1,則復雜網絡的社區結構越明顯.Q值一般在0.3-0.7 的范圍內[2],當Q＜0.3時表明網絡幾乎沒有社區結構.

1.2 基于模塊度的社區發現的典型算法

基于模塊度優化的社區發現算法有許多,其中包括許多以模塊度為目標函數的算法,其典型的代表如FMM (Fast Modularity Maximization)算法[5]、LPA(Label Propagation Algorithm)算法[33]、BGLL 算法[24]等貪心啟發式算法,以及近年提出的ACO (Ant Colony Optimization)[28]、LGA (Genetic Algorithm with Local search)[14]、IDDE、CC-GA 等元啟發式算法.

FMM 算法將圖中每個節點初始化為一個單獨的社區,然后選擇使模塊度Q的增值最大的社區進行合并,重復該步驟,直到網絡中所有節點屬于同一個社區.整個過程是自底向上的過程,最終得到一個層次圖.網絡中節點對應層次圖的最底層的葉子節點.層次圖中每一層對應網絡的某種劃分,層次圖中所有層次對應的劃分中模塊度最大的劃分為網絡最終劃分.

標簽傳播算法LPA 是由Raghavan 等提出的[34],其基本思想是讓每個節點有一個自己特有的標簽,節點會選擇自己鄰居中出現次數最多的標簽,如果每個標簽出現次數一樣多,就隨機選擇一個標簽替換自己原始的標簽,如此往復,直到每個節點標簽不再發生變化,那么持有相同標簽的節點就歸為一個社區.標簽傳播算法具有簡單、高效、快速的優點,常常和其它算法結合,用來初始化種群,增加種群的多樣性和精度,加快算法的收斂.

BGLL 算法是一種層次性貪心算法,它是一個兩階段過程.第一階段首先將每一個節點劃分作為單獨的社區,然后考慮將每個節點合并到其鄰接點所在的社區中,執行能使模塊度增大的合并.第二階段將第一階段劃分出來的社區聚合成為一個點后形成新的網絡,再在新的網絡上重復以上過程,直到網絡中的結構不再改變為止.

ACO 算法以網絡的一個隨機社區劃分作為初始解,通過編碼把初始解作為路徑上的初始信息素,然后利用網絡的鄰接矩陣作為路徑選擇啟發函數,采用最大最小蟻群算法不斷對模塊度函數進行優化.迭代一定次數后,產生的路徑即解碼為最終的社區劃分.

LGA 算法以模塊度Q為目標函數,采用基于社區標識的編碼方式,然后利用標簽傳播法初始化種群,采用單路交叉、局部搜索變異LMA 和μ+λ選擇等3 個算子來探測網絡社區結構.

IDDE 算法的基本思想是先用標簽傳播法初始化種群;然后借鑒差分進化算法基本特征,采用隨機單點變異、單路交叉和貪婪選擇策略生成中間種群,最后對執行免疫克隆選擇操作,生成下一代種群.該算法融合離散差分進化算法的全局搜索能力和免疫克隆選擇策略的局部搜索能力,增加了算法的魯棒性.

CC-GA 算法通過使用聚類協同系數來初始化種群,以模塊度為適應度函數,利用遺傳中的統一交叉和提出的變異操作進行更新種群,該算法不需要預先知道社區的數量.可用于稠密和稀疏網絡的社區發現.

1.3 Jaya 算法

Jaya 算法是近年來出現的一種元啟發式優化算法.Jaya 這個詞在梵語中是勝利的意思.因為該算法力求達到最優解從而取得勝利,因此命名為Jaya 算法[30].Jaya 算法中,第一步是隨機初始化規模大小為NP的種群,后續每一步不斷迭代,每次迭代中要完成從一個種群更新到下一個種群的任務,直到滿足最大迭代次數為止.每一代種群要選出最好解和最差解用于更新種群中的每個個體解.種群中個體的更新采用下述公式:

其中,XB(t)和Xw(t)分別表示第t代種群中最好解和最差解,i表示種群中第i個 個體解.r1和r2每個個體更新時產生的0 到1 的隨機數,用作縮放因子試圖增強算法的多樣性.式中+r1×(XB(t)-|Xi(t)|)表明個體X有朝著最優個體靠近的趨勢,式中-r2×(Xw(t)-|Xt(t)|)則表明個體X有遠離最差個體的趨勢.在每一代種群個體更新過程中,如果種群中下一代個體Xi(t+1)的目標函數值更優,則替代上一代個體Xi(t),否則,保持不變.

Jaya 與其它元啟發式優化算法相比,簡單易理解,參數較少,只需要設定種群的大小和迭代的次數.Jaya算法的流程圖如圖1.

圖1 Jaya 算法流程圖

2 離散Jaya 的社區發現算法

在本節中,我們主要介紹如何對Jaya 算法進行離散化.主要從社區的編碼和初始化、離散化策略以及算法偽代碼幾方面展開.

2.1 社區結構的表示和初始化

社區結構對應網絡的劃分,其表示方式往往與算法相關且是影響算法效果的一個關鍵.社區發現的進化類算法中,一個社區結構對應的網絡劃分可以看作是一個個體.目前有兩種經典的個體表示方法[32],一種是基于社區標識符表示法LR (Label-based Representation),另外一種是局部鄰接表示LAR (Locus-based Adjacency Representation).本文采用局部鄰接表示法,在該表示法中,向量的元素值代表該節點的某個鄰居節點的節點標識符.如圖2,網絡局部鄰接表示如表1,其對應的網絡劃分見圖3.

圖2 一個網絡示例

圖3 表1對應的局部鄰接表示所導出的網絡劃分

根據上述社區表示結構方式,本文使用類似標簽傳播思想的方法進行種群的初始化.在初始化過程中,首先使網絡中的每個節點都隨機選擇其中一個鄰居節點,每一次迭代中,如果節點i的鄰居節點出現的次數最多,則該鄰居節點作為節點i的值;如果鄰居節點出現的次數一樣,則隨機選擇一個鄰居節點.

2.2 離散化策略

Jaya 算法適用于求解連續性的最優化的問題.Jaya 算法的主要思想是通過遠離最差解,靠近最優解更新種群.社區發現是一個離散型的組合優化問題.當使用個體向量表示社區的一個劃分時,該向量中的每一個元素代表一個節點,如果利用Jaya 算法對個體向量更新,如對個體向量的作差運算,但節點之間的作差運算并無意義.為了采用Jaya 算法的思想求解社區結構劃分問題,我們需要對Jaya 算法做離散化處理,為此先引入幾個概念.

(1)傾向性

為了判斷種群中的個體是更靠近最優解個體還是更靠近最差解個體,本文提出傾向性判斷公式:

Q(Xbest),Q(Xworst),Q(X)分別表示最優個體的模塊度、最差個體的模塊度、當前個體的模塊度,bestGap表示當前個體模塊度和最優模塊度的差值,worstGap表示當前個體模塊度和最差模塊度的差值,Gap表示當前個體在最優個體和最差個體之間的傾向性.當Gap＞0,則該個體傾向于最差個體,當Gap＜0,則傾向于最優個體.

(2)最優相似率

最優相似率即當前個體向量與最優解個體向量相同節點個數占全部元素的比率,其計算公式如下:

其中,Xd表示當前個體,表示最優解個體,n表示節點個數,d表示該個體中元素的序數,Θ表示同或,如果Xd和相等,則結果為1,否則為0.

(3)模塊度函數的局部更新

為了使得模塊度函數最大化,我們定義一種模塊度函數的局部貪心更新方式.通過依次遍歷該節點的鄰居節點,選擇模塊度最大化的鄰居節點進行替代.第t+1 代的個體更新用式(7)表示如下:

其中,X表示一個個體向量解(向量的元素對應圖中的節點),t表 示第t次 迭代,Q為對應式(1)的模塊度函數,Neighbord={n1,n2,···,nk}為 節點d的鄰居節點集合.式(7)表示取最大模塊度的鄰居節點作為下一代個體的節點更新.

(4)貪心選擇

當個體更新后,選取適應度較高的個體作為下一代的父種群個體,即貪心選擇.該操作相當于遺傳中的“優勝劣汰”,同時和Jaya 算法保持了一致的篩選策略,對比非貪心選擇策略,即優化后的個體不進行比較直接作為下一代,選用貪心選擇策略保證了下一代種群中每一個個體都至少不會變得更差,從而使解的平均質量更優,加快了收斂速度.

基于上述幾個概念,下面給出Jaya 算法離散化策略,離散化的Jaya 算法稱作DJaya 算法.DJaya 算法通過式(3)～式(5)來判斷種群中每個個體是靠近種群的最優解還是最差解,從而對種群中的個體離散化為兩類.①對于種群中更靠近最差解的個體,采用類似標簽傳播的方法依次對該個體的各個節點進行更新操作,該操作提高了較差個體的多樣性和精度,達到了進一步遠離最差解的效果,有利于DJaya 算法的全局探索性.②對于種群中靠近最優解的個體,先對該個體向量采用式 (6)計算出最優相似率,然后基于相似率對該個體的某些節點采用式 (7)進行局部更新,該操作有利于加快種群的優化速度,使整個種群更加靠近最優解,從而有利于增強DJaya 算法的局部開發性.

DJaya 算法通過判定種群中個體的傾向性來平衡各個階段的全局搜索能力和局部搜索能力,當個體靠近最優個體解,采取類似標簽傳播方法進行更新,相當于重新定義初始解,有利于探索出最優解,體現了全局搜索能力;當算法靠近最有個體解,采取了基于局部函數的更新方法,進一步優化了精英解,加快了算法收斂,體現了局部搜索能力.

(5)隨機抖動

為了更進一步避免算法陷入全局較優,我們加入了隨機抖動操作,相當于遺傳算法中的變異操作,是一種局部開發,有利于增加搜索方向,增大搜索空間.當連續迭代幾次后種群中的個體沒有得到優化,則執行隨機抖動,即隨機選擇該個體節點的某個鄰居節點值替代當前個體節點值.該操作設置了一個較小的抖動率,一方面保持原始種群的較優性,另一方面增加多樣性.

2.3 DJaya 算法流程

綜上,通過選取模塊度為適應度函數,采用LAR表示種群的劃分和類似LPA 策略進行初始化,然后在每代種群更新中采用離散化的DJaya 算法進行不斷的迭代優化,選取適應度高的個體作為下一代的父種群.算法DJaya 的描述如算法1.

算法1.DJaya 算法輸入:G,M,T,R//G表示網絡,M表示種群規模,T表示最大迭代次數,R表示隨機抖動率輸出:Result// 網絡社區結構1.Begin 2.P←LAR 進行表示,并用LPA 初始化父種群P(new)←? 3.//子種群初始化為空集4.Fori= 1:T5.Forj= 1:M6.Gap(j)← 利用式(3)～(5)判斷個體傾向性7.IfGap(j)＞ 0 //靠近最差個體8.P(new)←LPA(j)//類似標簽傳播法更新9.Else //靠近最優個體10.If rand ()＜ similarRate (j)//滿足最優相似率11.P(new)←利用公式(7)更新P(new)←P(new)∪P12.//更優個體進入下一代13.Ifrand()＜RP(new)←14.隨機抖動15.End ForP←P(new)16.//生成新的種群17.End ForResult←18.選擇P中適應度最高的個體19.End

下面分析DJaya 算法的時間復雜度.假設網絡中G=(V,E)的節點個數為n,種群規模為M,迭代次數為T.使用局部鄰接表示法初始化種群時,對于每個節點隨機選擇其中一個節點值賦值,設網絡的節點平均度為,則該初始化種群的其時間復雜度為O ();利用DJaya 算法離散策略對種群進行更新時,計算模塊度函數的時間復雜度為 O(Mn2),如果個體靠近最差解,則利用類似標簽傳播法進行更新,其時間復雜度為O(T M×(+n2));如果個體靠近優解,則采用局部函數進行更新,其時間復雜度為因此,DJaya 算法的時間復雜度為

3 實驗結果與分析

實驗平臺為Windows 10 系統,Intel(R)Core(TM)i5 CPU 1.8 GHz,內存8.0 GB.實驗數據包括不同參數情況下的擴展GN Benchmark[33]人工網絡 和4 個經典真實網絡.實驗中將DJaya 算法與LPA,FMM,BGLL等經典貪心算法,以及智能算法如ACO、LGA、IDDE、CC-GA 進行比較.為了減少統計誤差,每個算法在每個算例上獨立運行20 次,取平均值作為算法運行的結果.

按照慣例,針對人工網絡,已知其真實社區結構,實驗中僅比較各算法的標準互信息值;對于真實的網絡,我們比較不同算法的模塊度值[34].

標準互信息(Normalized Mutual Information,NMI)[35]常用來評價算法的劃分結果與網絡真實劃分結果的吻合程度.對于網絡的的兩種劃分A和B,它們之間的互信息定義如下:

其中,N表示節點個數.CA表示劃分A中網絡的社區數目,CB表示劃分B中網絡的社區數目,Ci,表示第i行元素和,C,j表示第j列元素之和,Ci,j表示劃分A中的社區i和劃分B中的社區j兩者之間的交集中含有的節點數目.如果A=B,則NMI值為1,如果A劃分和B劃分完全不同,則NMI值為0.

3.1 人工網絡比較實驗

為了分析DJaya 算法的優化性能,我們在擴展GN Benchmark 上進行了實驗分析.該人工網絡的社區結構已知,它含有128 個節點,共劃分為4 個不同的社區,每個社區有32 個節點,社區中每個節點的平均度數為16,如表2.網絡中的混合參數u主要用于確定某一社區中任意一個節點與其他社區的節點之間共享邊的數量,當混u＜ 0.5 時,網絡中的社區結構較為明顯,但隨著u的增大,網絡中的社區結構將變得越來越模糊,性能一般的算法難以檢測出網絡中存在的社區結構,從而可以區分不同算法的性能,比較結果如圖4.

表2 人工網絡的參數(GN benchmark)

由圖4可見,當u＜0.35時候,各個算法的NMI值達到了1,都能準確找出社區結構;當u=0.4,BGLL、ACO 算法的NMI開始下降;當u=0.45,LGA、IDDE、DJaya 算法能找到和真實社區完全一樣的社區結構,相比其它算法,它們較為穩定;當u=0.5,此時網絡的社區結構已經非常模糊,DJaya 算法仍能準確劃分接近80%的社區結構,表明DJaya 算法的一定優越性,總體來說DJaya 算法在人工網絡上優于其它算法.

圖4 各種算法劃分精度的比較

3.2 真實網絡比較實驗

真實的復雜網絡與人工網絡相比,有不同的拓撲屬性.這里采用了4 個被廣泛使用的真實網絡作為實驗數據集,其點數和邊數見表3.Karate[36]網絡是通過對一個美國大學空手道俱樂部進行觀測而構建出的一個社會網絡.Dolphins[37]是由Lusseau 等使用長達7年的時間觀察新西蘭Doubtful Sound 海峽62 只海豚群體的交流情況而得到的海豚社會關系網絡.Polbooks[6]是由Amazon 上銷售的美國政治相關書籍頁面上建立起來的網絡.Football[1]網絡是根據美國大學生足球聯賽而創建的一個復雜的社會網絡.

表3 4 個真實網絡數據的參數

表3中,football 真實社區的劃分效果與DJaya 算法劃分的效果圖分別如圖5和圖6.

如圖5,football 對應的真實社區有12 個,圖6采用DJaya 算法劃分的社區則有10 個,可以看出DJaya算法合并了一些較小的社區,保持了大部分社區劃分是和真實社區一致,文獻[2]認為這種劃分是合理的.

表4給出了各種算法在4 個標準真實網絡算例上所得的模塊度值.對于算例Karate,CC-GA、LGA、DJaya 都達到0.4198 最優值[38];在算例Dolphins 上DJaya 算法取得了最高的模塊度值;在算例polbooks上,DJaya 和LGA 都達到了該數據集的理論最高值0.5272[39];在算例football上,LGA、IDDE、DJaya 都表現良好,達到了最優值[39].綜上所述,在4 個算例上,DJaya 算法展現出較明顯優勢.

圖5 真實的football 的社區(12 個社區)

圖6 DJaya 劃分的football 社區(10 個社區)

4 總結

本文提出的DJaya 算法用于求解復雜網絡社區發現問題,該算法采用局部鄰接表示法的編碼方式對種群進行社區表示,并用標簽傳播思想進行初始化,然后借鑒連續空間Jaya 算法的靠近最優解、遠離最差解的基本思想,先判斷種群個體的傾向性,針對靠近最差解采用標簽傳播思想更新種群,靠近最優解采用局部模塊度函數更新種群,最后采用貪心選擇策略生成下一代種群.DJaya 算法實現簡單,容易理解,具有全局搜索能力和局部開發能力.通過在真實網絡和人工網絡上的實驗對比發現,該算法具有較好的優化能力和魯棒性,達到了較高的社區發現精度且自動確定社區個數.該算法適用于非重疊、靜態社區,考慮到模塊度作為優化函數的局限性[39],今后將改進算法的目標函數,或建立多目標優化函數,同時考慮擴展算法的適應范圍,增大數據規模,應用在重疊、動態社區發現問題.

表4 各種算法在不同網絡中的模塊度對比