基于節點引力與魚記憶的社區檢測算法

孫福祿，王宇嘉，劉子怡

（上海工程技術大學電子電氣工程學院，上海 201620）

0 概述

在現實世界中，許多事物之間的關系可用復雜網絡表示。復雜網絡又分為重疊社區和非重疊社區，若節點只屬于一個社區，稱該社區為非重疊社區；反之則稱為重疊社區。目前的研究主要集中在非重疊社區檢測，而真實社交網絡中的社區通常是互相重疊的［1］，例如個體可能會同時屬于學校和社區，且其在網絡中也可能會同時存在于多個興趣小組中。因此，重疊社區的研究對于復雜網絡的結構分析具有重要意義［2］。

近年來，研究者發現，重疊社區與現實世界網絡的實際社區結構較為貼近，更具有研究意義，一些優秀的思想和方法被相繼提出。2004 年，NEWMAN等提出經典的基于分裂思想的社團檢測算法［3］。2005 年，PALLA 等提出基于派系過濾思想的重疊社區發現算法［4］。之后，研究者圍繞派系過濾提出了多種不同的方法，如FARKAS 等提出針對加權網絡的社區劃分算法［5］，KUMPULA 等提出快速的派系過濾算法［6］。2007 年，RAGHAVAN 等提出了著名的標簽傳播算法［7］。其后，研究者又提出了一些新的基于標簽傳播的改進算法，如SHANG 等提出了一種基于循環搜索核心節點并根據節點的相似度進行標簽傳播的方法［8］，文獻［9-10］提出了基于節點重要性進行社區檢測的標簽傳播方法，WANG 等提出了一種改進隨機策略［11］，提高了標簽傳播算法的穩定性，但這些算法都只是解決了非重疊社區的劃分問題。為了將標簽傳播算法應用到重疊社區檢測中，STEVE 等提出了基于標簽隸屬度的重疊社區檢測算 法［12］（Community Οverlap Propagation Algorithm，CΟPRA），XIE 等提出了一種基于speaker 和listener的標簽傳播算法［13］，SUN 等提出了一種基于優勢標記傳播 的網絡 重疊社 區檢測算法［14］，MA 等 在CΟPRA 的基礎上提出了一種采用PageRank 和節點聚類系數的標簽傳播重疊社區檢測算法［15］。這些算法都保持了標簽傳播算法可應用于大規模復雜網絡重疊社區檢測的優點，然而，并沒有解決LPA 隨機性強、準確性差的問題，不能有效提高社區劃分質量。

本文提出一種基于節點引力和魚記憶的社區檢測算法。通過節點質量計算節點信息熵，并將信息熵融入k-shell 算法中進行節點排序，同時根據節點與標簽間的引力，使用魚記憶節點標簽存儲策略實現標簽更新，從而解決標簽傳播隨機性造成社區劃分不穩定的問題，提高社區檢測的準確性。

1 基于節點引力與魚記憶的標簽傳播算法

當前的標簽傳播算法有近似線性的時間復雜度，但穩定性較差，即多次運行算法的社區發現結果差異很大。有效解決節點更新的隨機性及標簽選擇的不確定性，可以增強社區檢測的穩定性，提高社區檢測質量。本文提出的算法通過節點間的相互關系和節點標簽間的吸引力，解決節點排序與標簽傳播更新兩個重要步驟的隨機性與不確定性問題。

1.1 相關定義

設定圖G=(V,Ε)為復雜網絡，V=(ν1,ν2,…,νn)為圖的節點集，Ε表示圖的邊集，本文僅對無向圖結構進行研究。各節點在圖G中的度用ki表示，如圖1所示，則V=(ν1,ν2,…,ν9)，節點ν1的度k=3。

圖1 簡單圖結構Fig.1 Simple graph structure

定義1如果圖G中的節點u滿足：

則稱N(νi)為νi的鄰居節點集，ui為νi的鄰居節點。在簡單結構圖G中，有N(ν1)={ν2,ν4,ν8}。

