基于節點中心性和社區相似性的快速標簽傳播算法

顧軍華 ，霍士杰，王守彬，田 喆

(1．河北工業大學計算機科學與軟件學院，天津300401; 2．河北省大數據實驗室(河北工業大學)，天津300401)(*通信作者電子郵箱jhgu_hebut@163．com)

0 引言

自然界與人類社會中的許多系統都可以用復雜網絡模型表示，網絡社區結構是復雜網絡中最普遍和最重要的拓撲屬性。社區發現算法可以通過分析網絡中節點之間的關聯性，挖掘復雜網絡中的社區結構，從而揭示復雜網絡中隱含的特性和功能，對于網絡結構的理論研究和網絡分析的實際應用有著重要的作用。

2007年 Raghavan等［1］首次將標簽傳播算法(Label Propagation Algorithm，LPA)應用于社區發現。與傳統的社區發現方法(基于層次聚類的算法［2－3］、基于隨機游走的算法［4］等)相比，LPA僅依賴于網絡的傳播特性，且具有線性的時間復雜度，適合用于對復雜網絡進行社區發現和分析的優點。但是LPA也有一些缺點:1)節點更新順序具有隨機性，并且當鄰接節點中出現次數最多的標簽(最大值標簽)有多個時，會隨機選擇一個標簽;2)存在不必要的標簽更新過程;3)更新標簽時僅僅考慮鄰接節點中標簽出現的次數，忽略鄰接節點的局部結構信息。這些缺點會導致算法延遲收斂，社區發現的結果準確率低且穩定性差的問題。針對以上問題，2014年，Xing等［5］提出了基于節點影響力的標簽傳播算法(Node Influence Based Label Propagation Algorithm for community detection in networks，NIBLPA)，該算法使用k-shell分解方法計算每一個節點的影響力值，依據影響力值從高到低的順序更新標簽和選取標簽，提高了算法的穩定性和準確率，但是時間復雜度也有所提升。2015年，Sun等［6］提出了基于中心性的標簽傳播算法(Centrality-based Label Propagation algorithm for community detection in networks，Cen_LP)，該算法為每一個節點定義了節點中心值和節點偏向值，依據節點中心值從低到高的順序更新標簽并且利用節點偏向值選取標簽，算法在不增加時間復雜度的情況下，提高了社區發現的準確率。2017年，Ma等［7］提出了基于節點重要性和隨機游走的標簽傳播算法(An improved Label Propagation Algorithm based on Node Importance and random walk for community detection，NILPA)，該算法依據節點的度數計算節點重要性，并且依據隨機游走理論形成節點相似度矩陣，在兩者的基礎上形成新的度量標準來衡量節點之間的緊密程度，依據該度量標準更新標簽。算法提高了社區發現的準確率，但由于計算節點相似性依賴于矩陣相乘，在網絡規模不斷擴大時，會消耗越來越多計算資源，而且時間復雜度也較高。綜上所述，盡管上述算法在準確率上有所提高，但是都提高了算法的時間復雜度，降低了算法的執行速度。

為了在加快算法的執行速度的基礎上提高算法準確率和穩定性，本文提出了基于節點中心性和社區相似性的快速標簽傳播算法(Fast Label Propagation Algorithm based on the Node Centrality and Community Similarity，FNCS_LPA)。FNCS_LPA首先計算每一個節點的中心性度量值，按照中心性度量值從低到高的順序排序并加入到節點信息列表中，用節點信息列表指導更新過程，通過記錄節點信息列表中每一個節點的狀態信息，判斷當前節點是否需要更新，從而避免了不必要的更新，提高了運行速度。在更新過程中，FNCS_LPA利用基于社區相似性的更新規則，即不僅僅考慮鄰接節點中標簽出現的次數，還會評估每個鄰接節點與待更新節點的相似性，社區相似性依賴于節點相似性求和，待更新節點會選擇社區相似性最高的社區，從而提高算法的準確率。

1 基于節點中心性的快速標簽傳播算法

1．1 基于節點中心性的更新順序

在LPA的每一次迭代過程中，節點的更新順序是隨機的，這等同于平等對待網絡中的所有節點。事實上，網絡中的每個節點的重要程度依賴于其在網絡中的局部信息，并不是同等的，如果平等對待，按隨機的順序更新標簽，可能會造成結果與實際不符，導致算法準確率低且穩定性差的問題。基于此，本文提出了基于節點中心性的更新順序，其中，節點中心性依賴于節點的聚集系數(Clustering Coefficient)和節點密度。假設節點i和節點j是網絡中的兩個節點。

