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

(1．河北工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院，天津300401; 2．河北省大數(shù)據(jù)實(shí)驗(yàn)室(河北工業(yè)大學(xué))，天津300401)(*通信作者電子郵箱jhgu_hebut@163．com)

0 引言

自然界與人類社會中的許多系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)模型表示，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中最普遍和最重要的拓?fù)鋵傩?。社區(qū)發(fā)現(xiàn)算法可以通過分析網(wǎng)絡(luò)中節(jié)點(diǎn)之間的關(guān)聯(lián)性，挖掘復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，從而揭示復(fù)雜網(wǎng)絡(luò)中隱含的特性和功能，對于網(wǎng)絡(luò)結(jié)構(gòu)的理論研究和網(wǎng)絡(luò)分析的實(shí)際應(yīng)用有著重要的作用。

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

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

1 基于節(jié)點(diǎn)中心性的快速標(biāo)簽傳播算法

1．1 基于節(jié)點(diǎn)中心性的更新順序

在LPA的每一次迭代過程中，節(jié)點(diǎn)的更新順序是隨機(jī)的，這等同于平等對待網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。事實(shí)上，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)的重要程度依賴于其在網(wǎng)絡(luò)中的局部信息，并不是同等的，如果平等對待，按隨機(jī)的順序更新標(biāo)簽，可能會造成結(jié)果與實(shí)際不符，導(dǎo)致算法準(zhǔn)確率低且穩(wěn)定性差的問題?；诖耍疚奶岢隽嘶诠?jié)點(diǎn)中心性的更新順序，其中，節(jié)點(diǎn)中心性依賴于節(jié)點(diǎn)的聚集系數(shù)(Clustering Coefficient)和節(jié)點(diǎn)密度。假設(shè)節(jié)點(diǎn)i和節(jié)點(diǎn)j是網(wǎng)絡(luò)中的兩個節(jié)點(diǎn)。

定義1 節(jié)點(diǎn)的聚集系數(shù)。節(jié)點(diǎn)i的聚集系數(shù)定義如下:

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

定義2 節(jié)點(diǎn)密度。節(jié)點(diǎn)i的密度定義如下:

定義3 節(jié)點(diǎn)中心性度量值。

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

1．2 基于節(jié)點(diǎn)中心性的快速標(biāo)簽傳播算法

LPA運(yùn)行在線性時間內(nèi)，具有執(zhí)行速度快的優(yōu)點(diǎn)。LPA在前幾次迭代過程中節(jié)點(diǎn)改變標(biāo)簽的概率是非常高的，但是，在5次迭代以后，95%以上的節(jié)點(diǎn)都會被正確地劃分(當(dāng)前節(jié)點(diǎn)的標(biāo)簽已經(jīng)變?yōu)猷徑庸?jié)點(diǎn)中最大值標(biāo)簽)。為了說明這一現(xiàn)象，本文將 LPA分別應(yīng)用在 CA-Hepth、CA-GrQc、Email和PGP這4種常用的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行社區(qū)發(fā)現(xiàn)，本文實(shí)驗(yàn)將每一個真實(shí)網(wǎng)絡(luò)都看作無向無權(quán)圖，每一個圖都沒有自循環(huán)的邊并且只取圖的最大連通子圖。本文所有的實(shí)驗(yàn)均使用Python語言實(shí)現(xiàn)，在 Window 7，AMD Core A8-4555 CPU 1．6 GHz，8 GB 內(nèi)存環(huán)境下進(jìn)行。

1．2．1 實(shí)驗(yàn)一:LPA的收斂性

數(shù)據(jù)集詳細(xì)信息如表1所示，計算5次迭代以后已被正確劃分的節(jié)點(diǎn)占總節(jié)點(diǎn)的百分比。每個網(wǎng)絡(luò)重復(fù)100次實(shí)驗(yàn)，4種網(wǎng)絡(luò)的收斂信息如表2所示。

表1 第一部分?jǐn)?shù)據(jù)集介紹Tab．1 Introduction of the first part datasets

表2 網(wǎng)絡(luò)的收斂信息Tab．2 Convergence information of networks

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

1．2．2 實(shí)驗(yàn)二:LPA與FNC_LPA的對比

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

基于節(jié)點(diǎn)中心性的快速標(biāo)簽傳播算法(Fast Label Propagation Algorithm based on Node Centrality，F(xiàn)NC_LPA)的具體流程如下:

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

