張 猛，李玲娟

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023)

0 引 言

現(xiàn)實(shí)世界中的事物都可以用復(fù)雜網(wǎng)絡(luò)模型來(lái)表示，例如人與人之間的社會(huì)關(guān)系、細(xì)胞之間的生物關(guān)系和萬(wàn)維網(wǎng)之間的鏈接結(jié)構(gòu)等。隨著對(duì)網(wǎng)絡(luò)性質(zhì)的深入研究，人們發(fā)現(xiàn)許多網(wǎng)絡(luò)都存在著社團(tuán)結(jié)構(gòu)，其特征是同一社團(tuán)內(nèi)節(jié)點(diǎn)連接緊密，不同社團(tuán)間節(jié)點(diǎn)連接稀疏[1-2]。揭示網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，對(duì)于了解網(wǎng)絡(luò)結(jié)構(gòu)、分析網(wǎng)絡(luò)特性和發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中潛在的關(guān)系等都具有非常重要的意義。

因此，近年來(lái)研究人員提出了許多社團(tuán)劃分算法。文獻(xiàn)[3]提出了基于邊介數(shù)的GN算法，基本思想是社團(tuán)內(nèi)邊介數(shù)較小，社團(tuán)間邊介數(shù)較大。GN算法的時(shí)間復(fù)雜度為O(m2n)，其中m代表網(wǎng)絡(luò)中的邊數(shù)，n代表網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，該算法不適合用于大規(guī)模網(wǎng)絡(luò)。文獻(xiàn)[4]基于模塊度函數(shù)Q提出了一個(gè)快速層次聚類(lèi)算法FastQ，該算法的時(shí)間復(fù)雜度為O((m+n)n)，提高了社團(tuán)劃分的效率。文獻(xiàn)[5]首次提出使用派系過(guò)濾算法CPM挖掘網(wǎng)絡(luò)中的重疊社團(tuán)結(jié)構(gòu)，其基本思想是認(rèn)為社團(tuán)結(jié)構(gòu)由相鄰的派系(完全子圖)構(gòu)成，通過(guò)尋找相互連通的k-派系方法發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)。文獻(xiàn)[6]提出了基于標(biāo)簽傳播的社團(tuán)劃分算法LPA(label propagation algorithm)，該算法的時(shí)間復(fù)雜度近似線性。

LPA算法非常適用于大規(guī)模網(wǎng)絡(luò)，但是該算法在標(biāo)簽傳播過(guò)程中存在隨機(jī)性，嚴(yán)重影響了算法劃分結(jié)果的穩(wěn)定性。針對(duì)這一問(wèn)題，文獻(xiàn)[7]提出帶約束的標(biāo)簽傳播算法LPAm，將LPA算法轉(zhuǎn)換為優(yōu)化問(wèn)題，但是該算法容易使目標(biāo)函數(shù)模塊度陷入局部最優(yōu)。文獻(xiàn)[8]提出了LPAm+算法，采用同時(shí)合并多個(gè)社團(tuán)策略來(lái)避免局部最優(yōu)。文獻(xiàn)[9]提出了基于標(biāo)簽熵的標(biāo)簽傳播方法LPA-E(label propagation in entropic order)，將節(jié)點(diǎn)按照標(biāo)簽的熵升序進(jìn)行更新，降低了LPA算法的隨機(jī)性。文獻(xiàn)[10]基于網(wǎng)絡(luò)預(yù)處理的改進(jìn)標(biāo)簽傳播算法KLPA(improved label propagation algorithm based on network preprocessing)預(yù)處理階段刪除了網(wǎng)絡(luò)中的某些節(jié)點(diǎn)，一定程度上破壞了網(wǎng)絡(luò)的原始結(jié)構(gòu)。

雖然上述方法某種程度上能提高LPA算法的準(zhǔn)確性、穩(wěn)定性或者收斂速度，但是并未消除LPA算法的隨機(jī)性。

