進化譜分算法檢測動態網絡社團結構

付立冬， 馬小科， 聶靖靖

(1. 西安科技大學 計算機學院，陜西 西安 710054;2. 西安電子科技大學 計算機學院，陜西 西安 710071)

現實世界中的許多復雜系統可用網絡來描述，復雜網絡中的節點表示系統中的實體，節點之間的連線表示實體間的相互作用關系．在社會網絡[1]、信息網絡[2]、生物網絡[3-4]等復雜網絡中存在著社團結構．例如，在科學家合作網絡中，社團結構表示有著相同或相似研究興趣的科學家群體; 在Web頁面網絡中，社團結構表示有著相似或相近主題的一組頁面; 在蛋白質相互作用網絡中，社團結構表示提供某種功能的蛋白質集合，對分析生物機理及進程有著非凡的意義．這些社團結構為研究整個復雜系統的結構和功能提供了客觀依據．

目前，有許多算法基于模塊評估函數Q及模塊密度函數D優化以檢測靜態復雜網絡中的社團結構[5-6]．但是，現實世界的網絡不總是靜態的，而是處于動態進化中[7-9]．例如，在科學家合作網絡中，隨著時間推移，由于科學家的研究興趣和方向發生改變，相應的社團結構也會發生變化; 在疾病網絡中，由于癌細胞的遷移或分裂導致癌細胞組成社團結構發生改變．在動態復雜網絡中，由于社團中節點的增加或移除而發生變化的社團稱為動態社團．因此，動態網絡中的社團結構檢測更能揭示復雜網絡的特性、演變規律及發展趨勢．如何檢測動態網絡中的社團結構已成為當前的熱點和難點問題．有許多方法可檢測動態復雜網絡的社團結構，其中進化方法成為運用廣泛的一種策略[6，10]．該策略在一種時間平滑框架下，在每個時間步上生成聚類．這個時間平滑框架假定在一段很短的時間間隔內社團的改變不明顯，且最好的社團結構應當通過同時考慮當前時刻和前一時刻的社團結構來獲得．

為有效地在動態網絡中檢測社團結構，筆者將模塊函數Q及模塊密度函數D在時間平滑框架下進行譜分，以便能夠通過進化譜分方法檢測動態復雜網絡的社團結構，并提出了用進化譜分方法檢測動態社團結構的算法．

1　相關工作

1.1　符號定義

1.2　模塊函數與模塊密度函數

(1)

其中，L(Pct，Pct)表示t時刻社團i中連邊的數目，L(V，V)表示網絡Gt中邊的總數目．Q值越大，表示網絡中社團劃分越好．因此，對L(Pct，V)一個網絡，檢測社團問題可直接轉化為求函數Q值的最大優化問題．

模塊密度函數D可定義為

(2)

1.3　進化方法

進化方法使用了一種時間平滑框架檢測動態網絡社團結構．同其他類似的方法一樣，通過調節權重參數獲得兩個連續時間上最優的目標[11-12]．進化方法可表達成

C=λCS+(1-λ)CT,

(3)

其中，CS描述了在當前時刻獲得的社團結構是如何好，而CT描述了當前時刻的社團結構與前一時刻的社團結構如何相似．λ是權重參數，取值在[0，1]之間．當λ=0 時，獲得的社團結構僅為前一時刻的社團結構；當λ=1 時，獲得的社團結構僅為當前時刻的社團結構．

2　函數進化譜分方法

2.1　模塊Q函數進化譜分

首先在進化時間平滑框架下優化模塊函數Q，檢測動態社團需要的整個成本為

CQ=λCSQ+(1-λ)CTQ=λQt|Xt+(1-λ)Qt-1|Xt,

(4)

其中，CSQ表示當前時刻模塊性度量，CTQ表示歷史時刻模塊性度量，Qt-1|Xt表示社團Xt在Gt下的模塊密度值．

為解決CQ作為矩陣跡的優化問題，首先將式(4)中Qt|Xt變為矩陣跡的形式問題:

(5)

為了簡化，重寫Qt|Xt，有

其中，St為動態網絡t時刻的總邊數，可看成常數；dt∈Rn×1，其元素dit等于t時刻節點i的度．結果有

