皇甫斐斐，楊 陽，鄧曉懿,3

(1.華僑大學(xué)外國語學(xué)院,福建 泉州 362021；2.華僑大學(xué)現(xiàn)代應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心,福建 廈門 361021；3.新澤西州立羅格斯大學(xué)羅格斯商學(xué)院,新澤西 紐瓦克 07102)

1 引言

社區(qū)是構(gòu)成復(fù)雜社會(huì)網(wǎng)絡(luò)的重要單元結(jié)構(gòu)，復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)有助于揭示真實(shí)網(wǎng)絡(luò)的組織原則、拓?fù)浣Y(jié)構(gòu)和動(dòng)力學(xué)特性。作為當(dāng)前的研究熱點(diǎn)，社區(qū)發(fā)現(xiàn)的研究成果被廣泛應(yīng)用在金融、交通和生物等各個(gè)領(lǐng)域[1]。目前，主流社區(qū)發(fā)現(xiàn)算法可分為模塊度優(yōu)化算法和標(biāo)簽傳播算法。模塊度優(yōu)化算法源自于Newman[2]提出的模塊度概念，通過比較真實(shí)網(wǎng)絡(luò)中各社團(tuán)的邊密度和隨機(jī)網(wǎng)絡(luò)對(duì)應(yīng)的子圖的邊密度的差值來定量度量社團(tuán)結(jié)構(gòu)的顯著性，模塊度越大，社區(qū)劃分效果越好[3]。在此之后，誕生了大量基于模塊度的優(yōu)化算法，如利用模塊度增值公式快速定位節(jié)點(diǎn)所在社區(qū)，可計(jì)算大規(guī)模網(wǎng)絡(luò)的Louvian算法[4]；可進(jìn)行無向和未加權(quán)網(wǎng)絡(luò)劃分的基于最大化加權(quán)模塊度的社區(qū)發(fā)現(xiàn)算法[5]；能部分解決分辨率限制和極端退化問題的結(jié)合節(jié)點(diǎn)親密度和節(jié)點(diǎn)度的模塊度優(yōu)化算法[6]；可根據(jù)不同節(jié)點(diǎn)劃分，以及結(jié)合深度學(xué)習(xí)和模塊度優(yōu)化的DNR (Deep Nonlinear Reconstruction)[7]和ComE (Community Embedding)[8]算法進(jìn)一步提升整體網(wǎng)絡(luò)模塊度的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法[9]。但是，基于模塊度的算法并不能真實(shí)反映社區(qū)劃分。

因此，基于標(biāo)簽傳播算法LPA(Label Propagation Algorithm)[10]的快速社區(qū)發(fā)現(xiàn)算法應(yīng)運(yùn)而生。LPA思路簡(jiǎn)單，具有線性時(shí)間復(fù)雜度，可有效處理大規(guī)模復(fù)雜網(wǎng)絡(luò)等優(yōu)點(diǎn)。LPA的出現(xiàn)引起了大量關(guān)注,接著研究人員提出了一系列擴(kuò)展算法，例如Leung等[11]提出的異步標(biāo)簽傳播算法，可解決LPA算法在二部網(wǎng)絡(luò)中震蕩不收斂問題。LPAm(Label Propagation Algorithm specializing modularity)[12]通過尋優(yōu)模塊度進(jìn)行標(biāo)簽更新，降低了LPA的隨機(jī)性，但存在易陷入局部最優(yōu)的缺點(diǎn)。LPAm+[13]結(jié)合了多級(jí)貪婪集聚算法，避免了LPAm的缺點(diǎn)，可進(jìn)一步提高劃分模塊度。LPA-S(Stepping Label Propagation Algorithm)[14]先根據(jù)節(jié)點(diǎn)相似性更新節(jié)點(diǎn)標(biāo)簽、劃分初始社區(qū)，然后根據(jù)社區(qū)相似性合并社區(qū)，可獲得更好的社區(qū)劃分。由于將模塊度作為優(yōu)化條件可能導(dǎo)致和真實(shí)社區(qū)劃分結(jié)果有偏差，部分研究將節(jié)點(diǎn)度和邊的權(quán)重引入標(biāo)簽更新過程，以解決節(jié)點(diǎn)更新標(biāo)簽的隨機(jī)性和無序性。比如LPAp(Label Propagation Algorithm with importance quantification)[15]根據(jù)節(jié)點(diǎn)PageRank值找到k個(gè)核心節(jié)點(diǎn)，分別為每個(gè)核心節(jié)點(diǎn)分配一個(gè)社區(qū)標(biāo)簽再進(jìn)行標(biāo)簽擴(kuò)散，降低了LPA算法結(jié)果的不穩(wěn)定性。NIBLPA(Node Influence Based Label Propagation Algorithm)[16]通過k-shell值將節(jié)點(diǎn)重要程度排序作為節(jié)點(diǎn)標(biāo)簽更新順序，并通過計(jì)算標(biāo)簽的重要程度，避免了當(dāng)節(jié)點(diǎn)遇到出現(xiàn)次數(shù)最多的標(biāo)簽不止一個(gè)時(shí)隨機(jī)選擇的問題。CenLP(Centrality-based Label Propagation)[17]則重新定義了節(jié)點(diǎn)中心值和偏向值，通過節(jié)點(diǎn)中心值和偏向值計(jì)算局部高密度近鄰節(jié)點(diǎn)的相似性來改進(jìn)標(biāo)簽的選取和傳播過程。上述算法中的標(biāo)簽傳播和更新都是發(fā)生在鄰居節(jié)點(diǎn)之間，但是對(duì)于復(fù)雜網(wǎng)絡(luò)的小世界性質(zhì)，節(jié)點(diǎn)之間信息交換并不只發(fā)生在相鄰的節(jié)點(diǎn)之間。此外，社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)的明確程度可通過網(wǎng)絡(luò)平均集聚系數(shù)反映，集聚系數(shù)越大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)越清晰；反之，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)則越模糊。如何在拓?fù)浣Y(jié)構(gòu)相對(duì)模糊的網(wǎng)絡(luò)中提高社區(qū)劃分精度也是當(dāng)前的研究熱點(diǎn)[5]。