文中設(shè)計(jì)了一種穩(wěn)定的標(biāo)簽傳播社團(tuán)劃分算法S-LPA(a stable label propagation community division algorithm)，綜合考慮節(jié)點(diǎn)的局部信息和全局信息，計(jì)算節(jié)點(diǎn)綜合影響力，按照綜合影響力對(duì)節(jié)點(diǎn)標(biāo)簽進(jìn)行更新。然后在標(biāo)簽傳播過(guò)程中根據(jù)標(biāo)簽影響力大小進(jìn)行標(biāo)簽更新，減少算法的隨機(jī)性，提高算法的穩(wěn)定性和準(zhǔn)確性。

1 相關(guān)知識(shí)

1.1 LPA算法

LPA算法是一種基于圖的半監(jiān)督學(xué)習(xí)方法，基本思想是用鄰居節(jié)點(diǎn)的標(biāo)簽信息來(lái)預(yù)測(cè)待更新節(jié)點(diǎn)的標(biāo)簽信息。該算法在初始階段給每個(gè)節(jié)點(diǎn)分配唯一標(biāo)簽，然后隨機(jī)選擇節(jié)點(diǎn)進(jìn)行標(biāo)簽更新；在標(biāo)簽更新過(guò)程中，每個(gè)節(jié)點(diǎn)根據(jù)式1選擇鄰居節(jié)點(diǎn)中出現(xiàn)次數(shù)最高的標(biāo)簽進(jìn)行標(biāo)簽更新，其中l(wèi)i表示待更新節(jié)點(diǎn)i的標(biāo)簽，N(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集，lj表示節(jié)點(diǎn)i鄰居節(jié)點(diǎn)j的標(biāo)簽，δ(lj,l)為克羅內(nèi)克函數(shù)。

(1)

若次數(shù)最多的標(biāo)簽有多個(gè)，則隨機(jī)選擇一個(gè)標(biāo)簽作為待更新節(jié)點(diǎn)的標(biāo)簽；最后經(jīng)多次迭代至所有節(jié)點(diǎn)標(biāo)簽不再變化時(shí)，擁有相同標(biāo)簽的節(jié)點(diǎn)屬于一個(gè)社團(tuán)。

在LPA標(biāo)簽更新過(guò)程中存在兩種標(biāo)簽更新方式，分別為同步更新和異步更新。同步更新是指在第t次迭代時(shí)，待更新節(jié)點(diǎn)的標(biāo)簽由其鄰居節(jié)點(diǎn)在第t-1次迭代時(shí)的標(biāo)簽所決定，這種方式應(yīng)用在具有二分結(jié)構(gòu)的網(wǎng)絡(luò)上會(huì)產(chǎn)生標(biāo)簽震蕩現(xiàn)象。異步更新是指在第t次迭代時(shí)，待更新節(jié)點(diǎn)的標(biāo)簽由其鄰居節(jié)點(diǎn)在第t-1次和第t次迭代時(shí)的標(biāo)簽共同決定，這種方式可以避免標(biāo)簽震蕩現(xiàn)象。

1.2 LPA存在的問(wèn)題

LPA算法時(shí)間復(fù)雜度低，但是在算法中所存在的隨機(jī)策略會(huì)導(dǎo)致每次運(yùn)行所產(chǎn)生的結(jié)果不盡相同，有時(shí)會(huì)產(chǎn)生一些瑣碎的、無(wú)意義的社團(tuán)結(jié)構(gòu)，影響了算法的準(zhǔn)確性和穩(wěn)定性。LPA算法隨機(jī)策略主要存在于兩個(gè)方面：

(1)在標(biāo)簽初始化時(shí)，LPA算法給網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)分配一個(gè)唯一標(biāo)簽，將節(jié)點(diǎn)隨機(jī)排列得到一個(gè)節(jié)點(diǎn)序列并以此作為初始節(jié)點(diǎn)更新順序。每次迭代時(shí)節(jié)點(diǎn)的更新順序都是隨機(jī)的，而LPA算法對(duì)節(jié)點(diǎn)更新順序又非常敏感。這種更新順序忽略了節(jié)點(diǎn)自身的重要性差異，使得重要性較小的節(jié)點(diǎn)可能影響重要性較大的節(jié)點(diǎn)，產(chǎn)生標(biāo)簽“逆流”現(xiàn)象。