(7)

(8)

同理，式(4)中Qt-1|Xt作為矩陣跡的形式可描述為

(9)

將式(8)和式(9)代入式(4)中，有

(10)

因此，用Q函數檢測動態社團結構進化譜分后的最大優化問題可表達成

(11)

2.2　模塊密度D函數進化譜分

據相似推導，D函數在進化時間平滑框架下最大化可表達成

(12)

3　動態網絡社團結構檢測進化譜分算法

筆者提出了新的基于模塊函數和模塊密度函數檢測動態復雜網絡中社團結構的進化譜分算法．該算法基本框架是: 在最大化的CQ及CD值條件下，假設要在t時刻的動態網絡中尋求k個聚類中最優的社團結構．可通過計算得到相應矩陣的前k個特征向量．對于每一個變量c(2≤c≤k)，可采用傳統的迭代方法尋找最優的劃分c．詳細的進化譜分算法描述如下．

輸入R: 動態網絡;

(2) 對矩陣Mt，通過子圖迭代方法計算它的k個特征值對應的首個特征向量u1t，u2t，…，ukt．

(3) 構建一個矩陣Xt∈Rn×k，其元素為[u1t，u2t，…，ukt]T．

(4) 對每一個c(2≤c≤kt)值，重復做:

(a) 生成一個來自矩陣Xt的首個c列的矩陣Uct．

(b) 使用k均值方法或其他基于向量的聚類算法聚類Uct的行向量．對于c=1，社團僅是t時刻動態網絡本身．

(5) 重復步驟4中的(a)和(b)，當CQ或CD的值不再增大或達到最大迭代次數時，c的值就是t時刻網絡所對應的最優社團劃分數目．

(6) 返回．

4　算法檢驗

4.1　計算機合成動態網絡

該計算機合成的動態網絡是在網絡中社團結構形成和毀滅的基礎上構建的[13]．該動態網絡開始包含256個節點，劃分為4個社團結構，每個社團結構內包含64個節點．社團內每個節點的平均度為16，而且與社團外節點的連接邊數目為l，l為網絡拓撲調和參數，在實驗中可以調節．在t-1 時刻，從每個社團結構中隨機選擇8個節點；在t時刻，由隨機選擇出的節點組成一個新的社團結構，這個過程持續5個時間步．隨后，通過逆過程又將新社團結構中的頂點返回到原始社團中去，同樣持續5個時間步．因此，在10個時間步上，該動態網絡的社團結構數目分別為4，5，6，7，8，8，7，6，5，4．本實驗的目的在于檢測當進化時間平滑框架中的平衡參數λ以及參數l變化時，如何影響著筆者提出的進化譜分算法檢測動態網絡中社團結構的準確性．為檢驗算法在動態網絡中檢測社團結構的準確性，可應用歸一化互信息作為算法準確性的評判標準．歸一化互信息值在0和1之間，值越大，暗示算法準確性越高．

兩種函數的進化譜分算法在不同參數λ及l下檢測動態網絡社團的準確性分別如圖1和圖2所示．圖1和圖2說明了兩種算法具有相似的表現:當參數λ增大時，兩種算法的準確度都提升了．當λ= 0.8時，兩個算法的準確度最高．這是因為當λ增大時，CS的相對重要性加強，提升了算法的準確度．因此在實際中，通常取λ= 0.8．當參數l增大時，暗示了網絡中社團愈加變得模糊，因此算法將愈來愈難檢測．然而，從圖1和圖2可看出，當參數λ= 0.8時，無論在l=3 或l=5 時，兩種算法都有很好的準確度．

圖1　Q的進化譜分算法在不同λ及l下檢測動態網絡社團的準確性

圖2　D的進化譜分算法在不同λ及l下檢測動態網絡社團的準確性

4.2　手機通話網絡