為解決上述問題，本文提出基于節(jié)點(diǎn)影響力的理性標(biāo)簽傳播算法RLPBNI(Rational Label Propagation algorithm Based on Node Influence)。RLPBNI首先將節(jié)點(diǎn)影響力作為標(biāo)簽更新順序的依據(jù)；然后，引入理性節(jié)點(diǎn)的概念，假設(shè)節(jié)點(diǎn)可充分掌握網(wǎng)絡(luò)的局部和全局信息，并以理性思維方式選擇對(duì)它影響力最大的節(jié)點(diǎn)的標(biāo)簽作為更新標(biāo)簽，可兼顧拓?fù)浣Y(jié)構(gòu)不同的網(wǎng)絡(luò)；最后，根據(jù)社區(qū)重疊度對(duì)社區(qū)進(jìn)行降維處理，進(jìn)而提高社區(qū)劃分的精度。

2 相關(guān)理論

2.1 LPA

LPA是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的社區(qū)探測(cè)算法，主要思想是通過連接關(guān)系進(jìn)行標(biāo)簽傳遞。在初始狀態(tài)，每個(gè)節(jié)點(diǎn)被賦予唯一標(biāo)簽，每一次傳遞過程中，節(jié)點(diǎn)將自身標(biāo)簽傳遞給鄰居節(jié)點(diǎn)，同時(shí)接受來自其他鄰居節(jié)點(diǎn)傳遞的標(biāo)簽，并選擇出現(xiàn)次數(shù)最多的標(biāo)簽作為自身更新標(biāo)簽。如果出現(xiàn)次數(shù)最多的標(biāo)簽不止一個(gè)，那么節(jié)點(diǎn)隨機(jī)選擇其中一個(gè)標(biāo)簽進(jìn)行更新。不斷重復(fù)該過程，直至網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的標(biāo)簽不再變化，此時(shí)，具有相同標(biāo)簽的節(jié)點(diǎn)形成一個(gè)社區(qū)。

但是，LPA在多次迭代之后無法保證收斂性，當(dāng)算法采用同步更新標(biāo)簽的方式時(shí)，t步標(biāo)簽與t-1步標(biāo)簽相關(guān)，在二部網(wǎng)絡(luò)中會(huì)存在震蕩收斂的情況。除此之外，LPA還存在以下2個(gè)缺點(diǎn)：

(1)不穩(wěn)定性：節(jié)點(diǎn)更新的無序性造成不同更新順序可能得到不同的社區(qū)劃分結(jié)果；

(2)隨機(jī)性：當(dāng)節(jié)點(diǎn)的最大標(biāo)簽數(shù)不止一個(gè)時(shí)，節(jié)點(diǎn)會(huì)從中隨機(jī)選擇一個(gè)進(jìn)行標(biāo)簽更新，可能會(huì)產(chǎn)生雪崩效應(yīng)，難以保證社區(qū)劃分精度。

總體來說，標(biāo)簽傳播算法簡(jiǎn)單易于理解，未來也可應(yīng)用在大規(guī)模復(fù)雜網(wǎng)絡(luò)中，如何控制LPA的穩(wěn)定性和隨機(jī)性是亟待解決的問題。

2.2 節(jié)點(diǎn)影響力算法

常見的節(jié)點(diǎn)重要度度量指標(biāo)有度中心度、介數(shù)中心度和k-shell中心度[18]。度中心度只反映節(jié)點(diǎn)局部特征；而介數(shù)中心度只反映全局重要程度，且計(jì)算復(fù)雜，不能應(yīng)用在大規(guī)模網(wǎng)絡(luò)中；k-shell中心度可通過不斷刪除外層節(jié)點(diǎn)找到核心節(jié)點(diǎn)，在刪除節(jié)點(diǎn)的過程中直接去掉某些重要的邊，并將同一批次刪除的節(jié)點(diǎn)視為同等重要，其結(jié)果并不能準(zhǔn)確反映節(jié)點(diǎn)重要程度。

節(jié)點(diǎn)影響力算法[15]則認(rèn)為節(jié)點(diǎn)之間的相互影響并不只發(fā)生在相鄰節(jié)點(diǎn)之間，且在相同路徑長(zhǎng)度下，一個(gè)節(jié)點(diǎn)到達(dá)另一節(jié)點(diǎn)的路徑條數(shù)越多，影響力越大。設(shè)網(wǎng)絡(luò)G=(V,E)中存在M個(gè)節(jié)點(diǎn)，N條邊，其中，V表示節(jié)點(diǎn)集，E表示邊集。鄰接矩陣為A=A(i,j)M×M，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j直接相連，A(i,j)=1；否則，A(i,j)=0。 節(jié)點(diǎn)間影響力用Fk(i,j)表示(即節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的k步路徑影響力)，其等于節(jié)點(diǎn)i在長(zhǎng)度為k的鏈接路徑下到達(dá)節(jié)點(diǎn)j所遍歷的節(jié)點(diǎn)數(shù)量，如式(1)所示：