(2)在標(biāo)簽更新過(guò)程中，當(dāng)待更新節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中次數(shù)最多的標(biāo)簽有多個(gè)時(shí)，LPA算法隨機(jī)選擇一個(gè)標(biāo)簽作為待更新節(jié)點(diǎn)的標(biāo)簽，沒(méi)有考慮鄰居節(jié)點(diǎn)信息對(duì)標(biāo)簽選擇的影響。

2 S-LPA算法

為了減少算法的隨機(jī)性，提高LPA算法的準(zhǔn)確性和穩(wěn)定性，文中設(shè)計(jì)了一種穩(wěn)定的標(biāo)簽傳播社團(tuán)劃分算法S-LPA。該算法在保留LPA算法具有的線性時(shí)間復(fù)雜度的基礎(chǔ)上，結(jié)合節(jié)點(diǎn)局部影響力、全局影響力以及標(biāo)簽影響力對(duì)LPA算法進(jìn)行改進(jìn)。首先在節(jié)點(diǎn)初始化時(shí)，按照節(jié)點(diǎn)綜合影響力升序排序；其次當(dāng)候選標(biāo)簽有多個(gè)時(shí)，根據(jù)其標(biāo)簽影響力大小進(jìn)行標(biāo)簽更新，減少標(biāo)簽更新過(guò)程中的隨機(jī)性。

2.1 節(jié)點(diǎn)綜合影響力

(1)K-Shell算法。

評(píng)價(jià)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的方法有度中心性、介數(shù)中心性、PageRank等，但是這些評(píng)價(jià)方法都存在一定的局限性。例如度中心性方法沒(méi)有將節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置考慮在內(nèi)；介數(shù)中心性方法需要計(jì)算各節(jié)點(diǎn)之間的距離，時(shí)間復(fù)雜度較高；PageRank對(duì)節(jié)點(diǎn)影響力排序不唯一。文獻(xiàn)[11]提出了K-Shell分解算法，該算法時(shí)間復(fù)雜度為O(n)，并能準(zhǔn)確地衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的全局影響力。

假設(shè)網(wǎng)絡(luò)中不存在孤立節(jié)點(diǎn)，K-Shell算法的一般步驟為：首先刪除網(wǎng)絡(luò)中所有度為1的節(jié)點(diǎn)；若在刪除過(guò)程中出現(xiàn)新的度為1的節(jié)點(diǎn)，則繼續(xù)刪除，直到網(wǎng)絡(luò)中不存在度為1的節(jié)點(diǎn)，此時(shí)這些被刪除的節(jié)點(diǎn)的K-Shell值為1；然后以同樣的方法刪除網(wǎng)絡(luò)中所有度為2的節(jié)點(diǎn)；反復(fù)如此，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的K-Shell值都被確定，K-Shell值越大，說(shuō)明節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置越核心，其影響力也就越大。

(2)節(jié)點(diǎn)綜合影響力計(jì)算方法。

雖然K-Shell算法能較好地衡量網(wǎng)絡(luò)中所有節(jié)點(diǎn)的影響力，但是K-Shell是一種粗粒度化的節(jié)點(diǎn)影響力方法，同一層的節(jié)點(diǎn)被賦予相同K-Shell值，其影響力無(wú)法區(qū)分。為此，文中借鑒文獻(xiàn)[12]的思想，結(jié)合節(jié)點(diǎn)分解時(shí)的迭代層數(shù)和K-Shell值來(lái)衡量節(jié)點(diǎn)全局影響力，其公式如下：

IKs(i)=Ks(i)+t(i)

(2)

其中，Ks(i)表示節(jié)點(diǎn)i的K-Shell值；t(i)表示刪除節(jié)點(diǎn)i時(shí)的迭代次數(shù)；IKs(i)表示節(jié)點(diǎn)i的改進(jìn)的K-Shell值。