定義2（節點質量）對于G=(V,Ε)，節點質量表示節點在圖中各點的質量大小，即重要程度。

一個節點可能是潛在的社區中心，即該節點具有以下特征：它與更多的鄰居節點連接，并且這些鄰居節點緊密地相互連接。一個節點與其鄰居節點連接得越緊密，這個節點與其鄰居節點形成的三角形就越多，這意味著如果一個節點具有較大的度，并且與其鄰居節點形成更多的三角形，那么該節點質量越好，成為社區中心的可能性越大。因此，本文采用三角形數量及節點的度來表示節點質量，定義為：

其中：Ti表示節點i所屬三角形的數量。

定義3（節點信息熵）節點信息熵表示節點獲取鄰居節點信息時消耗的能量，定義為：

信息熵由節點質量計算得到，用以表示該節點質量的強弱，即節點在圖中的中心度。

定義4（節點相似度）節點相似度反映了兩個相鄰節點之間的連接強度。

常用的相似度計算方法是用Katz 函數［16］進行相似度度量，然而它不能有效區分兩個節點之間的程度差異對節點相似性的影響。此外，該算法計算復雜度很高。受Jaccard 函數［17］的啟發，本文提出一個基于Jaccard 函數的相似性函數，如式（4）所示：

其中：α為相似度系數，α=0.2～1；Str為節點t、r之間的節點相似度；Dij為節點i到j最優路徑上的所有節點。

定義5（節點引力）節點j對i的引力大小定義為：

在標簽傳播過程中，不同鄰居節點間的引力大小是不同的，也就導致不同節點間的信息影響程度不同。本文用節點的信息熵Ε及相似度S來表示節點引力，并通過節點引力計算節點對不同節點標簽的引力大小，使得節點更新變得更加合理。Ε越大，S越大，節點對標簽的引力就越大。

定義6（節點記憶）模擬魚的記憶存儲特征，構建一個節點記憶集合：

其中：ld為每一次迭代節點i中的支配標簽；m為當前迭代次數。在標簽傳播中，復雜網絡節點極易造成標簽震蕩（即兩個標簽交替支配節點），使得網絡形成二分圖結構，嚴重時會導致無法檢測出社團。根據魚記憶特征，每個記憶存儲保存最近n次迭代的記憶，Mi出現n次記憶相同時，則視為節點標簽出現記憶振蕩，需要做進一步處理。魚記憶的存儲策略既解決了標簽振蕩，可保持算法的準確性，又減少了計算成本及內存的損耗。

1.2 標簽更新策略

本文借鑒文獻［12］的設計思想，使用g(c,u)來表示節點u對標簽的引力。引力足夠大時才能將標簽吸引到節點，迭代結束時，通過引力大小來生成節點的標簽集，從而檢測到重疊社區。

為了降低標簽傳播的復雜性，只傳播具有最大歸屬系數的優勢標簽［14］，同時避免隨機更新節點標簽帶來的社區檢測不穩定性，將節點熵融入k-shell算法［18］對節點進行排序，節點標簽將根據排序進行標簽更新。筆者認為，節點k值越高、信息熵越大，節點成為潛在社區中心的概率越大。因此，按升序對節點進行排序，可以使潛在社區中心的標簽傳播得足夠遠，以占據社區中心，然后社區可以獲得與其他社區邊界區域中的節點，從而檢測到更準確的社區結構。

在每一次迭代的開始，首先更新標簽及節點間引力大小，具體更新策略如下：

1）根據節點的k值，對節點u∈V進行分殼處理，將相同k值的節點分在同一殼內。

2）計算各節點信息熵，在每一k殼中進行升序排序，然后進行總體升序排序。

3）對于節點，在迭代開始更新標簽時，節點只接收各鄰居節點引力最大的標簽，并形成鄰居節點標簽集：

其中：lj→i=(cj,gj)；cj為節點j中受節點i引力最強的標簽；gj為該標簽受節點i引力的大小。根據節點排序獲取鄰居節點的支配標簽集Li（若是第一次迭代則獲取初始標簽），能夠保證所獲取標簽對節點的支配性，降低標簽的隨機性。

