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

(1.同濟(jì)大學(xué) 控制科學(xué)與工程系， 上海 201804；2.上海應(yīng)用技術(shù)大學(xué) 電氣與電子工程學(xué)院， 上海 201418)

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

圖1中,有{1,7,8,9,10,11}和{2,3,4,5,6}兩個(gè)社區(qū)，節(jié)點(diǎn)1和2分別是兩個(gè)社區(qū)的關(guān)鍵節(jié)點(diǎn)。按照局部度數(shù)中心點(diǎn)的概念，節(jié)點(diǎn)2并非關(guān)鍵節(jié)點(diǎn)，這是因?yàn)樗泥従庸?jié)點(diǎn)1的度數(shù)比它高，而節(jié)點(diǎn)1屬于另外的社區(qū)。

要避免上述情況，首先要放寬標(biāo)準(zhǔn)，即在尋找關(guān)鍵節(jié)點(diǎn)時(shí)，允許其鄰居節(jié)點(diǎn)中有一些度數(shù)高于它，稱(chēng)這樣的節(jié)點(diǎn)為準(zhǔn)峰值點(diǎn)。

定義1：對(duì)于網(wǎng)絡(luò)G中的節(jié)點(diǎn)v，如果節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)中有t個(gè)節(jié)點(diǎn)的度數(shù)高于它，則稱(chēng)節(jié)點(diǎn)v為“t階準(zhǔn)峰值點(diǎn)”。

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

(a)

(b)

據(jù)此給出關(guān)鍵節(jié)點(diǎn)的定義。

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

表1 網(wǎng)絡(luò)規(guī)模與靈敏度T關(guān)系實(shí)驗(yàn)參數(shù)

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

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

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

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

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

表2 網(wǎng)絡(luò)混合參數(shù)與靈敏度T關(guān)系實(shí)驗(yàn)參數(shù)

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

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

3.2 算法分析

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

表3 對(duì)比實(shí)驗(yàn)網(wǎng)絡(luò)參數(shù)

對(duì)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)運(yùn)行算法，并將所得局部社區(qū)與真實(shí)社區(qū)進(jìn)行對(duì)比，得到節(jié)點(diǎn)在指定算法下的F值。F-節(jié)點(diǎn)關(guān)系如圖5所示。

(a) LMD

三種擴(kuò)張算法在兩種框架下的F值對(duì)比如表4所示。

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

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

4 總結(jié)

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

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