改進(jìn)的K-Shell值能較好地反映節(jié)點(diǎn)全局影響力，但是無(wú)法反映節(jié)點(diǎn)的局部影響力。為了進(jìn)一步區(qū)分和衡量節(jié)點(diǎn)影響力，文中融入能反映節(jié)點(diǎn)局部信息的節(jié)點(diǎn)歸一化度值和鄰居節(jié)點(diǎn)的影響力來(lái)綜合考慮節(jié)點(diǎn)影響力。節(jié)點(diǎn)綜合影響力公式如下：

(3)

其中，IKs(i)表示改進(jìn)的K-Shell值；D(i)表示節(jié)點(diǎn)的歸一化度值；N(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)；CI(i)表示節(jié)點(diǎn)i的綜合影響力。

節(jié)點(diǎn)綜合影響力綜合考慮能反映節(jié)點(diǎn)全局影響力的K-Shell值、迭代次數(shù)和局部影響力的度值、鄰居節(jié)點(diǎn)信息，克服了K-Shell算法的缺點(diǎn)，同時(shí)擁有近似線性時(shí)間復(fù)雜度。

2.2 標(biāo)簽影響力

LPA算法在標(biāo)簽更新過(guò)程中，待更新節(jié)點(diǎn)標(biāo)簽由其鄰居節(jié)點(diǎn)中出現(xiàn)次數(shù)最高的標(biāo)簽所決定；若存在多個(gè)競(jìng)爭(zhēng)標(biāo)簽，則隨機(jī)選擇一個(gè)標(biāo)簽作為待更新節(jié)點(diǎn)的標(biāo)簽，該方法很大程度上影響了算法的準(zhǔn)確性和穩(wěn)定性，導(dǎo)致在相同的網(wǎng)絡(luò)上運(yùn)行多次該算法，得到的結(jié)果不盡相同?？紤]到鄰居節(jié)點(diǎn)的影響力越大，鄰居節(jié)點(diǎn)中具有相同標(biāo)簽個(gè)數(shù)越多，其標(biāo)簽越容易傳播給待更新節(jié)點(diǎn)。文中將鄰居節(jié)點(diǎn)中出現(xiàn)標(biāo)簽的次數(shù)和鄰居節(jié)點(diǎn)影響力相結(jié)合來(lái)計(jì)算標(biāo)簽綜合影響力，公式如下：

(4)

其中，Nl(x)表示節(jié)點(diǎn)x的標(biāo)簽為l的鄰居節(jié)點(diǎn)集合。

2.3 S-LPA算法設(shè)計(jì)與分析

(1)S-LPA算法設(shè)計(jì)。

穩(wěn)定的標(biāo)簽傳播社團(tuán)劃分算法S-LPA的全部流程如下：

輸入：網(wǎng)絡(luò)G=(V,E)，V代表網(wǎng)絡(luò)中的頂點(diǎn)，E代表網(wǎng)絡(luò)中的邊，最大迭代次數(shù)為t；

輸出：社團(tuán)劃分結(jié)果。

算法步驟：

①初始化網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i∈V的標(biāo)簽；

②根據(jù)式2計(jì)算每個(gè)節(jié)點(diǎn)的全局影響力；

③根據(jù)式5計(jì)算每個(gè)節(jié)點(diǎn)的歸一化度值，其中d(i)表示節(jié)點(diǎn)i的度，并根據(jù)式3計(jì)算每個(gè)節(jié)點(diǎn)的綜合影響力，然后將節(jié)點(diǎn)按影響力升序排序；

(5)

④設(shè)置迭代次數(shù)t=1；

⑤對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn)x，按式4計(jì)算其鄰居節(jié)點(diǎn)中出現(xiàn)的標(biāo)簽的影響力，再按式6，將其標(biāo)簽更新為鄰居節(jié)點(diǎn)標(biāo)簽集中影響力最大的標(biāo)簽；

(6)

⑥若網(wǎng)絡(luò)中所有節(jié)點(diǎn)的標(biāo)簽不再變化或者迭代次數(shù)達(dá)到最大值，則算法結(jié)束，具有相同標(biāo)簽的節(jié)點(diǎn)屬于同一社團(tuán)；否則t+1，返回步驟⑤。