4）基于G和Li計算并更新節點i對標簽cj的引力大小：

7）將ld存儲在標簽記憶Mi中，更新Mi，當Mi內出現標簽記憶波紋，即該節點標簽只保存為ld將不再改變，且節點引力gd(c,j)=1。

CDA-GM 算法偽代碼如算法1 所示。

算法1CDA-GM

CDA-GM 算法的簡單圖應用如圖2 所示。

圖2 CDA-GM 的簡單圖應用Fig.2 Application of CDA-GM algorithm in simple graph

首先根據式（3）計算出的Εi進行排序，初始化標簽及標簽引力g=1，更新順序為2→6→1→3→5→7 →8 →9 →4，然后依據CDA-GM 的更新策略進行節點更新。

1.3 時間復雜度分析

一個具有n個節點的圖結構，在CDA-GM 的第一階段，時間復雜度分析如下：

1）Εi的時間復雜度：節點度數和三角形數量的時間復雜度分別為Ο(k)和Ο(k2)，即計算Εi的時間復雜度為Ο(n(k2+k)m)，m為相連節點數。

2）Sij的時間復雜度近似為Ο(knm+kn)。

3）利用Εi進行排序的時間復雜度約為Ο(2n)。

在CDA-GM 的第二階段，標簽迭代更新T次的時間復雜度為Ο(knT)。因此，算法總的時間復雜度為Ο(n(k2+k)m+kn(m+1) +2n+knT)。對于大型網絡n?m?k,T，總時間復雜度為Ο(nm+αn)，其中，α為常數。由上述可知，CDA-GM 各階段時間復雜度都趨近于線性，更適用于稀疏大規模網絡。

2 實驗結果與分析

為驗證CDA-GM 算法的性能，本文在真實數據集和人工數據集上進行社區檢測實驗，并與其他算法的社區檢測結果進行對比。

人工數據集由LFR 人工基準發生器［19］生成，采用標準化互信息（NMI）指標［20］進行對比評價。真實網絡大多情況下是不知其社區劃分的，因此，采用當前主流的拓展模塊度EQ［21］函數進行評價。

為更直觀地驗證CDA-GM 的實現效果，分別選取CΟPRA［12］、SPLA［13］、DLPA［14］、CΟPRAPC［15］算法進行對比。將CΟPRA、SLPA、DLPA 的參數分別設置為ν=2～9，r=0.1～0.5，in=1～8，使得各算法在指定的參數范圍內獲得最優評價指標。算法各運行20 次，并取最大值的平均值進行對比，減小算法隨機性對結果的影響。

2.1 實驗數據集

2.1.1 LFR 基準網絡

LFR 基準網絡由LANCICHINETTI 等［19］提 出，具有真實世界的網絡特性，且社區可調模塊度呈冪律分布。LFR 各參數意義如表1 所示，其中混合參數μ是衡量算法穩定性的重要指標，表示社區的模糊度，μ的值越大，則表示網絡連邊越多，社區結構越不清晰，社區檢測的難度越大。重疊社區的LFR 基準網絡參數設置如表2 所示。

表1 LFR 基準網絡參數說明Table 1 LFR benchmark network parameters description

表2 LFR 基準網絡參數設置Table 2 LFR benchmark network parameters setting

2.1.2 真實世界網絡

實驗用到的真實數據集有小數據集Karate、Dolphins和Football，以及大數據集Facebook、Ca-HepPh和Email-Enron。其中：小數據集來自于http：//wwwpersonal.umich.edu/～mejn/netdata/；大數據集 來自于http：//snap.stanford.edu/data/。具體數據參數如表3所示。

表3 真實網絡相關參數Table 3 Related parameters of the real network

2.2 評價指標

2.2.1 標準化互信息

標準化互信息（Normalized Mutual Information，NMI）指標［20］用于評價已知網絡結構的社區檢測。因為NMI 被用于比較各算法所獲取的社區劃分與基準網絡社區結構間的相似程度，所以只能被用于已知社區結構的網絡。NMI 指標定義如下：

