基于多階局部度數峰值點的局部社區發現算法

王得翊， 焦澳琛， 陳音拿， 安靜， 康琦， 汪鐳

(1.同濟大學 控制科學與工程系， 上海 201804；2.上海應用技術大學 電氣與電子工程學院， 上海 201418)

0 引言

隨著科學研究對象規模的不斷擴大和結構的進一步復雜，針對復雜網絡的研究已經成為生物學、社會學、經濟管理學、流行病學、統計物理學等諸多學科前沿領域的研究熱點之一[1]。復雜網絡一般具有社區結構，即復雜網絡往往可以被自然地分成一系列節點組，同一組的節點一般更具有相連相關的傾向[2]。社區發現能夠檢測復雜網絡中的社區結構，是分析復雜網絡、挖掘網絡信息的有力方法，例如,通過研究蛋白質中氨基酸的連接關系發現功能模塊和預測, 根據節點信息熵相似性和社區信息熵穩定性進行洗錢社區發現，因而自Kernighan-Lin算法[3]被完善并被用于圖分割始，社區發現算法有了長足的發展。

傳統的社區發現算法已知全局網絡信息對網絡中所有節點進行社區劃分，分為非重疊社區發現算法和重疊社區發現算法。非重疊社區發現算法的結果中每個節點只能屬于一個社區，例如，基于邊介數的GN算法[4]、基于模塊度概念FastUnfolding算法[5]和基于LeaderRank排序的標簽傳播算法[6]等?，F實中復雜網絡社區結構并非一個節點僅屬于一個社區，例如,微博用戶關注內容廣泛難以被分入一個社區[7]。重疊社區發現算法可以允許節點同時屬于多個社區，例如,基于完全子圖的派系過濾算法[8]等。傳統的社區發現算法需要事先知道全局網絡的信息，網絡規模巨大，不易獲知全局網絡信息。

局部算法[9]選擇種子節點并以一定的方式擴張形成社區。在種子節點選取問題上，LFM算法[10]主張以隨機選擇的方式確定種子節點；基于圖遍歷的局部社區發現算法[11]將度數較低的節點作為種子節點；提出局部度數中心點的概念，主張以局部度數最高的節點作為種子節點[12]，但由于種子節點選擇標準嚴苛，算法不能較為全面地感知各個社區的關鍵節點，發現社區的穩定性略有欠缺。

本文的主要貢獻：(1)在局部度數中心點的基礎上，提出了多階局部度數峰值點的概念，并將其作為種子節點的選擇依據。(2)提出了基于多階局部度數峰值點的種子節點選擇方法和局部社區檢測框架。

1 相關工作

1.1 局部社區擴張算法

Clauset[13]提出了衡量局部節點組社區結構顯著度的標準，即局部模塊度。算法從一個給定節點作為初始節點組開始，不斷將節點組的鄰居節點加入節點組并更新局部模塊度，直到加入任何鄰居節點都不能使模塊度值增大，得到擴張的局部社區。

羅峰等[14]提出了基于模塊度的擴張算法。先將能使子圖模塊度增大的相鄰節點加入子圖，再將子圖中能使模塊度值進一步增大的節點刪去，直至任何節點的加入和刪去都不能使子圖的模塊度值增大為止，得到擴張社區。

Bagrow等定義了與給定初始節點間最短路徑等于L的節點集合L-shell[15]及其總出度KL。L-shell不斷擴張，直至KL增長速度小于給定閾值α，擴張停止，L-shell已覆蓋節點構成擴張社區。

1.2 局部度數中心點框架

對于網絡G中的節點v，如果節點v的度數不小于它的任何一個鄰居節點，則稱節點v為“局部度數中心點”。從初始節點開始找到與初始節點最近的“局部度數中心點”，并以此為新的初始節點擴張得到局部社區。

2 基于多階局部度數峰值點的局部社區發現算法

網絡中度數最高的節點往往具有與其他節點緊密的聯系，以它為關鍵節點進行擴張能達到較好的擴張社區效果，而一個社區內的關鍵節點度數可能不大。規模大、節點間聯系緊密的社區內往往囊括了全網絡大部分度數較高的節點，局部度數中心點是基于此建立的關鍵節點概念。

局部度數中心點框架下容易出現：某節點是其所在社區的關鍵節點，但與它的所有鄰居節點相比，它并非度數最高的節點，這是因為度數高于它的節點屬于其他的社區，如圖1所示。

圖1 局部度數中心點概念失效

圖1中,有{1,7,8,9,10,11}和{2,3,4,5,6}兩個社區，節點1和2分別是兩個社區的關鍵節點。按照局部度數中心點的概念，節點2并非關鍵節點，這是因為它的鄰居節點1的度數比它高，而節點1屬于另外的社區。