第二步 從節(jié)點(diǎn)信息列表中隨機(jī)選擇一個主動節(jié)點(diǎn)或干擾節(jié)點(diǎn)，按照節(jié)點(diǎn)標(biāo)簽更新規(guī)則，對當(dāng)前節(jié)點(diǎn)的標(biāo)簽進(jìn)行更新。標(biāo)簽更新完成后對該節(jié)點(diǎn)及其鄰接節(jié)點(diǎn)進(jìn)行狀態(tài)更新，節(jié)點(diǎn)在更新狀態(tài)時，可能會更新為被動節(jié)點(diǎn)、主動節(jié)點(diǎn)和干擾節(jié)點(diǎn)。

第三步 根據(jù)節(jié)點(diǎn)狀態(tài)判斷節(jié)點(diǎn)信息列表中是否還有主動節(jié)點(diǎn):若有，繼續(xù)執(zhí)行第二步;否則，算法結(jié)束。

為了評估FNC_LPA的有效性，本次實(shí)驗(yàn)包括表1和表3中的8個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集。對8種數(shù)據(jù)集分別使用FNC_LPA和LPA進(jìn)行社區(qū)發(fā)現(xiàn)，對比算法收斂時所需的迭代次數(shù)和模塊度［11］。模塊度是一種比較重要的衡量網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)強(qiáng)度的方法，計算公式如下:

其中:Lc表示社區(qū)c內(nèi)部的鏈接數(shù)，m表示整個網(wǎng)絡(luò)邊的總個數(shù)，Dc表示社區(qū)c內(nèi)部節(jié)點(diǎn)的度數(shù)總和，L表示整個網(wǎng)絡(luò)的全部社區(qū)。

表3 第二部分?jǐn)?shù)據(jù)集介紹Tab．3 Introduction of the second part datasets

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

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

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

2 基于社區(qū)相似性的更新規(guī)則

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

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

定義4 邊緣度數(shù)比。假設(shè)節(jié)點(diǎn)i和節(jié)點(diǎn)j是圖中的兩個節(jié)點(diǎn)，i與j的邊緣度數(shù)比定義如下:

其中:sim(i，j)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的公共節(jié)點(diǎn)的個數(shù)，di表示節(jié)點(diǎn)i的度。

定義5 節(jié)點(diǎn)相似性。節(jié)點(diǎn)j對節(jié)點(diǎn)i的重要程度定義如下:

其中:c1和c2是取值在0～1的兩個常數(shù)，ρij是節(jié)點(diǎn)i和節(jié)點(diǎn)j的邊緣度數(shù)比。

定義6 社區(qū)相似性。節(jié)點(diǎn)i與社區(qū)l的相似性定義如下:

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

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

定義8 基于社區(qū)相似性的更新規(guī)則。假設(shè)集合T中保存了節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)中的最大值標(biāo)簽(社區(qū))和近似最大值標(biāo)簽，L(i)表示節(jié)點(diǎn)i的標(biāo)簽，基于社區(qū)相似性的更新規(guī)則如式(9)所示:

式(9)是在集合T中，讓節(jié)點(diǎn)i選擇使得S(i，l)最大的一類標(biāo)簽，如果有多類標(biāo)簽使得S(i，l)最大，就從中隨機(jī)選取。

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

表5 LFR基準(zhǔn)網(wǎng)絡(luò)的主要參數(shù)Tab．5 Parameters of LFR benchmark network

表6 LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集描述Tab．6 Description of LFR benchmark network datasets

歸一化互信息(Normal Mutual Information，NMI)［17］能夠量化算法對網(wǎng)絡(luò)進(jìn)行的劃分和網(wǎng)絡(luò)的真實(shí)劃分之間的關(guān)系，是一種在社區(qū)發(fā)現(xiàn)領(lǐng)域常用的度量標(biāo)準(zhǔn)。NMI的取值在0～1，其計算式(10)所示:

其中:A是網(wǎng)絡(luò)的真實(shí)劃分，B是算法對網(wǎng)絡(luò)所進(jìn)行的劃分，CA表示A種劃分的社區(qū)個數(shù)，CB表示B種劃分的社區(qū)個數(shù)，N表示一個矩陣，Nij表示A種劃分第i個社區(qū)中的節(jié)點(diǎn)出現(xiàn)在B種劃分第j個社區(qū)中的節(jié)點(diǎn)個數(shù)，Ni·表示矩陣N第i行的求和，N·j表示矩陣N第j列的求和。n表示整個網(wǎng)絡(luò)節(jié)點(diǎn)的個數(shù)。如果A種劃分和B種劃分是相同的，則NMI(A，B)的值為1。NMI的值越高，表示算法社區(qū)發(fā)現(xiàn)的準(zhǔn)確率越高。