(1)

其中，節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的1步路徑節(jié)點(diǎn)間影響力F1(i,j)=A(i,j)，節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的k步路徑節(jié)點(diǎn)間影響力為Fk(i,j)，l為網(wǎng)絡(luò)中任意節(jié)點(diǎn)。若Fk-1(i,l)和A(l,j)同時(shí)非零，表示節(jié)點(diǎn)i可通過節(jié)點(diǎn)l對(duì)節(jié)點(diǎn)j施加影響力，相當(dāng)于k步路徑節(jié)點(diǎn)間影響力Fk(i,j)在Fk-1(i,l)的基礎(chǔ)上增加了一個(gè)遍歷節(jié)點(diǎn)l。

已有研究[18,19]發(fā)現(xiàn)，當(dāng)k等于網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)間的最短距離(即網(wǎng)絡(luò)直徑)時(shí)，標(biāo)準(zhǔn)化節(jié)點(diǎn)影響力值可以達(dá)到收斂狀態(tài)。節(jié)點(diǎn)影響力算法不僅考慮了節(jié)點(diǎn)的全局特性，而且模擬網(wǎng)絡(luò)中信息傳播真實(shí)過程，可以更有效地識(shí)別網(wǎng)絡(luò)中具有影響力的重要節(jié)點(diǎn)。

3 基于節(jié)點(diǎn)影響力的理性標(biāo)簽傳播算法

3.1 相關(guān)定義

定義1(節(jié)點(diǎn)間整體影響力Inf(i,j)) 基于節(jié)點(diǎn)影響力定義，節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的整體影響力等于兩者之間1～k步路徑節(jié)點(diǎn)間影響力之和[19]。不同路徑長(zhǎng)度下節(jié)點(diǎn)間影響力的權(quán)重不同，路徑長(zhǎng)度越長(zhǎng)，對(duì)應(yīng)的權(quán)重越小，計(jì)算公式如式(2)所示：

(2)

其中，F(xiàn)k(i,j)是節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的k步路徑節(jié)點(diǎn)間影響力；K表示節(jié)點(diǎn)間影響力的最長(zhǎng)路徑數(shù)，K值通常設(shè)為網(wǎng)絡(luò)直徑；參數(shù)λ因網(wǎng)絡(luò)結(jié)構(gòu)而異。

定義2(節(jié)點(diǎn)間整體影響力矩陣INF) 與鄰接矩陣類似，網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)間的整體影響力Inf(i,j)可組成節(jié)點(diǎn)間整體影響力矩陣，即INF=Inf(i,j)M×M。節(jié)點(diǎn)i到其他節(jié)點(diǎn)的節(jié)點(diǎn)間整體影響力構(gòu)成了INF的第i個(gè)行向量INFi。

定義3(理性節(jié)點(diǎn)) 理性節(jié)點(diǎn)的概念借鑒了經(jīng)濟(jì)學(xué)中理性人假設(shè)。理性節(jié)點(diǎn)定義為，在標(biāo)簽傳播過程中可以感知其他近鄰節(jié)點(diǎn)對(duì)其自身影響力大小，進(jìn)而選擇對(duì)自身影響最大的節(jié)點(diǎn)的標(biāo)簽作為本輪新標(biāo)簽進(jìn)行更新的一類節(jié)點(diǎn)。

定義4(社區(qū)重疊度COD(Ci,Cj)) 社區(qū)Ci與Cj的重疊度等于Ci和Cj重疊邊的數(shù)量與Ci和Cj中節(jié)點(diǎn)所連接邊總數(shù)的比值，公式如式(3)所示：

(3)

其中，Eo(Ci,Cj)表示社區(qū)Ci和Cj重疊邊的數(shù)量，Ec(Ci,Cj)表示Ci與Cj中節(jié)點(diǎn)所連接邊的總數(shù)。

3.2 算法流程

RLPBNI包含3個(gè)步驟，其流程如圖1所示。

Figure 1 Procedure of RLPBNI

(1)計(jì)算節(jié)點(diǎn)間影響力F(i,j)，并基于F(i,j)計(jì)算節(jié)點(diǎn)整體影響力Inf(i,j)，進(jìn)而得到矩陣INF。然后，將節(jié)點(diǎn)按照整體影響力的降序排列作為更新順序。

(2)初始化節(jié)點(diǎn)標(biāo)簽li，此時(shí)每個(gè)節(jié)點(diǎn)標(biāo)簽編號(hào)唯一，按照更新順序，對(duì)于每個(gè)節(jié)點(diǎn)找到對(duì)它影響力最大的節(jié)點(diǎn)的標(biāo)簽作為更新標(biāo)簽，重復(fù)這一過程直到每個(gè)節(jié)點(diǎn)標(biāo)簽不再變化時(shí)，停止更新。將具有同一個(gè)標(biāo)簽的節(jié)點(diǎn)歸為一個(gè)社區(qū)，得到初始候選社區(qū)。

(3)如果初始候選社區(qū)之間重疊度大于閾值，則將該2個(gè)社區(qū)進(jìn)行融合，直到所有社區(qū)之間重疊度都小于閾值，得到最終社區(qū)劃分結(jié)果。