其中，A、B分別是原有網絡社區結構以及算法檢測結果；Mi·表示網絡A中第i社區的節點數量；M·j為網絡B中第j社區的節點數；Mij表示兩個網絡之間的接近程度。NMI 在[0,1]之間的值越高，代表算法檢測出的社區結構越好。

2.2.2 社區模塊度

對于未知社區結構的真實網絡，算法劃分結果往往采用社區模塊度（即Q 指標）［22］作為劃分社區結構質量的評價指標。與文獻［22］提出的模塊度指標不同，因為本文研究的對象是重疊社區，所以采用的是重疊模塊度QE指標［21］，定義如下：

其中：m為網絡邊數總和；Ci為最終網絡結構的第i社區；各節點x、y的歸屬社區數為Οx、Οy；Axy為x、y節點間的鄰居矩陣元素。

2.3 算法參數分析

2.3.1 相似度參數分析

本文分別在LFR1 與真實世界網絡上進行對相似度參數α的實驗分析，CDA-GM 基于相似度參數不同值在LFR 人工網絡中的NMI 值如圖3 所示，真實世界網絡中相似度參數的取值如圖4 所示。

圖3 各α 值下LFR1 網絡NMI 值Fig.3 NMI value of LFR1 network under each α value

圖4 各α 值下真實世界網絡QE 值Fig.4 QE value of real world network under each α value

由圖3、圖4 可以看出：當α=0.8 時，CDA-GM 的表現明顯優于其他參數取值；當網絡結構變模糊時，α=0.8 仍能保持一個較好的穩定性及準確性；α=1雖然也能在結構模糊時保持一定的穩定性，但準確性上卻差了一些。

2.3.2 記憶存儲參數分析

為分析記憶存儲參數，將相似度參數設為0.8，在人工網絡LFR1 中對是否引入魚記憶存儲及記憶存儲個數進行實驗對比分析。CDA-GM 引入魚記憶存儲方法前后及不同記憶存儲個數在LFR1 人工網絡中的性能表現如圖5 所示。

圖5 各n 值 下LFR1 網絡的NMI 值Fig.5 NMI value of LFR1 network under each n value

在圖5 中，n=0 為沒有引入魚記憶存儲策略的CDA-GM 算法?？梢钥闯觯寒攏=0 和n=2 時，社 區劃分結果始終不如n＞2 的社區劃分結果，且在網絡結構越模糊時表現越明顯；當n=2 時，各節點只保存兩次迭代，而標簽交替出現兩次的情況易發生，導致節點的標簽多樣性嚴重下降，干擾了檢測準確性，社區劃分結果反而下降；當n＞2 時，NMI 值明顯大于沒有引入記憶存儲的NMI 值，說明引入n＞2 的記憶存儲后社區劃分結果更貼近原有的社區劃分，將網絡信息進行了更為完整準確的保存。同時由圖5 可以看出：n＞3 與n=3 的社區劃分結果基本相同。因此，在保證算法計算復雜度及內存占用耗費較低的前提下，本文選擇n=3，即將存儲次數為3 的標簽記憶引入CDA-GM 中。

2.4 LFR 人工網絡實驗結果分析

CDA-GM 及其他4 種比較算法在基準網絡LFR1、LFR2 和LFR3 中的NMI 評價結果如圖6 所示。

圖6 各算法在3 種LFR 基準網絡上的實驗結果Fig.6 Experimental result of each algorithm on three LFR benchmark networks

在圖6（a）中，調整μ值大小，其余參數固定?？梢钥闯觯寒敠?0.7時，其他算法已經基本檢測不出社區結果，CDA-GM 的NMI 值依然 能保持在0.2 以 上，且 當μ＜0.7時，CDA-GM 也始終能獲得比其他算法更好的NMI值，說明CDA-GM 在模糊圖上的社區劃分能力更強。