可以看出，S-LPA算法用式3來(lái)計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的綜合影響力，并在后續(xù)的標(biāo)簽傳播過(guò)程中按照節(jié)點(diǎn)綜合影響力升序?qū)?biāo)簽進(jìn)行更新。之所以采用升序，是由于S-LPA算法的每一步標(biāo)簽更新基本是穩(wěn)定的，不存在標(biāo)簽?zāi)媪鳜F(xiàn)象，從影響力較小的節(jié)點(diǎn)開(kāi)始更新，使得這些影響力較小的節(jié)點(diǎn)的標(biāo)簽與未更新的影響力較大的標(biāo)簽一致。圖1(a)是一個(gè)包含8個(gè)節(jié)點(diǎn)的簡(jiǎn)單網(wǎng)絡(luò)，分別按綜合影響力的升序和降序運(yùn)行S-LPA算法，結(jié)果如圖1(b)、(c)所示。經(jīng)計(jì)算，各節(jié)點(diǎn)影響力為{1:13.25,3:13.25,5: 13.25,8:13.25,2:16.75,6:16.75,4:21.75,7:21.75}。假設(shè)節(jié)點(diǎn)4和7的標(biāo)簽分別為a、b，若采用降序，首先更新節(jié)點(diǎn)4或7，會(huì)導(dǎo)致兩社區(qū)合并成一個(gè)社區(qū)；若采用升序，首先更新節(jié)點(diǎn)1、3、5和8，對(duì)于節(jié)點(diǎn)1和3，其標(biāo)簽更新為節(jié)點(diǎn)4的標(biāo)簽a，當(dāng)更新到節(jié)點(diǎn)4時(shí)，節(jié)點(diǎn)4選擇鄰居中標(biāo)簽影響力最大的標(biāo)簽，此時(shí)節(jié)點(diǎn)1和3的標(biāo)簽影響力之和(即標(biāo)簽綜合影響力)為26.5，大于節(jié)點(diǎn)7的標(biāo)簽影響力21.75，節(jié)點(diǎn)4標(biāo)簽更新為a；同理節(jié)點(diǎn)7的標(biāo)簽更新為b。經(jīng)過(guò)2次迭代，算法達(dá)到穩(wěn)定狀態(tài)而停止。

(2)S-LPA算法時(shí)間復(fù)雜度分析。

網(wǎng)絡(luò)中所有節(jié)點(diǎn)初始化標(biāo)簽所需的時(shí)間復(fù)雜度為O(n)；計(jì)算所有節(jié)點(diǎn)的改進(jìn)的K-Shell值的時(shí)間復(fù)雜度為O(n)，計(jì)算節(jié)點(diǎn)歸一化度值的時(shí)間復(fù)雜度為O(n)，結(jié)合每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，所需的時(shí)間復(fù)雜度為O(dn)，d為網(wǎng)絡(luò)的平均度值，因此計(jì)算所有節(jié)點(diǎn)綜合影響力的時(shí)間復(fù)雜度為O(n+n+dn)～O(n)；使用計(jì)數(shù)排序?qū)?jié)點(diǎn)影響力升序排序，時(shí)間復(fù)雜度為O(n)；節(jié)點(diǎn)一次標(biāo)簽傳播的時(shí)間為O(m)，m為網(wǎng)絡(luò)中的邊數(shù)，最多傳播t次，所需時(shí)間為O(tm)；節(jié)點(diǎn)劃分到不同社團(tuán)所需的時(shí)間為O(n)。所以S-LPA算法總的時(shí)間復(fù)雜度為O(3n+tm)～O(n)，繼承了LPA算法時(shí)間復(fù)雜度近似線性的優(yōu)點(diǎn)。

(a)簡(jiǎn)單網(wǎng)絡(luò)

(b)升序結(jié)果

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

3.1 實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)

(1)模塊度。