3.2.1 節(jié)點(diǎn)更新序列初始化

本文首先計(jì)算節(jié)點(diǎn)影響力，按照由大到小的順序?qū)?jié)點(diǎn)影響力排序，并將其作為度量節(jié)點(diǎn)重要程度的依據(jù)。首先，根據(jù)式(1)計(jì)算k步路徑節(jié)點(diǎn)間影響力Fk；然后根據(jù)式(2)求得節(jié)點(diǎn)整體影響力INF，將節(jié)點(diǎn)按整體影響力由大到小排序即可得到初始節(jié)點(diǎn)序列L，流程如算法1所示。

算法1節(jié)點(diǎn)序列初始化

輸入：鄰接矩陣A，路徑長(zhǎng)度K，參數(shù)λ。

輸出：整體影響力矩陣INF，初始節(jié)點(diǎn)序列L。

1.INF=0M×M，F(xiàn)1(i,j)=A(i,j)，L=?；

2.Fork=1 toK

3.CalculateFk(i,j) according to equation(1)；

4. CalculateInf(i,j) according to equation(2)；

5.EndFor

6.INF=(Inf(i,j))M×M；

7.Fori=1 toM

8.Li=sort{INFi}，L=L∪Li；

9.EndFor

3.2.2 標(biāo)簽傳播

假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)都是理性節(jié)點(diǎn)，可獲得近鄰節(jié)點(diǎn)的完全信息，那么節(jié)點(diǎn)會(huì)選擇近鄰節(jié)點(diǎn)中對(duì)它影響最大的節(jié)點(diǎn)標(biāo)簽作為本輪更新標(biāo)簽。如果對(duì)該節(jié)點(diǎn)影響最大的節(jié)點(diǎn)存在2個(gè)或2個(gè)以上，則選取與該節(jié)點(diǎn)距離最短的節(jié)點(diǎn)。若對(duì)該節(jié)點(diǎn)影響最大，且距離最近的節(jié)點(diǎn)存在2個(gè)，則從中隨機(jī)選擇一個(gè)節(jié)點(diǎn)。按照標(biāo)簽更新順序重復(fù)迭代，直到每個(gè)節(jié)點(diǎn)的標(biāo)簽不再發(fā)生變化時(shí)，迭代停止。之后，將具有相同標(biāo)簽的節(jié)點(diǎn)歸為一個(gè)社區(qū)，得到初始候選社區(qū)。算法流程如算法2所示。

算法2標(biāo)簽傳播

輸入：網(wǎng)絡(luò)G，節(jié)點(diǎn)間影響力F，節(jié)點(diǎn)序列L，社區(qū)劃分?jǐn)?shù)q。

輸出：初始候選社區(qū)C。

1.Label={l1,l2, …,lM}；

2.Whileeach node’s labelliis not unique

3.ForeachLi∈L

4.MaxInf=max{F(i,1),…,F(i,M)}；

5.Ifcount(MaxInf) > 1

6.Ifcount(nearest(MaxInf)) > 1

7.Random select a nodeF(i,t)；

8.F(i,j)=F(i,t)；

9.Li=Lj；

10.EndIf

11.Endif

12.EndFor

13.EndWhile

14.If(C1∩…∩Cq=? andCiis unique)

15.C={C1,C2,…,Cq}；

16.EndIf

3.2.3 社區(qū)合并與更新

計(jì)算候選初始社區(qū)之間的重疊度，將重疊度高于閾值的2個(gè)社區(qū)中較小的社區(qū)合并在較大社區(qū)中，再次計(jì)算新社區(qū)之間重疊度，直到所有社區(qū)之間的重疊度不大于閾值，迭代停止。

算法3社區(qū)合并與更新

輸入：初始候選社區(qū)C，重疊度閾值a。

輸出：最終社區(qū)劃分COM。

1.WhileCOD(Ci,Cj) >a

2.ForeachCi∈C

3.D=max{COD(Ci,C1),…,COD(Ci,Cq)};

4.IfD>a

5.COD(Ci,Cj)=D;

6.Ci=Ci∪Cj;

7.DeleteCjfromC;

8.EndIf

9.EndFor

10.EndWhile

11.COM←C;

3.3 算法復(fù)雜度分析

假定網(wǎng)絡(luò)中有M個(gè)節(jié)點(diǎn)和N條邊，K為網(wǎng)絡(luò)直徑，S是理性節(jié)點(diǎn)標(biāo)簽傳播所得初始社區(qū)數(shù)，那么：

(1)計(jì)算節(jié)點(diǎn)影響力的時(shí)間復(fù)雜度為O(KM2)；

(2)理性節(jié)點(diǎn)標(biāo)簽傳播過程和LPA傳播過程相似，整個(gè)傳播過程的時(shí)間復(fù)雜度為O(N)；

(3)社區(qū)相似性計(jì)算的時(shí)間復(fù)雜度為O(S2)。

因此，本文RLPBNI的時(shí)間復(fù)雜度為O(KM2+N+S2)。由于K和S的取值通常遠(yuǎn)遠(yuǎn)小于M，因此O(KM2+N+S2) ～O(M2)。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證RLPBNI的有效性，本文采用真實(shí)網(wǎng)絡(luò)(Karate、Dolphins及Football)[20]及人工基準(zhǔn)網(wǎng)絡(luò)LFR(Lancichinetti Fortunato Radicchi)[21]進(jìn)行驗(yàn)證實(shí)驗(yàn)，評(píng)價(jià)指標(biāo)則選取模塊度Q、標(biāo)準(zhǔn)互信息指標(biāo)NMI(Normalized Mutual Information)[22]和調(diào)整蘭德指標(biāo)ARI(Adjust Rand Index)[23]3種。對(duì)比算法則包含F(xiàn)N(Fast Newman)、LPA、NIBLPA和CenLP 4種。