要避免上述情況，首先要放寬標準，即在尋找關鍵節點時，允許其鄰居節點中有一些度數高于它，稱這樣的節點為準峰值點。

定義1：對于網絡G中的節點v，如果節點v的鄰居節點中有t個節點的度數高于它，則稱節點v為“t階準峰值點”。

一般地，處于同一社區內的節點間聯系相對緊密，其內部的同階準峰值點之間更有可能相互連接，不大可能成為社區的關鍵節點；相對孤立的準峰值點更有可能成為社區的關鍵節點,如圖2所示。

(a)

(b)

據此給出關鍵節點的定義。

定義2：對于網絡G中的節點v，如果節點v是“t階準峰值點”，且它的鄰居節點中沒有其他“t階準峰值點”，則稱節點v為“t階局部度數峰值點”。

算法從給定節點出發，不斷檢測鄰居節點，直到發現第一個符合要求的多階局部度數中心點，則以該節點為種子節點，按照既定方法擴張得到局部社區。若發現多個符合要求的節點，則任意選取一個階數最低的作為種子節點。

給定一個階數靈敏度系數T，只有被發現的峰值點的階數不大于T才稱為找到種子節點。一般地，靈敏度系數越小，算法精確度越高，但穩定性越低。

3 實驗分析

采用LFR基準網絡數據集[16]作為研究對象。LFR基準網絡生成后節點的社區分布已知，故使用F值作為對給定節點社區劃分效果評價指標。

3.1 峰值點階數靈敏度系數T的選定

網絡的規模越大，各節點的度數普遍越高，LFR基準網絡的混合參數μ越大，對應現實中網絡的社區越不明顯，探究不同網絡規模與不同混合參數對靈敏度系數的要求是很有必要的。

(1) 網絡規模與靈敏度T的關系

固定LFR社區的混合參數為μ=0.1，生成社區規模為1 000、2 000、3 000個節點的三個網絡。網絡參數如表1所示。

表1 網絡規模與靈敏度T關系實驗參數

靈敏度系數由0開始逐漸增長，建立全局社區劃分精確度-靈敏度系數關系,如圖3所示。

圖3 不同規模網絡全局社區劃分精確度與峰值點階數靈敏度系數的關系

在網絡規模相同的情況下，加入多階局部度數峰值點較之只有局部度數中心點的情況，劃分精度得到了明顯改善，選取的靈敏度系數T越大，劃分精度越高。

(2) 網絡混合參數與靈敏度T的關系

將LFR社區的社區規模固定在1 000個節點，生成混合參數為μ=0.1、0.2、…、0.5的五個網絡。網絡具體參數如表2所示。

表2 網絡混合參數與靈敏度T關系實驗參數

對于不同的靈敏度建立全局社區劃分精確度-靈敏度系數關系,如圖4所示。

混合參數越大，社區結構越不明顯的網絡，其社區劃分的精準度越低。隨著靈敏度系數的提高，不同混合參數的網絡之間的差異并未被消除。網絡混合參數相較于規模對社區劃分質量影響更大。

3.2 算法分析

為說明本算法框架的優勢，將其與局部度數中心點框架進行對比實驗。實驗網絡具體參數如表3所示。

表3 對比實驗網絡參數

對網絡中的每個節點運行算法，并將所得局部社區與真實社區進行對比，得到節點在指定算法下的F值。F-節點關系如圖5所示。

(a) LMD

三種擴張算法在兩種框架下的F值對比如表4所示。

表4 兩種框架下各節點F值平均值對比

由表4可知，基于多階峰值點選取種子節點的算法效果較之局部度數中心點有明顯的提高。

4 總結

本文基于社區內關鍵節點度數較高和關鍵節點間聯系松散對社區結構的認識，提出了多階局部度數峰值點的概念及社區發現算法，精確度更高，穩定性更強。在一定范圍內，選取的階數靈敏度系數越大，算法精確度越高。然而，隨著階數的增大，其峰值特性逐漸弱化，帶動算法精確度提高的邊際效益遞減，不穩定性增加。當階數足夠大時，算法退化為以既定節點為擴張初始節點的普通算法。

本文為解決局部社區發現種子節點選取問題，提供了尋找多階局部度數峰值點的框架。以多階局部度數峰值點為種子節點進行擴張能在一定程度上改善原局部擴張算法的性能。該算法無須得知全局網絡的信息，僅通過初始給定節點便能自主探索網絡，有著較低的計算復雜度，有助于復雜網絡局部結構的研究。在同一網絡中研究多個節點的社區歸屬時，本算法不限制各節點歸屬社區的數量，有助于探索復雜網絡中的重疊社區。