模塊度(Q modularity)[13]是由Newman等提出的用來(lái)評(píng)價(jià)網(wǎng)絡(luò)社團(tuán)劃分質(zhì)量的指標(biāo)。對(duì)于一個(gè)不含重疊社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)，模塊度定義如下：

(7)

其中，m表示網(wǎng)絡(luò)中的邊數(shù)；Aij表示網(wǎng)絡(luò)的鄰接矩陣；ki、kj分別表示節(jié)點(diǎn)i、節(jié)點(diǎn)j的度值；δ(i,j)為克羅內(nèi)克函數(shù)，當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j屬于同一社團(tuán)時(shí)，δ(i,j)=1，節(jié)點(diǎn)i和節(jié)點(diǎn)j不屬于同一社團(tuán)時(shí)，δ(i,j)=0。模塊度的取值為0～1，值越接近1，說(shuō)明社團(tuán)劃分的質(zhì)量越好。

(2)標(biāo)準(zhǔn)化互信息。

標(biāo)準(zhǔn)化互信息(NMI)[14]是基于信息論的社區(qū)質(zhì)量評(píng)價(jià)指標(biāo)，可以用來(lái)衡量已知社團(tuán)結(jié)構(gòu)與算法所發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)之間的相似性。其定義如下：

(8)

其中，X表示真實(shí)社團(tuán)的集合；Y表示算法發(fā)現(xiàn)社團(tuán)的集合；H(X|Y)表示X在Y上的規(guī)范化條件熵。標(biāo)準(zhǔn)化互信息的取值為0～1，值越接近1，說(shuō)明算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)與真實(shí)社團(tuán)結(jié)構(gòu)一致性越高。

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

(1)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)。

實(shí)驗(yàn)采用四個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，分別是Zachary空手道俱樂(lè)部網(wǎng)絡(luò)Karate、Lusseau海豚社交網(wǎng)絡(luò)Dolphins、美國(guó)大學(xué)足球聯(lián)賽賽程表網(wǎng)絡(luò)Football和美國(guó)政治書(shū)籍網(wǎng)絡(luò)Polbooks，各自的特征信息如表1所示。

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

文中選擇經(jīng)典的LPA算法、LPA-E算法和KLPA算法同文中算法S-LPA進(jìn)行對(duì)比。由于LPA算法、LPA-E算法和KLPA算法存在隨機(jī)性，所有實(shí)驗(yàn)結(jié)果取運(yùn)行100次后的平均值，文中算法S-LPA運(yùn)行一次，表2給出了不同算法在四個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上運(yùn)行時(shí)得出的Q值、NMI值，以及平均迭代次數(shù)。

表2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集社團(tuán)劃分結(jié)果

從表2可以看出，S-LPA算法在四個(gè)真實(shí)網(wǎng)絡(luò)上的Q值和NMI值都要好于LPA算法，并且迭代次數(shù)也比LPA算法少。其中，在Karate網(wǎng)絡(luò)中發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)與實(shí)際社團(tuán)結(jié)構(gòu)一致，通過(guò)計(jì)算該網(wǎng)絡(luò)所有節(jié)點(diǎn)綜合影響力發(fā)現(xiàn)：節(jié)點(diǎn)1綜合影響力最大，為84；節(jié)點(diǎn)34綜合影響力僅次于節(jié)點(diǎn)1，為79.82；而實(shí)際情況是，節(jié)點(diǎn)1和節(jié)點(diǎn)34正好代表俱樂(lè)部分裂后分別以管理員和校長(zhǎng)為中心的兩個(gè)社團(tuán)。綜合Q值、NMI值以及迭代次數(shù)，S-LPA算法優(yōu)于LPA-E和KLPA算法，僅僅在Dolphins、Polbooks網(wǎng)絡(luò)上的Q值和NMI值低于LPA-E、KLPA算法，但是迭代次數(shù)比這兩個(gè)算法少。

(2)人工合成網(wǎng)絡(luò)上的實(shí)驗(yàn)。