模塊度是評(píng)價(jià)社區(qū)發(fā)現(xiàn)算法性能的常用指標(biāo)，用于衡量社區(qū)結(jié)構(gòu)性的強(qiáng)弱，Q越接近 1，社區(qū)劃分精度越高，其對(duì)應(yīng)的社區(qū)結(jié)構(gòu)性越強(qiáng)，計(jì)算公式如式(4)所示：

(4)

其中，N為網(wǎng)絡(luò)中的總邊數(shù)，A表示網(wǎng)絡(luò)所對(duì)應(yīng)的鄰接矩陣。如果節(jié)點(diǎn)i和節(jié)點(diǎn)j直接相連，Aij= 1；否則，Aij=0。di和dj分別為節(jié)點(diǎn)i和節(jié)點(diǎn)j的度，li和lj分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的標(biāo)簽，如果li=lj，則δ(li,lj)=1，否則為0。

NMI和ARI指標(biāo)用于度量社區(qū)劃分結(jié)果與標(biāo)準(zhǔn)(真實(shí))社區(qū)結(jié)構(gòu)的相似度，如式(5)和式(6)所示：

(5)

(6)

其中，Ni和Nj分別表示算法結(jié)果序列中社區(qū)Ci的節(jié)點(diǎn)個(gè)數(shù)和真實(shí)劃分序列中社區(qū)Cj的節(jié)點(diǎn)個(gè)數(shù)，Nij表示社區(qū)Ci和Cj的公共節(jié)點(diǎn)個(gè)數(shù)，m和n表示結(jié)果序列和真實(shí)序列的長(zhǎng)度，M表示節(jié)點(diǎn)個(gè)數(shù)。NMI的取值為[0,1]，其值越大說明互信息化程度越高，2個(gè)序列越相近。ARI指標(biāo)與NMI類似，取值亦為[0,1]，其值越大，2個(gè)序列相似程度越高。

4.2 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果與分析

4.2.1 Karate數(shù)據(jù)集

Karate網(wǎng)絡(luò)是通過對(duì)某一美國大學(xué)空手道俱樂部進(jìn)行觀測(cè)而構(gòu)建出的一個(gè)含有34個(gè)節(jié)點(diǎn)的社會(huì)網(wǎng)絡(luò)。Karate網(wǎng)絡(luò)中的節(jié)點(diǎn)表示俱樂部成員，其中包括俱樂部經(jīng)理、教練和學(xué)員；邊則表示成員之間的關(guān)系或聯(lián)系。由于俱樂部經(jīng)理和教練之間產(chǎn)生意見分歧，俱樂部成員之間逐漸形成以教練和經(jīng)理為首的2個(gè)社區(qū)。RLPBNI的社區(qū)探測(cè)結(jié)果如圖2所示，本文用黑色虛線區(qū)分左下和右上2個(gè)社區(qū)。從圖2中可看出，節(jié)點(diǎn)1和節(jié)點(diǎn)34分別處在2個(gè)社區(qū)中心，表示俱樂部經(jīng)理和教練，NMI值為1，說明RLPBNI劃分結(jié)果與真實(shí)社區(qū)劃分結(jié)果完全一致。

Figure 2 Community detection result on Karate

4.2.2 Dolphins數(shù)據(jù)集

Dolphins網(wǎng)絡(luò)描述了1994～2001年生活在新西蘭海峽間的寬吻海豚之間的聯(lián)系，網(wǎng)絡(luò)中節(jié)點(diǎn)表示海豚，邊則表示2只海豚間關(guān)系，共包含62個(gè)節(jié)點(diǎn)和928條邊。本文算法將Dolphins網(wǎng)絡(luò)劃分為2個(gè)社區(qū)，結(jié)果如圖3所示。RLPBNI的NMI值為0.881 9，其結(jié)果只有1個(gè)節(jié)點(diǎn)和真實(shí)社區(qū)劃分不一致，算法將節(jié)點(diǎn)SN89(圖中箭頭所指節(jié)點(diǎn))劃分到了左側(cè)的社區(qū)中。SN89只有2條邊，分別連接了左側(cè)社區(qū)中的節(jié)點(diǎn)Web和右側(cè)社區(qū)中的節(jié)點(diǎn)SN100。Web的節(jié)點(diǎn)度為9，SN100的節(jié)點(diǎn)度為7。從圖3中可知，由于Web所在局部結(jié)構(gòu)中節(jié)點(diǎn)連接更加緊密，對(duì)SN89的影響路徑條數(shù)大于對(duì)SN100的，因此本文算法將SN89劃分到節(jié)點(diǎn)Web所在的社區(qū)。

Figure 3 Community detection result on Dolphins

Figure 4 Community detection result on Football

4.2.3 Football數(shù)據(jù)集