該手機通話網絡(http://www.cs.umd.edu/hcil/VASTchange08/)是虛擬Paraiso移動成員之間的手機通話動態網絡，并在2006年6月運行了10天．在手機通話網絡中，將每個成員個體作為節點，成員之間的通話作為邊．每一天，一個手機通話網絡被構建．手機總數目是400．在該網絡中檢證筆者提出的算法檢測動態網絡中社團的正確率．

圖3　各種算法在手機通話網絡中的準確性比較

因為真實的社團結構未知，首先采用文獻[14]中的動態多目標遺傳算法(DYNamic Multi-Objective Genetic Algorithm，DYNMOGA)在這個動態網絡中發現社團結構，這些社團結構可看成是對真實網絡的劃分．動態多目標遺傳算法與筆者提出的算法在每一時刻之間的歸一化互信息值可看成算法的檢測社團準確性．如圖3所示，筆者提出的兩種譜分算法能很好地識別社團結構，準確性比動態多目標遺傳算法的高．特別地，Q函數的進化譜分算法及D函數的譜分算法得到的平均歸一化互信息值分別為0.63，0.64，而動態多目標遺傳算法得到的平均歸一化互信息值為0.48．

5　總　　結

以上研究了在進化時間平滑框架下對模塊函數及模塊密度函數進行優化的問題．通過兩種函數的優化進程，論證了模塊函數及模塊密度函數可在進化框架下作為進化譜分聚類方法檢測動態網絡中社團結構的理論可行性，在此理論上提出了檢測動態網絡社團結構的進化譜分算法．在計算機合成的動態網絡及真實世界網絡中檢驗了該算法的合理性及準確性，并與其他方法進行了比較．實驗結果顯示這種算法仍有很高的準確性．在將來的研究中，可把其他社團評價函數或圖劃分函數納入進化時間平滑框架下，并進一步研究它們的特性．

參考文獻：

[2]NEWMAN M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices[J]. Physical Review E, 2006, 74(3): 036104.

[3]YU L, WANG B B, MA X K, et al. The Extraction of Drug-disease Correlations Based on Module Distance in Incomplete Human Interactome[J]. BMC Systems Biology, 2016, 10(111): 532-548.

[4]GUO X L, GAO L, LIAO Q, et al. Long Non-coding RNAs Function Annotation: a Global Prediction Method Based on Bi-colored Networks[J]. Nucleic Acids Research, 2013, 41(2): e35.

[5]NEWMAN M E J. Modularity and Community Structure in Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582.

[6]WANG P Z, GAO L, MA X K. Dynamic Community Detection Based on Network Structural Perturbation and Topological Similarity[J]. Journal of Statistical Mechanics: Theory and Experiment, 2017, 2017(1): 013401.

[7]YANG Y J, YU J X, GAO H, et al. Mining Most Frequently Changing Component in Evolving Graphs[J]. World Wide Web, 2014, 17(3): 351-376.

[8]YANG C, ZHANG X, ZHONG C, et al. A Spatiotemporal Compression Based Approach for Efficient Big Data Processing on Cloud[J]. Journal of Computer and System Sciences, 2014, 80(8): 1563-1583.

[9]CRAENEL B D, BERXL G. Regulatory Networks Defining EMT During Cancer Initiation and Progression[J]. Nature Review Cancer, 2013, 13: 97-110.

[10] FOLINO F, PIZZUTI C. An Evolutionary Multiobjective Approach for Community Discovery in Dynamic Networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1838-1852.

[11]黃偉華, 馬中, 戴新發, 等. 一種特征加權模糊聚類的負載均衡算法[J]. 西安電子科技大學學報, 2017, 44(2): 127-132.

HUANG Weihua, MA Zhong, DAI Xinfa, et al. Fuzzy Clustering Based Load Balancing Algorithm with Feature Weighted[J]. Journal of Xidian University, 2017, 44(2): 127-132.

[12]李翠蕓, 王精毅, 姬紅兵, 等. 模型參數未知時的CPHD多目標跟蹤方法[J]. 西安電子科技大學學報, 2017, 44(2): 37-41.

LI Cuiyun, WANG Jingyi, JI Hongbing, et al. CPHD Multi-target Tracking Algorithm with Unknown Model Parameters[J]. Journal of Xidian University, 2017, 44(2): 37-41.

[13]MA X K, DONG D. Evolutionary Nonnegative Matrix Factorization Algorithms for Community Detection in Dynamic Networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(5): 1045-1058.

[14]FOLINO F, PIZZUTI C. An Evolutionary Behavior of Interaction Graph[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26: 1838-1852.