定義1 節點的聚集系數。節點i的聚集系數定義如下:

其中:Ni表示節點i的鄰接節點集合，|Ni|表示節點i的鄰接節點數，E(i)表示節點i的鄰接點之間實際的連邊數。節點的聚集系數可表示為當前節點的所有鄰節點之間實際連邊數與所有可能連邊數的比值，由于節點的鄰接點之間實際存在的邊不會大于可能存在的最大值，因此節點的聚集系數的取值范圍在0～1:當節點的度數為0或1時，或者當節點的鄰接點之間相互獨立時，該節點的聚集系數為0;當節點的聚集系數為1時，則表示該節點與其鄰接點之間構成完全圖。因此節點的聚集系數越高，說明節點具有越高的聚集度。

定義2 節點密度。節點i的密度定義如下:

定義3 節點中心性度量值。

節點中心性度量值表示為節點密度和節點聚集系數的乘積，δi的值越大，表明節點在網絡中的重要程度越高。在實際生活中，重要程度高的節點為專家，而重要程度低的節點為普通求知者，普通求知者都是聽取專家的知識，從而完成知識傳播。同樣，在標簽傳播過程中，標簽就是知識，節點就是人，重要程度低的節點往往要先采納周圍重要程度高的節點的標簽，從而完成標簽傳播。因此，節點δi的值越小，該節點就越先更新標簽，這樣得到的結果才會與實際相符，因此節點的更新順序按照節點中心性度量值升序更新。

1．2 基于節點中心性的快速標簽傳播算法

LPA運行在線性時間內，具有執行速度快的優點。LPA在前幾次迭代過程中節點改變標簽的概率是非常高的，但是，在5次迭代以后，95%以上的節點都會被正確地劃分(當前節點的標簽已經變為鄰接節點中最大值標簽)。為了說明這一現象，本文將 LPA分別應用在 CA-Hepth、CA-GrQc、Email和PGP這4種常用的真實網絡數據集上進行社區發現，本文實驗將每一個真實網絡都看作無向無權圖，每一個圖都沒有自循環的邊并且只取圖的最大連通子圖。本文所有的實驗均使用Python語言實現，在 Window 7，AMD Core A8-4555 CPU 1．6 GHz，8 GB 內存環境下進行。

1．2．1 實驗一:LPA的收斂性

數據集詳細信息如表1所示，計算5次迭代以后已被正確劃分的節點占總節點的百分比。每個網絡重復100次實驗，4種網絡的收斂信息如表2所示。

表1 第一部分數據集介紹Tab．1 Introduction of the first part datasets

表2 網絡的收斂信息Tab．2 Convergence information of networks

從表2可以看出，在5次迭代以后，Email網絡有96．64%的節點被正確劃分，CA-Hepth網絡有98．97%的節點被正確劃分，Email和PGP網絡有99%以上的節點都已被正確劃分。這說明無論總的迭代次數是多少，LPA在5次迭代以后，95%以上的節點都已經得到了正確的劃分，而5次迭代后的每一次迭代，僅僅較少的節點標簽會發生改變，而對于大部分的節點來說，即使更新標簽，也不會改變標簽，這些不必要的更新拖慢了算法的收斂速度。針對這一問題，本節提出基于節點中心性的快速標簽傳播算法。

1．2．2 實驗二:LPA與FNC_LPA的對比

LPA在每次迭代過程中，對節點標簽的更新有兩種情況:一種是鄰接節點中的最大值的標簽只有一個，另一種是鄰接節點中的最大值標簽有多個。如果當前節點的標簽已經是鄰接節點中的唯一最大值標簽，這樣的節點稱為被動節點，被動節點在本次更新中不會再改變標簽;如果鄰接節點中的最大值標簽有多個，當前節點的標簽是其中之一，這樣的節點稱為干擾節點，根據LPA的更新規則，干擾節點會隨機選擇其中一個標簽，干擾節點在本次更新中可能會改變標簽。被動節點和干擾節點以外的其他節點是主動節點，主動節點在本次更新中一定會改變標簽。如果能避免對被動節點的標簽更新，算法會以更快的速度收斂，因此，本文構建一個節點信息列表，其中包含所有的節點和每個節點的狀態信息(被動、干擾和主動)。每次只選擇信息列表中的干擾和主動節點進行標簽更新，標簽更新完成后再進行狀態更新。