將CS_LPA和LPA分別用在表1和表3的8種真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和4種LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行社區(qū)發(fā)現(xiàn)，對每一個網(wǎng)絡(luò)重復(fù)100次實(shí)驗(yàn)。在8種真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上與LPA對比平均模塊度，對比如表7所示:在所用的數(shù)據(jù)集上，CS_LPA的模塊度都比 LPA要高;其中，在 Email、CA-Hepth、dolphins和netscience網(wǎng)絡(luò)上，CS_LPA模塊度有明顯的提高。由于LFR基準(zhǔn)網(wǎng)絡(luò)已知真實(shí)的劃分結(jié)果，因此在LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上與LPA對比平均NMI值。NMI的對比如圖2所示。

圖2 LFR基準(zhǔn)網(wǎng)絡(luò)上CS_LPA和LPA的NMI對比Fig．2 NMI comparison of CS_LPA and LPA on LFR benchmark network

從圖2(a)可以看出，mu的值在0．1～0．45時，兩種算法都能較好地發(fā)現(xiàn)社區(qū)結(jié)構(gòu);mu的值在0．45～0．6時，LPA的NMI值迅速下降，表明社區(qū)發(fā)現(xiàn)的準(zhǔn)確率在下降，而CS_LPA的NMI的值遠(yuǎn)高于LPA;mu的值在0．65～0．8，LPA已無法進(jìn)行社區(qū)發(fā)現(xiàn)，而CS_LPA仍可進(jìn)行。圖2(b)產(chǎn)生了類似于圖2(a)的效果，mu的值在0．1～0．4時，兩種算法都能較好地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，而 mu的值在0．45～0．8時，CS_LPA的NMI值高于LPA。在圖2(c)和圖2(d)中，當(dāng) mu大于0．6時，CS_LPA的NMI明顯高于LPA。

綜上所述，相比LPA，CS_LPA提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確率，尤其對于社區(qū)結(jié)構(gòu)不清晰的網(wǎng)絡(luò)，算法的優(yōu)勢更加明顯。

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

3 FNCS_LPA算法

3．1 算法流程

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

FNCS_LPA:

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

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

輸出 社區(qū)劃分結(jié)果。

1) 為每個節(jié)點(diǎn)分配一個獨(dú)一無二的標(biāo)簽;

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

3) 從節(jié)點(diǎn)信息列表中隨機(jī)選取一個主動節(jié)點(diǎn)或干擾節(jié)點(diǎn)，記為i;

4) 將當(dāng)前節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽和近似最大值標(biāo)簽加入集合T當(dāng)中;

5) 初始化maxLabel集合為空;maxLabel記錄與當(dāng)前節(jié)點(diǎn)i相似性最高的一個或多個標(biāo)簽。

6) for each l∈T do

7) maxS←0;

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

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

10) 將l標(biāo)簽添加到maxLabel中;

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

12) maxS ← S(i，l);

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

14) 將l標(biāo)簽添加到maxLabel中;

15) end if

16)end for

17)當(dāng)前節(jié)點(diǎn)i從maxLabel集合中隨機(jī)選取標(biāo)簽;

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

/* 更新當(dāng)前節(jié)點(diǎn)i和i的鄰接節(jié)點(diǎn)的狀態(tài)*/

19) if node j is interference node then

20) 標(biāo)記j為干擾節(jié)點(diǎn);

21) else if node j is passive node then

22) 標(biāo)記j為被動節(jié)點(diǎn);

23) else

24) 標(biāo)記j為主動節(jié)點(diǎn);

25) end if

26)end for

27)如果節(jié)點(diǎn)信息列表仍含有主動節(jié)點(diǎn)，跳到第3)步;

28)將具有相同標(biāo)簽的節(jié)點(diǎn)劃分到一個社區(qū)當(dāng)中，算法結(jié)束

3．2 時間復(fù)雜度

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

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

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

4．1 執(zhí)行速度對比

將FNCS_LPA、Cen_LP、NIBLPA和NILPA分別應(yīng)用到真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中進(jìn)行社區(qū)發(fā)現(xiàn)。為了具有可比性，每一個算法的終止條件都是節(jié)點(diǎn)標(biāo)簽成為鄰接節(jié)點(diǎn)中的最大值標(biāo)簽，對每一個網(wǎng)絡(luò)重復(fù)100次實(shí)驗(yàn)求平均的迭代次數(shù)，得到的結(jié)果如圖3所示。

圖3 FNCS_LPA與三種改進(jìn)LPA的迭代次數(shù)對比Fig．3 Comparison of iterations between FNCS_LPA and other three improved LPA algorithms

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

4．2 模塊度對比