Football足球俱樂部網(wǎng)絡(luò)由2000年美國大學(xué)生足球聯(lián)賽數(shù)據(jù)抽象而成，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)表示一個(gè)足球隊(duì)，每條邊表示2支隊(duì)之間進(jìn)行過的一場(chǎng)比賽，每個(gè)球隊(duì)都隸屬一個(gè)聯(lián)盟，聯(lián)盟內(nèi)部球隊(duì)之間比賽次數(shù)多于非聯(lián)盟球隊(duì)之間比賽次數(shù)，共有112支球隊(duì)，12個(gè)聯(lián)盟，613場(chǎng)比賽。應(yīng)用RLPBNI對(duì)Football網(wǎng)絡(luò)進(jìn)行劃分，得到11個(gè)社區(qū)，在圖4中分別用①～表示。

Navy、NotreDame、UtahState、Connecticut和CentralFlorida這5支球隊(duì)(圖中橢圓所圈節(jié)點(diǎn))本屬同一個(gè)聯(lián)盟，但該聯(lián)盟節(jié)點(diǎn)松散，內(nèi)部賽事較少。Navy和NotreDame這2支球隊(duì)與①號(hào)聯(lián)盟間的關(guān)系更為緊密，Connecticut和CentralFlorida與②號(hào)聯(lián)盟的球隊(duì)之間的比賽更多，UtahState與以上4支球隊(duì)未曾有過接觸，但與⑧號(hào)聯(lián)盟的球隊(duì)有過多次較量。根據(jù)節(jié)點(diǎn)連接緊密程度和節(jié)點(diǎn)影響力，RLPBNI將5支球隊(duì)劃分給其他聯(lián)盟，最終得到11個(gè)聯(lián)盟，但NMI值仍然高達(dá)0.909 5，比其他4種算法的精度更高。

由于3個(gè)真實(shí)網(wǎng)絡(luò)的集聚系數(shù)皆大于0.2，為方便性能對(duì)比，RLPBNI的參數(shù)λ取值設(shè)為0.2～0.3，K等于對(duì)應(yīng)網(wǎng)絡(luò)直徑。5種算法在3個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行社區(qū)劃分的平均模塊度Qavg和NMI結(jié)果如表1所示。在Qavg指標(biāo)方面，NIBLPA和RLPBNI 2種算法分別在Karate網(wǎng)絡(luò)上獲得了最優(yōu)值(0.404 3)和次優(yōu)值(0.401 2)，F(xiàn)N的結(jié)果最差；而RLPBNI和CenLP則在Dolphins和Football 2個(gè)網(wǎng)絡(luò)上分別得到最優(yōu)值(0.533 4，0.626 3)和次優(yōu)值(0.526 6，0.609 7)，LPA在Dolphins網(wǎng)絡(luò)上的平均模塊度最低，F(xiàn)N在Football網(wǎng)絡(luò)上的社區(qū)劃分效果最差。在NMI指標(biāo)方面，本文提出的RLPBNI在所有真實(shí)網(wǎng)絡(luò)上皆得到最優(yōu)結(jié)果，其中在Karate網(wǎng)絡(luò)上的結(jié)果和真實(shí)劃分結(jié)果一致，在Dolphins和Football網(wǎng)絡(luò)上的NMI值均高于其他算法的，也非常接近真實(shí)結(jié)果。NIBLPA的社區(qū)劃分結(jié)果次之；FN算法的劃分結(jié)果總體較差，這是因?yàn)镕N算法是將模塊度系數(shù)作為優(yōu)化目標(biāo)，而沒有考慮得到的社區(qū)劃分結(jié)果和真實(shí)社區(qū)劃分的相似性。

Table 1 Results comparison of five algorithms on real-world networks

4.3 人工合成網(wǎng)絡(luò)實(shí)驗(yàn)與結(jié)果分析

LFR模型通常用于生成人工合成網(wǎng)絡(luò)，該模型生成的人工網(wǎng)絡(luò)的節(jié)點(diǎn)度和社區(qū)規(guī)模均服從冪律分布，更接近現(xiàn)實(shí)生活中的網(wǎng)絡(luò)結(jié)構(gòu)，且可通過改變可調(diào)節(jié)參數(shù)控制生成不同社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)，一般用于測(cè)試社區(qū)發(fā)現(xiàn)算法的性能。本節(jié)實(shí)驗(yàn)共生成2個(gè)人工網(wǎng)絡(luò)，具體參數(shù)設(shè)置如表2所示。

Table 2 Parameter settings of LFR synthetic networks

在表2中，M表示網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù);p和pmax分別表示網(wǎng)絡(luò)的平均度數(shù)和最大度數(shù);Nmax和Nmin分別表示社區(qū)的最大和最小節(jié)點(diǎn)數(shù);μ為網(wǎng)絡(luò)混合系數(shù)，其值越大，網(wǎng)絡(luò)結(jié)構(gòu)越模糊，社區(qū)劃分結(jié)果越不明顯。

5種算法在Net1和Net2網(wǎng)絡(luò)上的NMI與ARI結(jié)果分別如圖5和圖6所示。圖中橫坐標(biāo)為網(wǎng)絡(luò)混合系數(shù)μ，μ以步長(zhǎng)0.1從0.1增加到0.9，縱坐標(biāo)是相應(yīng)算法的社區(qū)劃分結(jié)果與真實(shí)社區(qū)劃分之間的接近程度(NMI與ARI)。從圖5和圖6中可看出，隨著μ值增加(即網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜程度提高)，5種算法的社區(qū)劃分精度不斷降低，對(duì)應(yīng)劃分結(jié)果的社區(qū)結(jié)構(gòu)越來越模糊。當(dāng)μ≤ 0.5時(shí)，F(xiàn)N的精度隨著μ的增加不斷降低，其他4種算法的精度接近于1，且基本持平；當(dāng)μ>0.5時(shí)，NIBLPA、LPA、CenLP和RLPBNI的社區(qū)劃分精度開始降低，其中前三者的精度下降速度較快，而RLPBNI精度的下降速度則相對(duì)平緩，而且在不同網(wǎng)絡(luò)上皆優(yōu)于其他4種算法，說明該算法能夠有效地發(fā)現(xiàn)社區(qū)邊界比較模糊的網(wǎng)絡(luò)結(jié)構(gòu)。