基于節點中心性的快速標簽傳播算法(Fast Label Propagation Algorithm based on Node Centrality，FNC_LPA)的具體流程如下:

第一步 按照式(1)、式(2)和式(3)計算節點的中心性度量值，將所有的節點按照節點中心性度量值降序排序并加入節點信息列表當中。每一個節點都被初始化為一個獨一無二的標簽，都被設置為主動節點。

第二步 從節點信息列表中隨機選擇一個主動節點或干擾節點，按照節點標簽更新規則，對當前節點的標簽進行更新。標簽更新完成后對該節點及其鄰接節點進行狀態更新，節點在更新狀態時，可能會更新為被動節點、主動節點和干擾節點。

第三步 根據節點狀態判斷節點信息列表中是否還有主動節點:若有，繼續執行第二步;否則，算法結束。

為了評估FNC_LPA的有效性，本次實驗包括表1和表3中的8個真實網絡數據集。對8種數據集分別使用FNC_LPA和LPA進行社區發現，對比算法收斂時所需的迭代次數和模塊度［11］。模塊度是一種比較重要的衡量網絡社區結構強度的方法，計算公式如下:

其中:Lc表示社區c內部的鏈接數，m表示整個網絡邊的總個數，Dc表示社區c內部節點的度數總和，L表示整個網絡的全部社區。

表3 第二部分數據集介紹Tab．3 Introduction of the second part datasets

表4 LPA和FNC_LPA平均模塊度對比Tab．4 Comparison of average modularity between LPA and FNC_LPA

為了使算法具有可比性，FNC_LPA與LPA使用相同的更新規則(當前節點的標簽選取鄰接節點中的最大值標簽)。FNC_LPA的迭代次數記為算法總更新次數和節點總個數的比值。模塊度和迭代次數為對每一個網絡重復100次實驗后所求得的平均值，迭代次數對比如圖1所示，可以看出，因為FNC_LPA避免了很多不必要的更新，所以迭代次數明顯少于LPA。在 karate、dolphins、polbooks和 netscience 網絡上，FNC_LPA的迭代次數是LPA的1/5至1/2左右，在Email和CAGrQc網絡上，FNC_LPA是LPA的1/6左右，在CA-Hepth和PGP網絡上，FNC_LPA是LPA的1/10左右。平均模塊度對比如表4所示，可以看出，與 LPA相比，FNC_LPA除了在Email和CA-Hepth網絡上模塊度有小幅提升以外，在其余網絡上模塊度幾乎沒有發生變化。因此，實驗結果證明FNC_LPA在沒有改變社區發現效果的基礎上，能夠大幅度降低迭代次數。

圖1 FNC_LPA和LPA的迭代次數對比Fig．1 Comparison of iterations between FNC_LPA and LPA

2 基于社區相似性的更新規則

LPA的更新規則僅僅考慮鄰接節點的標簽出現次數，并且當前節點的標簽更新為鄰接節點中最大值標簽，具有相同標簽的節點看作一個社區，這種更新規則默認是將每一個鄰接節點與當前節點的相似性(社區相似性依賴于節點相似性求和)看作是相同的，LPA最終是將最大值標簽所代表的社區作為與當前節點相似性最高的社區。實際上，每一個鄰接節點與當前節點的相似性并不是同等的，如果同等對待，會導致算法準確率低且穩定性差的問題。本章提出基于社區相似性的更新規則，社區相似性是由節點相似性求和得到，其中節點相似性依賴于節點之間的公共節點個數和節點的度數，基于社區相似性的更新規則會使待更新節點選擇鄰接節點的社區中相似性最高的社區。

本章對算法中使用的主要概念進行形式化定義，如下所示:

定義4 邊緣度數比。假設節點i和節點j是圖中的兩個節點，i與j的邊緣度數比定義如下:

其中:sim(i，j)表示節點i和節點j的公共節點的個數，di表示節點i的度。

定義5 節點相似性。節點j對節點i的重要程度定義如下:

其中:c1和c2是取值在0～1的兩個常數，ρij是節點i和節點j的邊緣度數比。

定義6 社區相似性。節點i與社區l的相似性定義如下:

定義7 近似最大值標簽。在LPA中，當前更新的節點的標簽選取鄰接節點中的最大值標簽，將這個標簽的出現次數記為max;然而，如果鄰接節點某類標簽的出現次數(計為n)和max的值相差不大時，這類標簽稱為近似最大值標簽。算法引入一個取值在0～1的常量Radio來衡量近似程度。