為了進(jìn)一步測(cè)試文中算法對(duì)不同網(wǎng)絡(luò)的適用性以及穩(wěn)定性，使用LFR基準(zhǔn)網(wǎng)絡(luò)生成工具[15]生成兩個(gè)人工合成網(wǎng)絡(luò)，分別包含1 000和2 000個(gè)頂點(diǎn)，具體參數(shù)見(jiàn)表3。

表3 人工合成網(wǎng)絡(luò)參數(shù)

其中，k表示網(wǎng)絡(luò)的平均度值；maxk表示網(wǎng)絡(luò)的最大度值；minc和maxc分別表示社團(tuán)所含節(jié)點(diǎn)數(shù)的最小值和最大值；mu為混合參數(shù)，表示連接不同社團(tuán)節(jié)點(diǎn)的邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例，通過(guò)設(shè)置不同的mu值來(lái)測(cè)試算法的性能。當(dāng)mu<0.5時(shí)，mu值越小，人工合成的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)越明顯；當(dāng)mu>0.5時(shí)，mu值越大，合成的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)越模糊。

將S-LPA算法與LPA算法和KLPA算法進(jìn)行對(duì)比，同樣，文中算法運(yùn)行一次，LPA和KLPA算法各運(yùn)行100次，在節(jié)點(diǎn)數(shù)N=1 000、2 000和不同mu值下NMI值的變化分別如圖2(a)和圖2(b)所示。

由圖2可以看出，當(dāng)mu≤0.45時(shí)，網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)較為明顯，S-LPA算法與LPA算法、KLPA算法相當(dāng)；當(dāng)0.5≤mu≤0.6時(shí)，網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)漸漸模糊，S-LPA算法的NMI值明顯高于LPA算法和KLPA算法；當(dāng)mu=0.65時(shí)，S-LPA在G1網(wǎng)絡(luò)中的NMI值仍然高于LPA和KLPA算法，而在G2網(wǎng)絡(luò)中LPA和S-LPA算法失效，KLPA算法的NMI值為0.4；當(dāng)mu>0.65時(shí)，3種算法均失效?？傮w來(lái)說(shuō)，S-LPA算法在G1和G2人工合成網(wǎng)絡(luò)上的性能要優(yōu)于LPA算法和KLPA算法。

為了測(cè)試算法的穩(wěn)定性，分別在N=1 000、2 000和mu=0.5的情況下運(yùn)行多次LPA算法和S-LPA算法，并統(tǒng)計(jì)其平均迭代次數(shù)，結(jié)果如圖3(a)和圖3(b)所示。

(a)N=1 000

(b)N=2 000

(a)N=1 000

(b)N=2 000

由圖3可以看出，LPA算法在不同運(yùn)行次數(shù)下平均迭代次數(shù)均不同，而文中的S-LPA算法在N=1 000和N=2 000的情況下迭代次數(shù)都為6次。相比于LPA算法，S-LPA算法不僅降低了LPA算法的隨機(jī)性，還明顯減少了LPA算法的迭代次數(shù)。

4 結(jié)束語(yǔ)

傳統(tǒng)的LPA算法以及一些改進(jìn)的LPA算法雖然具有近似線性的時(shí)間復(fù)雜度，但是仍然存在結(jié)果不穩(wěn)定的問(wèn)題。文中對(duì)LPA算法的標(biāo)簽更新序列進(jìn)行改進(jìn)，綜合考慮節(jié)點(diǎn)的局部信息和全局信息，以此來(lái)計(jì)算節(jié)點(diǎn)在網(wǎng)絡(luò)中的綜合影響力，并進(jìn)一步用標(biāo)簽影響力對(duì)LPA算法標(biāo)簽更新策略進(jìn)行改進(jìn)。通過(guò)在真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)上的實(shí)驗(yàn)證明了S-LPA算法僅需運(yùn)行一次就能得到社團(tuán)劃分結(jié)果，并且劃分結(jié)果的Q值和NMI值優(yōu)于傳統(tǒng)的LPA算法，在繼承了LPA算法線性時(shí)間復(fù)雜度的同時(shí)，提高了社團(tuán)劃分的質(zhì)量，增強(qiáng)了算法的穩(wěn)定性。