Figure 5 Comparison of NMI and ARI on Net1

Figure 6 Comparison of NMI and ARI on Net2

4.4 參數(shù)靈敏度分析

NIBLPA的社區(qū)劃分效果在很大程度上依賴參數(shù)K和λ。K為節(jié)點(diǎn)間影響力最長(zhǎng)路徑，也就是對(duì)整個(gè)網(wǎng)絡(luò)計(jì)算傳播影響力的上限估計(jì)。K≥1，最大值是2個(gè)節(jié)點(diǎn)之間最長(zhǎng)路徑，2節(jié)點(diǎn)間最長(zhǎng)路徑顯然可以無窮大，由于計(jì)算復(fù)雜度高，本文假設(shè)在不影響算法效果的前提下，K越小越好。λ為可調(diào)節(jié)參數(shù)，對(duì)不同路徑長(zhǎng)度下節(jié)點(diǎn)間影響力進(jìn)行權(quán)重分配。λ越大，路徑長(zhǎng)的節(jié)點(diǎn)間影響力獲得的權(quán)重較小。

4.4.1 參數(shù)K靈敏度分析

由于RLPBNI在Net1和Net2網(wǎng)絡(luò)上的劃分效果相近，本文僅使用Net2網(wǎng)絡(luò)分析K的靈敏度，并討論K對(duì)算法的影響效果。網(wǎng)絡(luò)混合系數(shù)μ=0.6，網(wǎng)絡(luò)直徑為6，實(shí)驗(yàn)結(jié)果如圖7所示。

Figure 7 Parameter sensitivity (K) of RLPBNI on Net2@0.6

在圖7中，2個(gè)子圖的x軸和y軸分別代表可調(diào)節(jié)參數(shù)λ和路徑長(zhǎng)度K，z軸表示網(wǎng)絡(luò)劃分的相似度指標(biāo)NMI和ARI，顏色越淺則表示劃分相似度越低，顏色越深則反之。參數(shù)K和λ的取值分別為{1,2,…,10}和{0.1,0.2,…,1}。從圖7中可以看出，對(duì)于不同取值的λ，K值的變化對(duì)NMI和ARI的整體影響很小，特別是當(dāng)λ∈[0.1,0.4]時(shí)，K值大小對(duì)結(jié)果基本上沒有影響；當(dāng)λ∈(0.4,0.6]時(shí)，K值變化使NMI和ARI值產(chǎn)生微小的波動(dòng)；當(dāng)λ∈(0.6,1]時(shí)，K值變化會(huì)帶來相對(duì)較大的NMI和ARI值波動(dòng)，但在可接受范圍之內(nèi)?？傮w來看，當(dāng)λ值確定且K取值為網(wǎng)絡(luò)直徑時(shí)，NMI和ARI可以得到最優(yōu)結(jié)果。

4.4.2 參數(shù)λ靈敏度分析

為分析網(wǎng)絡(luò)上λ的取值范圍，將RLPBNI應(yīng)用在3個(gè)真實(shí)網(wǎng)絡(luò)和人工網(wǎng)絡(luò)Net2上，并將K值固定為每個(gè)網(wǎng)絡(luò)對(duì)應(yīng)的網(wǎng)絡(luò)直徑，直接討論λ與相似度指標(biāo)NMI和ARI的關(guān)系。實(shí)驗(yàn)結(jié)果分別如圖8和圖9所示。

Figure 8 Parameter sensitivity (λ) of RLPBNI on real-world networks

在圖8中，橫軸為λ，以步長(zhǎng)0.05從0.1遞增到0.9，縱坐標(biāo)代表NMI和ARI。由圖8可知，在Karate和Dolphins網(wǎng)絡(luò)上，λ的取值對(duì)NMI和ARI沒有影響，其中在Karate網(wǎng)絡(luò)上的NMI和ARI值均為1，劃分結(jié)果與真實(shí)情況相符。在Football網(wǎng)絡(luò)上，當(dāng)λ≤0.7時(shí)，NMI和ARI值保持穩(wěn)定；當(dāng)λ>0.7時(shí)，NMI和ARI值開始逐步降低，說明在3個(gè)真實(shí)網(wǎng)絡(luò)上，RLPBNI在λ≤0.7時(shí)效果最優(yōu)。對(duì)于以上3個(gè)真實(shí)網(wǎng)絡(luò)而言，對(duì)應(yīng)的網(wǎng)絡(luò)集聚系數(shù)分別是0.570 6，0.248 0和0.403 2，皆大于0.1，此時(shí)λ取較小值即可達(dá)到最優(yōu)劃分效果，因此最優(yōu)λ可以取0.1或0.2。

Figure 9 Parameter sensitivity (λ) of RLPBNI on Net2 with different settings of μ