若鄰接節點中標簽出現次數n滿足式(8)，都稱之為近似最大值標簽。正在更新的當前節點也可能選擇近似最大值標簽，其中，在更新過程中為了不考慮節點數量較少的標簽，Radio的值不宜設置過大，應在0～0．5。近似最大值標簽的引入，避免了對每一個社區進行相似性計算，提高了算法效率。

定義8 基于社區相似性的更新規則。假設集合T中保存了節點i的鄰接節點中的最大值標簽(社區)和近似最大值標簽，L(i)表示節點i的標簽，基于社區相似性的更新規則如式(9)所示:

式(9)是在集合T中，讓節點i選擇使得S(i，l)最大的一類標簽，如果有多類標簽使得S(i，l)最大，就從中隨機選取。

為了驗證該更新規則的有效性，本次實驗在LPA中使用基于社區相似性的更新規則形成基于社區相似性的標簽傳播算法(LabelPropagationAlgorithmbasedonCommunity Similarity，CS_LPA)，CS_LPA的節點更新的順序是隨機的。其中式(6) 中的c1取值1，c2取值0．2，式(8) 中的Radio值取0．4。本次實驗除了使用表1和表3中的8種真實網絡數據集，還應用了LFR(Lancichinetti Fortunato Radicchi)基準網絡。LFR基準程序是由Lancichinetti等［16］提出的專門用于生成模擬網絡的算法，該算法主要根據輸入的參數，盡可能地生成符合真實網絡特征的人工合成網絡，因此具有較高的實驗價值，是當前社區發現研究中最為常用的模擬數據集。在生成LFR基準網絡時常用的參數如表5所示，其中mu表示節點與社區外部連接的概率，其值在0～1，mu值越大，表明社區的結構越不明顯，社區發現的難度也越大。本次實驗使用的LFR基準網絡數據集如表6所示，其中包含4組LFR基準網絡，每組包含15個不同 mu值的網絡，mu的取值在0．1 ～0．8，間隔為0．05。相比2000S(5000S)網絡，2000B(5000B)網絡中每一社區內的節點個數較多。

表5 LFR基準網絡的主要參數Tab．5 Parameters of LFR benchmark network

表6 LFR基準網絡數據集描述Tab．6 Description of LFR benchmark network datasets

歸一化互信息(Normal Mutual Information，NMI)［17］能夠量化算法對網絡進行的劃分和網絡的真實劃分之間的關系，是一種在社區發現領域常用的度量標準。NMI的取值在0～1，其計算式(10)所示:

其中:A是網絡的真實劃分，B是算法對網絡所進行的劃分，CA表示A種劃分的社區個數，CB表示B種劃分的社區個數，N表示一個矩陣，Nij表示A種劃分第i個社區中的節點出現在B種劃分第j個社區中的節點個數，Ni·表示矩陣N第i行的求和，N·j表示矩陣N第j列的求和。n表示整個網絡節點的個數。如果A種劃分和B種劃分是相同的，則NMI(A，B)的值為1。NMI的值越高，表示算法社區發現的準確率越高。

將CS_LPA和LPA分別用在表1和表3的8種真實網絡數據集和4種LFR基準網絡數據集上進行社區發現，對每一個網絡重復100次實驗。在8種真實網絡數據集上與LPA對比平均模塊度，對比如表7所示:在所用的數據集上，CS_LPA的模塊度都比 LPA要高;其中，在 Email、CA-Hepth、dolphins和netscience網絡上，CS_LPA模塊度有明顯的提高。由于LFR基準網絡已知真實的劃分結果，因此在LFR基準網絡數據集上與LPA對比平均NMI值。NMI的對比如圖2所示。

圖2 LFR基準網絡上CS_LPA和LPA的NMI對比Fig．2 NMI comparison of CS_LPA and LPA on LFR benchmark network

從圖2(a)可以看出，mu的值在0．1～0．45時，兩種算法都能較好地發現社區結構;mu的值在0．45～0．6時，LPA的NMI值迅速下降，表明社區發現的準確率在下降，而CS_LPA的NMI的值遠高于LPA;mu的值在0．65～0．8，LPA已無法進行社區發現，而CS_LPA仍可進行。圖2(b)產生了類似于圖2(a)的效果，mu的值在0．1～0．4時，兩種算法都能較好地發現社區結構，而 mu的值在0．45～0．8時，CS_LPA的NMI值高于LPA。在圖2(c)和圖2(d)中，當 mu大于0．6時，CS_LPA的NMI明顯高于LPA。