將4種算法應(yīng)用在8種真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行社區(qū)發(fā)現(xiàn)，并在最低模塊度、平均模塊度和最高模塊度方面進(jìn)行對比，模塊度的計算公式如式(1)所示。平均模塊度(average)是對每一個真實(shí)網(wǎng)絡(luò)作100次實(shí)驗(yàn)求取的平均值，最低模塊度(min)和最高模塊度(max)分別是對每一個真實(shí)網(wǎng)絡(luò)作100次實(shí)驗(yàn)后求取的最差結(jié)果和最優(yōu)結(jié)果。模塊度的對比如表8所示，其中加粗的數(shù)據(jù)表明4種算法中對應(yīng)每一個網(wǎng)絡(luò)的最好結(jié)果。

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

從表8中可以看出，F(xiàn)NCS_LPA在所有的數(shù)據(jù)集上的最低模塊度、平均模塊度和最高模塊度均完全一致。在karate網(wǎng)絡(luò)上，F(xiàn)NCS_LPA和NILPA都將網(wǎng)絡(luò)劃分為兩個社區(qū)，求得的結(jié)果與真實(shí)劃分完全相同;在dolphins和polbooks網(wǎng)絡(luò)上，F(xiàn)NCS_LPA在最低模塊度、平均模塊度和最高模塊度上，均接近于最優(yōu)解;盡管Email網(wǎng)絡(luò)沒有在最高模塊度方面取得最好的結(jié)果，但是從平均模塊度和最低模塊度方面，F(xiàn)NCS_LPA仍是最有優(yōu)勢的;而在netscience、CA-GrQc、CA-Hepth和PGP等網(wǎng)絡(luò)上，F(xiàn)NCS_LPA的模塊度明顯高于其他幾種算法。綜上所述，F(xiàn)NCS_LPA相比其他3種算法提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確率和穩(wěn)定性;尤其在較大規(guī)模的網(wǎng)絡(luò)算法，算法的優(yōu)勢更加明顯。

4．3 歸一化互信息對比

本次實(shí)驗(yàn)將4種算法應(yīng)用在表6中的LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行社區(qū)發(fā)現(xiàn)，并在歸一化互信息度量(NMI)方面進(jìn)行對比，NMI的計算公式如式(7)所示。對每一個網(wǎng)絡(luò)重復(fù)100次實(shí)驗(yàn)求取平均NMI值。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 LFR基準(zhǔn)網(wǎng)絡(luò)上FNCS_LPA與三種改進(jìn)LPA算法的NMI對比Fig．4 NMI comparison of FNCS_LPA and other three improved LPA algorithms on LFR benchmark network

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

5 結(jié)語

本文提出了基于節(jié)點(diǎn)中心性和社區(qū)相似性的快速標(biāo)簽傳播算法。首先，該算法計算每一個節(jié)點(diǎn)的中心度量值，依據(jù)節(jié)點(diǎn)中心性度量值升序?qū)⒐?jié)點(diǎn)加入節(jié)點(diǎn)信息列表，利用節(jié)點(diǎn)信息列表指導(dǎo)更新過程，通過記錄每一個節(jié)點(diǎn)的更新狀態(tài)，避免了許多不必要的更新，減少了迭代次數(shù)，從而提高了社區(qū)發(fā)現(xiàn)的穩(wěn)定性和執(zhí)行速度。為了驗(yàn)證基于節(jié)點(diǎn)中心性的快速更新過程的有效性，實(shí)驗(yàn)使用了8種真實(shí)網(wǎng)絡(luò)在迭代次數(shù)和平均模塊度方面與LPA進(jìn)行了對比。其次，算法引入社區(qū)相似性的更新規(guī)則，即當(dāng)前節(jié)點(diǎn)會加入與當(dāng)前節(jié)點(diǎn)社區(qū)相似性最高的社區(qū)，提高了社區(qū)發(fā)現(xiàn)的準(zhǔn)確率，為了驗(yàn)證基于社區(qū)相似性的更新規(guī)則的有效性，算法在平均模塊度、NMI方面與LPA進(jìn)行了對比。最后，將基于節(jié)點(diǎn)中心性的快速更新過程和基于社區(qū)相似性的更新規(guī)則結(jié)合形成本文提出的基于節(jié)點(diǎn)中心性和社區(qū)相似性的快速標(biāo)簽傳播算法，與目前3種改進(jìn)的LPA在迭代次數(shù)、模塊度和NMI三個方面進(jìn)行了對比，實(shí)驗(yàn)結(jié)果表明FNCS_LPA在提升算法執(zhí)行速度的基礎(chǔ)上，提高了算法的穩(wěn)定性和準(zhǔn)確率。