在圖9的所有子圖中，橫軸為λ，且以0.1為步長(zhǎng)由0.1遞增到0.9，縱坐標(biāo)表示NMI和ARI。9個(gè)子圖中的K值為其對(duì)應(yīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)直徑?？梢钥闯觯?dāng)μ≤0.2時(shí)，NIBLPA的精度與參數(shù)λ無關(guān)；當(dāng)μ∈(0.2,0.7]時(shí)，算法精度隨λ的增大而緩慢降低，且當(dāng)μ=0.7時(shí)，算法精度隨λ增大而降低的幅度降至最低；當(dāng)μ∈[0.8,0.9]時(shí)，算法精度反而隨λ增大而增加。這是因?yàn)殡S著網(wǎng)絡(luò)混合系數(shù)的增大，網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)越來越不明顯，需要對(duì)距離較近的節(jié)點(diǎn)分配較高的權(quán)重，以提高凝聚度，可使結(jié)果更為精確。而當(dāng)社區(qū)結(jié)構(gòu)較為明顯時(shí)，為了充分辨識(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力，距離較近的路徑權(quán)重可設(shè)置較小，增大后期其他節(jié)點(diǎn)的參與度。社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)的明顯程度可以通過網(wǎng)絡(luò)平均集聚系數(shù)反映，網(wǎng)絡(luò)平均集聚系數(shù)與網(wǎng)絡(luò)混合系數(shù)μ成反比。μ值越高，不同社團(tuán)之間的辨識(shí)程度越差，節(jié)點(diǎn)之間的集聚效應(yīng)越差，相對(duì)應(yīng)的網(wǎng)絡(luò)平均集聚系數(shù)越小。

由Net2網(wǎng)絡(luò)所生成的9個(gè)衍生網(wǎng)絡(luò)的網(wǎng)絡(luò)混合系數(shù)和網(wǎng)絡(luò)平均集聚系數(shù)如表3所示。顯然，在表3中，Net2上的9個(gè)衍生網(wǎng)絡(luò)的網(wǎng)絡(luò)平均集聚系數(shù)都與網(wǎng)絡(luò)混合系數(shù)μ成反比。結(jié)合圖9和表3可以發(fā)現(xiàn)，當(dāng)網(wǎng)絡(luò)混合系數(shù)μ≤0.7時(shí)(即網(wǎng)絡(luò)平均集聚系數(shù)≥0.04時(shí))，λ的取值越小，RLPBNI的劃分結(jié)果對(duì)應(yīng)的NMI和ARI值越大，此時(shí)最優(yōu)λ可取[0.1,0.3]；當(dāng)網(wǎng)絡(luò)混合系數(shù)μ>0.7時(shí)(即網(wǎng)絡(luò)平均集聚系數(shù)<0.04時(shí))，λ取值越大，算法劃分效果則越好，此時(shí)最優(yōu)λ可取0.9。上述分析進(jìn)一步印證了RLPBNI的精度與參數(shù)λ及社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)(平均集聚系數(shù))之間的關(guān)系，并給出了不同情況下的最優(yōu)λ取值。

Table 3 Average clustering coefficients on Net2 variants

5 結(jié)束語

本文提出基于節(jié)點(diǎn)影響力的理性節(jié)點(diǎn)標(biāo)簽傳播算法RLPBNI，首次提出理性節(jié)點(diǎn)概念，通過節(jié)點(diǎn)整體影響力主動(dòng)選擇鄰近節(jié)點(diǎn)中對(duì)自身影響最大的節(jié)點(diǎn)的標(biāo)簽作為更新標(biāo)簽，得到初始候選社區(qū)。然后，根據(jù)社區(qū)重疊度對(duì)初始候選社區(qū)進(jìn)行再融合，并得到最終社區(qū)劃分結(jié)果。通過模塊度、NMI和ARI指標(biāo)，在3個(gè)真實(shí)網(wǎng)絡(luò)和2個(gè)人工網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果顯示，本文提出RLPBNI相比其他4種主流算法的精度更高，且在混合程度較高的網(wǎng)絡(luò)上精度較高。此外，本文還分析并討論了參數(shù)K和λ對(duì)RLPBNI的影響：通常，K對(duì)應(yīng)網(wǎng)絡(luò)直徑，λ則與網(wǎng)絡(luò)平均聚類系數(shù)直接相關(guān)，當(dāng)網(wǎng)絡(luò)平均聚類系數(shù)較大時(shí)，λ值越小越好；當(dāng)網(wǎng)絡(luò)平均集聚系數(shù)較小時(shí)，λ值越大越好。

本文算法依然存在一些不足：(1)只考慮了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)社區(qū)形成的影響，沒有討論現(xiàn)實(shí)社區(qū)節(jié)點(diǎn)間相互聚合時(shí)所需考慮的多種影響因素，例如節(jié)點(diǎn)的固有屬性(如特征、描述及偏好等)；(2)只研究了無向網(wǎng)絡(luò)中的節(jié)點(diǎn)歸屬問題，沒有考慮有向網(wǎng)絡(luò)，也未考慮到節(jié)點(diǎn)可能存在歸屬重疊的情況。未來將在節(jié)點(diǎn)標(biāo)簽傳播的基礎(chǔ)上，引入邊標(biāo)簽的更新規(guī)則，以提高算法穩(wěn)定性，進(jìn)一步提高算法在社區(qū)結(jié)構(gòu)模糊的重疊網(wǎng)絡(luò)中的識(shí)別能力。