綜上所述，相比LPA，CS_LPA提高了社區發現的準確率，尤其對于社區結構不清晰的網絡，算法的優勢更加明顯。

表7 LPA與CS_LPA平均模塊度對比Tab．7 Comparison of average modularity between LPA and CS_LPA

3 FNCS_LPA算法

3．1 算法流程

在第1章和第2章中，本文分別引入了基于節點中心性的快速更新過程和基于社區相似性的更新規則，在基于節點中心性的快速更新過程中引入基于社區相似性的更新規則，形成基于節點中心性和社區相似性的快速標簽傳播算法(FNCS_LPA)。算法的偽代碼如下:

FNCS_LPA:

輸入 G(V，E)、c1、c2、Radio;

/*輸入圖的鄰接矩陣和式(6)，式(8)的參數*/

輸出 社區劃分結果。

1) 為每個節點分配一個獨一無二的標簽;

2) 按式(1)～(3)計算所有節點的中心性度量值，按照升序的順序添加到節點信息列表當中，將所有的節點標記為主動節點;

3) 從節點信息列表中隨機選取一個主動節點或干擾節點，記為i;

4) 將當前節點i的鄰接節點中出現次數最多的標簽和近似最大值標簽加入集合T當中;

5) 初始化maxLabel集合為空;maxLabel記錄與當前節點i相似性最高的一個或多個標簽。

6) for each l∈T do

7) maxS←0;

8) 依據式(6)計算S(i，l);

9) if S(i，l)==maxS then

10) 將l標簽添加到maxLabel中;

11) else if S(i，l) ＞ maxS then

12) maxS ← S(i，l);

13) 從maxLabel中移除所有元素;

14) 將l標簽添加到maxLabel中;

15) end if

16)end for

17)當前節點i從maxLabel集合中隨機選取標簽;

18)for each j∈N(i)∩ i do

/* 更新當前節點i和i的鄰接節點的狀態*/

19) if node j is interference node then

20) 標記j為干擾節點;

21) else if node j is passive node then

22) 標記j為被動節點;

23) else

24) 標記j為主動節點;

25) end if

26)end for

27)如果節點信息列表仍含有主動節點，跳到第3)步;

28)將具有相同標簽的節點劃分到一個社區當中，算法結束

3．2 時間復雜度

與LPA相比，FNCS_LPA的總體時間復雜度沒有改變。首先按照節點中心性度量值對網絡節點進行排序，排序算法選擇較快的桶排序，其時間復雜度接近于O(n)，n表示網絡中的節點個數。初始化節點信息列表的時間復雜度是O(n);從節點信息列表中隨機選擇一個節點時間復雜度為O(1);更新當前節點的標簽的時間復雜度是O(di)，di是節點i的度數，因此在整個更新過程中，時間復雜度是O(m)，m是邊的個數。通過使用節點信息列表，算法的收斂比較簡單，僅僅判斷節點的狀態標記即可，最差的情況是 O(n)。因此FNCS_LPA算法的總體時間復雜度是O(m)。

4 實驗結果與分析

為了驗證FNCS_LPA的有效性，本次實驗選取了第1章提到的 NIBLPA［5］、Cen_LP［6］和 NILPA［7］三種較好的改進LPA，數據集選取了表1和表3中的8種真實網絡數據集和表6中的4種LFR基準網絡數據集。其中式(6)的c1的值為1，c2的值為0．2，式(8) 的 Radio值為0．4。

4．1 執行速度對比

將FNCS_LPA、Cen_LP、NIBLPA和NILPA分別應用到真實網絡數據集中進行社區發現。為了具有可比性，每一個算法的終止條件都是節點標簽成為鄰接節點中的最大值標簽，對每一個網絡重復100次實驗求平均的迭代次數，得到的結果如圖3所示。

圖3 FNCS_LPA與三種改進LPA的迭代次數對比Fig．3 Comparison of iterations between FNCS_LPA and other three improved LPA algorithms

從圖3可以看出，與Cen_LP相比，FNCS_LPA在所有的數據集上的迭代次數明顯要比Cen_LP少很多，這是因為FNCS_LPA避免了很多不必要的更新。在 karate、dolphins、polbooks和netscience網絡上，FNCS_LPA的迭代次數是Cen_LP的1/4至1/2左右;在Email、CA-GrQc和PGP網絡中，算法的迭代次數是Cen_LP的1/10左右;而在CA-Hepth數據集上，算法的迭代次數是Cen_LP的1/30左右。與NIBLPA相比，FNCS_LPA在各個數據集上的迭代次數為NIBLPA的1/16到1/3左右。與NILPA相比，FNCS_LPA在各個數據集上的迭代次數為NIBLPA的1/14到1/2左右。綜上所述，與其他三種算法相比，FNCS_LPA明顯提高了算法的執行速度。