在圖6（b）中，調整Οm值大小，其余參數固定?？梢钥闯觯涸诓煌痬值下，CDA-GM 具有良好適應性。由于CDA-GM 的標簽引力設置，節點最多只能擁有3 個標簽，因此，當Οm≥4 時，CDA-GM 的NMI值下降較快。但相比于其他算法，CDA-GM 仍能保持一個較優的NMI 值，說明在結構復雜的網絡中，CDA-GM 仍能獲得較好的社區劃分結果。

在圖6（c）中，調整Οn的值，控制其他參數不變?？梢钥闯觯弘S著Οn值增大，社區檢測的難度逐漸增大。當Οn=3 500 時，除了SLPA 能保持一個較好的適應性，CDA-GM 仍能擁有最高的NMI 值，即使是在較多重疊節點的網絡中，CDA-GM 仍能獲得較好的社區劃分結果。

本文選取LFR3 中Οn=2 000 的基準網絡，將各算法在較復雜網絡上進行社區檢測穩定性對比，結果如圖7 所示?？梢钥闯觯篊DA-GM 的穩定性明顯優于CΟPRA、SLPA 和DLPA；CΟPRAPC 的穩定性較好，但極值相差較大。

圖7 各算法穩定性對比Fig.7 Stability comparison of each algorithm

圖8 顯示了各算法在LFR4 人工網絡上的時間耗費?？梢钥闯觯篋LPA 所用的時長最短，SLPA 與CΟPRA 相當，這是因為DLPA 的時間復雜度為Ο(Tm)，其中m是網絡中的邊數；而CΟPRA 與SLPA的時間復雜度分別為其中，T為迭代次數，ν為社區數量。圖8 中因LFR4 網絡結構較為簡單，當社區規模增大時，邊的數量相比于節點數較小，DLPA 算法時間耗費也就較小。而CΟPRAPC 的時間復雜度為Ο((m+n)/c)，其中，c為聚類系數，CDA-GM 與CΟPRAPC 的時間耗費相比于基線方法略高，但與其他4 種算法相比，CDA-GM 獲得了較好的準確度和穩定性，這表明CDA-GM 在保持一個接近線性時間復雜度的前提下，大幅提高了標簽傳播算法的社區檢測能力。

圖8 LFR4 網絡數據集上的運行時間Fig.8 Running time on LFR4 data sets

算法劃分的社區與原有社區的相似程度，也經常用于輔助評價社區檢測結果。表4 為各算法在LFR1 上獲取的社區數量，其中，Nreal為數據集中的原有網絡數量。可以看出，CDA-GM 能夠獲得較好的社區劃分結果，與原有社區較為接近，而CΟPRA、CΟPRAPC 在μ=0.4 時，已經無法檢測社區。

表4 各算法劃分社區數Table 4 Number of divided communities of each algorithm

2.5 真實世界網絡實驗結果分析

將5 種算法分別應用到真實世界數據中，對比經過20 次重復實驗取得的平均值以及標準差值如表5、表6 所示，其中，最優值以粗體顯示，CΟPRA、SLPA 及DLPA 算法調整參數取最優結果。

表5 各算法值對比Table 5 Comparison of value of each algorithm

表5 各算法值對比Table 5 Comparison of value of each algorithm

表6 各算法值對比Table 6 Comparison of value of each algorithm

表6 各算法值對比Table 6 Comparison of value of each algorithm

3 結束語

為提高社區檢測的準確性和穩定性，本文提出一種基于節點引力與魚記憶的社區檢測算法CDA-GM。使用融入節點信息熵的k-shell 排序策略，同時利用節點間的引力選擇標簽。在此基礎上，引入魚記憶的節點標簽存儲策略避免出現標簽震蕩。實驗結果表明，該算法在LFR 人工基準網絡和真實世界網絡中能獲得較好且穩定的NMI 值和社區模塊度，檢測性 能優于CΟPRA、SLPA、DLPA 和CΟPRAPC 算法。在后續研究中，擬將本文算法結合時間參數應用到動態的社區檢測中，進一步提高算法的實用性。