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

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

0 引言

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

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

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

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

1 相關工作

1.1 局部社區(qū)擴張算法

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

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

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

1.2 局部度數(shù)中心點框架

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

2 基于多階局部度數(shù)峰值點的局部社區(qū)發(fā)現(xiàn)算法

網(wǎng)絡中度數(shù)最高的節(jié)點往往具有與其他節(jié)點緊密的聯(lián)系，以它為關鍵節(jié)點進行擴張能達到較好的擴張社區(qū)效果，而一個社區(qū)內(nèi)的關鍵節(jié)點度數(shù)可能不大。規(guī)模大、節(jié)點間聯(lián)系緊密的社區(qū)內(nèi)往往囊括了全網(wǎng)絡大部分度數(shù)較高的節(jié)點，局部度數(shù)中心點是基于此建立的關鍵節(jié)點概念。

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

圖1 局部度數(shù)中心點概念失效

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

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

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

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

(a)

(b)

據(jù)此給出關鍵節(jié)點的定義。

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

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

給定一個階數(shù)靈敏度系數(shù)T，只有被發(fā)現(xiàn)的峰值點的階數(shù)不大于T才稱為找到種子節(jié)點。一般地，靈敏度系數(shù)越小，算法精確度越高，但穩(wěn)定性越低。

3 實驗分析

采用LFR基準網(wǎng)絡數(shù)據(jù)集[16]作為研究對象。LFR基準網(wǎng)絡生成后節(jié)點的社區(qū)分布已知，故使用F值作為對給定節(jié)點社區(qū)劃分效果評價指標。

3.1 峰值點階數(shù)靈敏度系數(shù)T的選定

網(wǎng)絡的規(guī)模越大，各節(jié)點的度數(shù)普遍越高，LFR基準網(wǎng)絡的混合參數(shù)μ越大，對應現(xiàn)實中網(wǎng)絡的社區(qū)越不明顯，探究不同網(wǎng)絡規(guī)模與不同混合參數(shù)對靈敏度系數(shù)的要求是很有必要的。

(1) 網(wǎng)絡規(guī)模與靈敏度T的關系

固定LFR社區(qū)的混合參數(shù)為μ=0.1，生成社區(qū)規(guī)模為1 000、2 000、3 000個節(jié)點的三個網(wǎng)絡。網(wǎng)絡參數(shù)如表1所示。

表1 網(wǎng)絡規(guī)模與靈敏度T關系實驗參數(shù)

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

圖3 不同規(guī)模網(wǎng)絡全局社區(qū)劃分精確度與峰值點階數(shù)靈敏度系數(shù)的關系

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

(2) 網(wǎng)絡混合參數(shù)與靈敏度T的關系

將LFR社區(qū)的社區(qū)規(guī)模固定在1 000個節(jié)點，生成混合參數(shù)為μ=0.1、0.2、…、0.5的五個網(wǎng)絡。網(wǎng)絡具體參數(shù)如表2所示。

表2 網(wǎng)絡混合參數(shù)與靈敏度T關系實驗參數(shù)

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

混合參數(shù)越大，社區(qū)結(jié)構(gòu)越不明顯的網(wǎng)絡，其社區(qū)劃分的精準度越低。隨著靈敏度系數(shù)的提高，不同混合參數(shù)的網(wǎng)絡之間的差異并未被消除。網(wǎng)絡混合參數(shù)相較于規(guī)模對社區(qū)劃分質(zhì)量影響更大。

3.2 算法分析

為說明本算法框架的優(yōu)勢，將其與局部度數(shù)中心點框架進行對比實驗。實驗網(wǎng)絡具體參數(shù)如表3所示。

表3 對比實驗網(wǎng)絡參數(shù)

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

(a) LMD

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

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

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

4 總結(jié)

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

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