4．2 模塊度對比

將4種算法應用在8種真實網絡數據集上進行社區發現，并在最低模塊度、平均模塊度和最高模塊度方面進行對比，模塊度的計算公式如式(1)所示。平均模塊度(average)是對每一個真實網絡作100次實驗求取的平均值，最低模塊度(min)和最高模塊度(max)分別是對每一個真實網絡作100次實驗后求取的最差結果和最優結果。模塊度的對比如表8所示，其中加粗的數據表明4種算法中對應每一個網絡的最好結果。

表8 FNCS_LPA與三種改進LPA算法模塊度對比Tab．8 Comparison of modularity between FNCS_LPA and other three improved LPA algorithms

從表8中可以看出，FNCS_LPA在所有的數據集上的最低模塊度、平均模塊度和最高模塊度均完全一致。在karate網絡上，FNCS_LPA和NILPA都將網絡劃分為兩個社區，求得的結果與真實劃分完全相同;在dolphins和polbooks網絡上，FNCS_LPA在最低模塊度、平均模塊度和最高模塊度上，均接近于最優解;盡管Email網絡沒有在最高模塊度方面取得最好的結果，但是從平均模塊度和最低模塊度方面，FNCS_LPA仍是最有優勢的;而在netscience、CA-GrQc、CA-Hepth和PGP等網絡上，FNCS_LPA的模塊度明顯高于其他幾種算法。綜上所述，FNCS_LPA相比其他3種算法提高了社區發現的準確率和穩定性;尤其在較大規模的網絡算法，算法的優勢更加明顯。

4．3 歸一化互信息對比

本次實驗將4種算法應用在表6中的LFR基準網絡數據集上進行社區發現，并在歸一化互信息度量(NMI)方面進行對比，NMI的計算公式如式(7)所示。對每一個網絡重復100次實驗求取平均NMI值。實驗結果如圖4所示。

圖4 LFR基準網絡上FNCS_LPA與三種改進LPA算法的NMI對比Fig．4 NMI comparison of FNCS_LPA and other three improved LPA algorithms on LFR benchmark network

從圖4可以直觀地看出，隨著mu的值不斷增大，社區結構越來越不清晰，4種算法的社區發現準確率都在下降。從圖4(a)可以看出:當mu的值在0．1～0．4時，4種算法都能較好地發現社區結構;mu的值在0．4～0．8時，FNCS_LPA的NMI的值高于其他3種算法。在圖4(b)中，mu的值在0．35～0．45時，FNCS_LPA 略低于 NILPA;但 mu 的值在 0．6～0．8時，FNCS_LPA的 NMI值都是4種算法中最高的。圖4(c)和圖4(d)產生了類似的效果，當mu的值大于0．5時，FNCS_LPA社區發現的準確率明顯高于其他3種算法。綜上所述，FNCS_LPA相比其他3種算法提高了社區發現的準確率;尤其對于社區結構不清晰的網絡，FNCS_LPA的效果更好，準確率更高。

5 結語

本文提出了基于節點中心性和社區相似性的快速標簽傳播算法。首先，該算法計算每一個節點的中心度量值，依據節點中心性度量值升序將節點加入節點信息列表，利用節點信息列表指導更新過程，通過記錄每一個節點的更新狀態，避免了許多不必要的更新，減少了迭代次數，從而提高了社區發現的穩定性和執行速度。為了驗證基于節點中心性的快速更新過程的有效性，實驗使用了8種真實網絡在迭代次數和平均模塊度方面與LPA進行了對比。其次，算法引入社區相似性的更新規則，即當前節點會加入與當前節點社區相似性最高的社區，提高了社區發現的準確率，為了驗證基于社區相似性的更新規則的有效性，算法在平均模塊度、NMI方面與LPA進行了對比。最后，將基于節點中心性的快速更新過程和基于社區相似性的更新規則結合形成本文提出的基于節點中心性和社區相似性的快速標簽傳播算法，與目前3種改進的LPA在迭代次數、模塊度和NMI三個方面進行了對比，實驗結果表明FNCS_LPA在提升算法執行速度的基礎上，提高了算法的穩定性和準確率。