穩(wěn)定的標(biāo)簽傳播社團(tuán)劃分算法研究

張 猛，李玲娟

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

0 引 言

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

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

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

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

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

1 相關(guān)知識

1.1 LPA算法

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

(1)

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

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

1.2 LPA存在的問題

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

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

(2)在標(biāo)簽更新過程中，當(dāng)待更新節(jié)點的鄰居節(jié)點中次數(shù)最多的標(biāo)簽有多個時，LPA算法隨機選擇一個標(biāo)簽作為待更新節(jié)點的標(biāo)簽，沒有考慮鄰居節(jié)點信息對標(biāo)簽選擇的影響。

2 S-LPA算法

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

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

(1)K-Shell算法。

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

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

(2)節(jié)點綜合影響力計算方法。

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

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

(2)

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

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

(3)

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

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

2.2 標(biāo)簽影響力

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

(4)

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

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

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

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

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

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

算法步驟：

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

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

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

(5)

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

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

(6)

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

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

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

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

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

(b)升序結(jié)果

3 實驗結(jié)果與分析

3.1 實驗結(jié)果評價指標(biāo)

(1)模塊度。

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

(7)

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

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

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

(8)

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

3.2 實驗結(jié)果分析

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

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

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

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

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

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

(2)人工合成網(wǎng)絡(luò)上的實驗。

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

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

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

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

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

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

(a)N=1 000

(b)N=2 000

(a)N=1 000

(b)N=2 000

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

4 結(jié)束語

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