基于核心節(jié)點(diǎn)逐層擴(kuò)展的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法*

翟鎮(zhèn)新 於躍成 谷 雨 景道月

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展和社會(huì)網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，人與人之間的交流形式發(fā)生了巨大變化，人們獲取的信息量也呈爆炸式增長(zhǎng)。社會(huì)網(wǎng)絡(luò)具有信息大、無標(biāo)識(shí)、社區(qū)結(jié)構(gòu)等特性，其中社區(qū)結(jié)構(gòu)是社會(huì)網(wǎng)絡(luò)的基本性質(zhì)。所謂社區(qū)結(jié)構(gòu)是指一個(gè)網(wǎng)絡(luò)可以分為若干個(gè)社區(qū)，社區(qū)內(nèi)節(jié)點(diǎn)相似度較高且連接相對(duì)緊密，社區(qū)間節(jié)點(diǎn)相似度較低且相對(duì)稀疏。社區(qū)發(fā)現(xiàn)可用于社交平臺(tái)用戶群組的發(fā)現(xiàn)，以實(shí)現(xiàn)相關(guān)商業(yè)廣告的投放；通過社區(qū)發(fā)現(xiàn)并挖掘群組的最新討論話題，可以向用戶更好地推薦感興趣的話題。

為了能夠?qū)崿F(xiàn)社區(qū)的有效劃分，基于隨機(jī)游走的方法［1］、基于模塊度優(yōu)化的方法［2～3］以及基于圖分割的方法［4～5］被相繼提出。這些方法主要依據(jù)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行劃分，當(dāng)應(yīng)用于數(shù)據(jù)規(guī)模較大的社會(huì)網(wǎng)絡(luò)時(shí)，便會(huì)面臨迭代周期較長(zhǎng)，算法復(fù)雜度較高等一系列問題。

2007 年，KUMARA 等學(xué)者［6］首次在面對(duì)非常繁瑣的社會(huì)網(wǎng)絡(luò)時(shí)，嘗試將標(biāo)簽傳播模型（Label Propagation Algorithm，LPA）運(yùn)用其中做社區(qū)發(fā)現(xiàn)的研究。實(shí)驗(yàn)結(jié)果表明，使用LPA模型的社區(qū)發(fā)現(xiàn)時(shí)間效率等方面指標(biāo)都有了巨大的突破。該算法模型不需要提前知道真實(shí)的社區(qū)個(gè)數(shù)有多少，僅依賴于社會(huì)網(wǎng)絡(luò)的自身結(jié)構(gòu)。LPA 算法復(fù)雜度較低，被廣泛應(yīng)用于大規(guī)模社會(huì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。

然而，LPA 在每次的迭代過程中存在著隨機(jī)性，致使每次社區(qū)發(fā)現(xiàn)的結(jié)果都不一致。造成LPA算法穩(wěn)定性較差和隨機(jī)性較高的主要原因在于該算法沒有充分考慮節(jié)點(diǎn)自身的影響力，網(wǎng)絡(luò)中所有節(jié)點(diǎn)均被平等看待。為此，本文引入LeaderRank［7］算法來計(jì)算節(jié)點(diǎn)的影響力，在根據(jù)影響力值對(duì)節(jié)點(diǎn)進(jìn)行排序的基礎(chǔ)上，采取一定的節(jié)點(diǎn)選取策略，篩選出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)；接著，在初始化網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)，這些關(guān)鍵節(jié)點(diǎn)被賦予唯一的標(biāo)簽，并將這些節(jié)點(diǎn)視為初始傳播源；最后，采用逐層更新的方式更新節(jié)點(diǎn)標(biāo)簽。

2 相關(guān)工作

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

標(biāo)簽傳播算法（LPA）的基本思想：一個(gè)擁有n個(gè)鄰居節(jié)點(diǎn)x1,x2,…,xn的給定節(jié)點(diǎn)x，和該節(jié)點(diǎn)x相互連接的節(jié)點(diǎn)都有所屬于自身的唯一標(biāo)簽，那么該節(jié)點(diǎn)的標(biāo)簽信息將由和其相互連接的節(jié)點(diǎn)標(biāo)簽信息共同決定。標(biāo)簽傳播算法可簡(jiǎn)述為

1）對(duì)圖中節(jié)點(diǎn)標(biāo)簽初始化時(shí)，為每個(gè)節(jié)點(diǎn)賦予唯一的標(biāo)簽，用來標(biāo)識(shí)節(jié)點(diǎn)所在的社區(qū)。

2）對(duì)圖中所有的節(jié)點(diǎn)開始迭代更新，節(jié)點(diǎn)將會(huì)接受和其相連接的節(jié)點(diǎn)標(biāo)簽信息，選取和其相連接的節(jié)點(diǎn)標(biāo)簽中標(biāo)簽出現(xiàn)頻率最大的那個(gè)。當(dāng)多個(gè)標(biāo)簽數(shù)量相同時(shí)，將隨機(jī)選取其中一個(gè)標(biāo)簽作為更新節(jié)點(diǎn)的標(biāo)簽。經(jīng)過多次迭代，使得圖中所有的節(jié)點(diǎn)標(biāo)簽趨于穩(wěn)定，社區(qū)結(jié)構(gòu)也隨之顯現(xiàn)出來

3）根據(jù)每個(gè)節(jié)點(diǎn)的標(biāo)簽，將所有的節(jié)點(diǎn)進(jìn)行劃分，標(biāo)簽相同的節(jié)點(diǎn)將劃分為同一社區(qū)。

圖1 為標(biāo)簽傳播過程的一個(gè)簡(jiǎn)單案例。由圖可以明顯看出，標(biāo)簽為a 的節(jié)點(diǎn)在接受鄰居節(jié)點(diǎn)的標(biāo)簽信息后，由于標(biāo)簽c 的節(jié)點(diǎn)數(shù)量為2，根據(jù)上述原理，標(biāo)簽為a的節(jié)點(diǎn)將更新為標(biāo)簽c。

圖1 標(biāo)簽傳播過程

上述算法有兩種更新方式：同步更新和異步更新。采用同步更新將會(huì)在二分圖上產(chǎn)生循環(huán)震蕩的問題。如圖2 所示，假設(shè)p-1 時(shí)刻的狀態(tài)如圖2（a）所示，p 時(shí)刻的狀態(tài)如圖2（b）所示，那么如此循環(huán)下去將無法形成真正的社區(qū)。采用異步更新時(shí)，那么該節(jié)點(diǎn)的標(biāo)簽信息將會(huì)由和該節(jié)點(diǎn)相連接的節(jié)點(diǎn)標(biāo)簽信息中部分p時(shí)刻的信息和部分p-1時(shí)刻的信息所共同決定。

圖2 標(biāo)簽震蕩

LPA 模型在時(shí)間效率等指標(biāo)方面有著絕對(duì)的優(yōu)勢(shì)，現(xiàn)階段已經(jīng)在百萬級(jí)的復(fù)雜網(wǎng)絡(luò)中有著較高的使用頻率，但是該算法模型會(huì)存在一些無意義的節(jié)點(diǎn)標(biāo)簽更新，往往會(huì)導(dǎo)致“無意義”的小型社區(qū)或者大型社區(qū)的形成，這些都是沒有研究?jī)r(jià)值的成果。

趙卓翔等［8］綜合考慮了在標(biāo)簽的傳播過程中邊的權(quán)重、每個(gè)標(biāo)簽的個(gè)數(shù)以及需更新節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度，提出了平均權(quán)重的概念。Zhao 等學(xué)者［9］將LPA算法模型與物理學(xué)中熵相結(jié)合，形成一種新的算法模型，該模型主要是計(jì)算每個(gè)節(jié)點(diǎn)所擁有標(biāo)簽的熵值，按照熵值的大小來決定節(jié)點(diǎn)更新順序，從而消除原始算法中的節(jié)點(diǎn)更新隨意性。康旭彬等［10］采用Jaccard 系數(shù)計(jì)算節(jié)點(diǎn)之間的相似度，并以此決定節(jié)點(diǎn)標(biāo)簽的更新選擇。張?chǎng)蔚龋?1］在通過尋找不重疊三角形的方式來優(yōu)化標(biāo)簽初始化，并結(jié)合鄰居節(jié)點(diǎn)的影響力來選擇標(biāo)簽，提高了社區(qū)發(fā)現(xiàn)的穩(wěn)定性。馬秀等［12］利用k-shell 方法計(jì)算節(jié)點(diǎn)的影響力，但k-shell 方法只是一種粗粒度的劃分，對(duì)節(jié)點(diǎn)影響力的計(jì)算不夠精確。石夢(mèng)雨等學(xué)者在原始標(biāo)簽傳播算法的基礎(chǔ)上，融合進(jìn)了LeaderRank算法模型，提出了新的標(biāo)簽傳播算法（LRLPA）。Zhang 等［16］將節(jié)點(diǎn)重要性融入到原始算法中，計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)重要性，并以此來替代節(jié)點(diǎn)標(biāo)簽的重要程度，形成了一種新的標(biāo)簽傳播算法（LPA_NI）。龔宇等［17］將LeaderRank算法與典型的COPRA算法相結(jié)合，對(duì)發(fā)現(xiàn)更加復(fù)雜的重疊社區(qū)的精準(zhǔn)度有了較大的提升。

盡管以上方法在一定程度上提高了LPA 檢測(cè)社區(qū)的精確度，但這些方法在進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)初始化時(shí)，為所有節(jié)點(diǎn)都賦予了唯一標(biāo)簽。這也意味著，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)均被平等對(duì)待，弱化了核心節(jié)點(diǎn)的影響力，變相地抬高了邊緣節(jié)點(diǎn)的影響力，忽略了網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的差異。

2.2 LeaderRank算法

目前用于衡量節(jié)點(diǎn)影響力的經(jīng)典方法有很多，但大多數(shù)方法考慮的因素過于單一。如度中心性方法，僅僅從節(jié)點(diǎn)的度數(shù)進(jìn)行考慮，忽略了節(jié)點(diǎn)自身影響力、鄰域節(jié)點(diǎn)影響力等諸多因素。以PageRank 為代表的一類算法中還含有參數(shù)，在面對(duì)不同網(wǎng)絡(luò)結(jié)構(gòu)時(shí)，還需進(jìn)行參數(shù)測(cè)試的方式來選取最優(yōu)參數(shù)。

LeaderRank 算法由Zhang 等提出，是一種對(duì)社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行排序的方法。該算法綜合考慮了節(jié)點(diǎn)度數(shù)、鄰居節(jié)點(diǎn)影響力等因素，無需任何參數(shù)，能夠自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)，符合網(wǎng)絡(luò)中的傳播特性，因此被廣泛用于復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的度量。

LeaderRank 算法被用于計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力，在整個(gè)網(wǎng)絡(luò)圖G=（V，E）中加入了一個(gè)背景節(jié)點(diǎn)vg，該節(jié)點(diǎn)與原圖中的所有節(jié)點(diǎn)均相互鏈接，使得整個(gè)網(wǎng)絡(luò)圖成為強(qiáng)連通圖。

首先對(duì)背景節(jié)點(diǎn)vg分配0 個(gè)資源單位的S 值（即LeaderRank值），除背景節(jié)點(diǎn)vg外的節(jié)點(diǎn)均分配1 個(gè)資源單位的S 值，使用式（1）計(jì)算每個(gè)節(jié)點(diǎn)的S值，直至達(dá)到穩(wěn)態(tài)。

式（2）用于將背景節(jié)點(diǎn)vg的S 值平均分給每個(gè)節(jié)點(diǎn)。其中，tc表示穩(wěn)定時(shí)刻，Si(tc)表示節(jié)點(diǎn)vi在穩(wěn)定時(shí)刻的S 值，Sg(tc)表示背景節(jié)點(diǎn)vg在穩(wěn)定時(shí)刻的S值，N為網(wǎng)絡(luò)G中的節(jié)點(diǎn)總數(shù)。

3 基于核心節(jié)點(diǎn)逐層擴(kuò)展的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法

本文在LeaderRank算法的基礎(chǔ)上，對(duì)標(biāo)簽傳播算法的節(jié)點(diǎn)初始化進(jìn)行優(yōu)化并給出新的標(biāo)簽傳播策略，提出了一種新的標(biāo)簽傳播算法CNE_LPA。在對(duì)節(jié)點(diǎn)初始化時(shí)選取核心節(jié)點(diǎn)，并為核心節(jié)點(diǎn)提供唯一標(biāo)簽，以減少后續(xù)標(biāo)簽傳播過程中無意義的判斷，提高標(biāo)簽傳播過程的整體效率。在標(biāo)簽傳播過程中，本文采用逐層更新的方式更新節(jié)點(diǎn)標(biāo)簽。

3.1 節(jié)點(diǎn)初始化

由于CNE_LPA 算法僅選取部分節(jié)點(diǎn)作為初始傳播源，為此，從網(wǎng)絡(luò)中篩選出的核心節(jié)點(diǎn)應(yīng)盡可能地輻射到所有的節(jié)點(diǎn)，并盡可能散落于每個(gè)社區(qū)之中。為實(shí)現(xiàn)上述目的，CNE_LPA 算法首先計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)S 值的平均值，將S 值大于平均值的節(jié)點(diǎn)優(yōu)先加入核心節(jié)點(diǎn)集中，并確保加入核心節(jié)點(diǎn)集的節(jié)點(diǎn)不是核心節(jié)點(diǎn)集中已存在節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。那么，對(duì)于對(duì)于網(wǎng)絡(luò)G=（V，E），其中V 和E分別為網(wǎng)絡(luò)G 的頂點(diǎn)集和邊集，核心節(jié)點(diǎn)K 的選取策略可以概述如下。

1）對(duì)于?vi∈V，以S（vi）和avg分別表示節(jié)點(diǎn)vi的S 值和網(wǎng)絡(luò)G 中所有節(jié)點(diǎn)S 值的平均值，若S（vi）＞avg，則節(jié)點(diǎn)vi將被視為核心節(jié)點(diǎn)集K的候選節(jié)點(diǎn)；

2）對(duì)于?vj∈K，以Neighbor（vj）表示節(jié)點(diǎn)vj的鄰居節(jié)點(diǎn)，若候選核心節(jié)點(diǎn)vi∈Neighbor（vj），那么可以將vi加入核心節(jié)點(diǎn)集K。

算法1 核心節(jié)點(diǎn)集選取算法

輸入：網(wǎng)絡(luò)G=（V，E）

輸出：核心節(jié)點(diǎn)集K

算法：

1）對(duì)于?vi∈V，計(jì)算所有節(jié)點(diǎn)S 值的和Snum，即Snum+= S（vi）；

2）計(jì)算網(wǎng)絡(luò)G 中節(jié)點(diǎn)S 值的均值avg=Snum/N，其中N 為網(wǎng)絡(luò)G中的節(jié)點(diǎn)總數(shù)；

3）初始化核心節(jié)點(diǎn)集K=?，并將節(jié)點(diǎn)集V 拷貝至集合V′，若S（vi）＜avg，將vi從V′中刪除，然后將V′中節(jié)點(diǎn)按照其S值進(jìn)行降序排列；

4）若V′≠?，從節(jié)點(diǎn)集V′中任意選取節(jié)點(diǎn)vi；否則，跳轉(zhuǎn)至5）；

（1）將節(jié)點(diǎn)集K拷貝至集合K′，跳轉(zhuǎn)至（2），測(cè)試節(jié)點(diǎn)vi是否為K中節(jié)點(diǎn)的鄰居；否則跳轉(zhuǎn)至（5）；

（2）從集合K′中任取一個(gè)節(jié)點(diǎn)vj，如果vi?Neighbor（vj）成立，跳轉(zhuǎn)至（3）；否則跳轉(zhuǎn)至（5）；

（3）將節(jié)點(diǎn)vj移出集合K′ ，若K′≠?，跳轉(zhuǎn)至（2）；若K′=?，跳轉(zhuǎn)至（4）；

（4）將節(jié)點(diǎn)vi移入集合K，將節(jié)點(diǎn)vi從集合V′中刪除，跳轉(zhuǎn)至4）；

（5）清空集合K′，將節(jié)點(diǎn)vi從集合V′中刪除，跳轉(zhuǎn)至4）；

5）輸出核心節(jié)點(diǎn)集K。

3.2 標(biāo)簽傳播策略

在標(biāo)簽傳播過程中，如果待更新節(jié)點(diǎn)的鄰域中擁有最大節(jié)點(diǎn)數(shù)量的標(biāo)簽不止一個(gè)時(shí)，傳統(tǒng)LPA算法便會(huì)隨機(jī)選取其中的一個(gè)標(biāo)簽。這種隨機(jī)選取標(biāo)簽的方式往往導(dǎo)致相同數(shù)據(jù)集上多次檢測(cè)到的社區(qū)結(jié)果卻不一致。

為了降低LPA 在標(biāo)簽傳播過程中的隨機(jī)性，CNE_LPA 算法選取待更新節(jié)點(diǎn)vi鄰域Neighbor（vi）中影響力最大的節(jié)點(diǎn)vk的標(biāo)簽label（vk）作為節(jié)點(diǎn)vi的待更新標(biāo)簽labelnew（vi）。也就是說，如果?vk∈Neighbor（vi），并且對(duì)于?vj∈Neighbor（vi），滿足S（vk）≥S（vj），那么labelnew（vi）=label（vk）。直覺上，社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)受到與其相鄰的所有節(jié)點(diǎn)的影響，而這些鄰居節(jié)點(diǎn)又可能隸屬于不同的社區(qū)。這意味著，一個(gè)節(jié)點(diǎn)的影響力實(shí)際上是其在多個(gè)社區(qū)上的影響力的綜合表現(xiàn)。為簡(jiǎn)化起見，如式（3）所示，本文以節(jié)點(diǎn)影響力與該節(jié)點(diǎn)度的比值來表示該節(jié)點(diǎn)在特定社區(qū)上的影響力。另外，在節(jié)點(diǎn)vi的領(lǐng)域節(jié)點(diǎn)中可能存在多個(gè)節(jié)點(diǎn)與影響力最大的節(jié)點(diǎn)vk具有相同標(biāo)簽的情形，為此，CNE_LPA算法以這些具有相同標(biāo)簽的節(jié)點(diǎn)局部影響力之和來更新該節(jié)點(diǎn)的影響力。因此，當(dāng)節(jié)點(diǎn)vi的標(biāo)簽以節(jié)點(diǎn)vk的標(biāo)簽更新后，節(jié)點(diǎn)vi的影響力Snew（vi）將按照式（3）所示的方式進(jìn)行更新：

其中，Neighbor（vi）表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合，S（vj）表示節(jié)點(diǎn)vj的影響力，d（vj）表示節(jié)點(diǎn)的度。

由于CNE_LPA 算法對(duì)節(jié)點(diǎn)標(biāo)簽采用逐層更新的方式，為此，本文引入多級(jí)鄰居節(jié)點(diǎn)這一概念。按照網(wǎng)絡(luò)層次結(jié)構(gòu)，一級(jí)鄰居節(jié)點(diǎn)為核心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，二級(jí)鄰居節(jié)點(diǎn)為一級(jí)鄰居節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，以此類推。當(dāng)進(jìn)行標(biāo)簽傳播時(shí)，以核心節(jié)點(diǎn)集中的核心節(jié)點(diǎn)為初始傳播源，首先更新一級(jí)鄰居節(jié)點(diǎn)標(biāo)簽；然后再以一級(jí)鄰居節(jié)點(diǎn)作為傳播源來更新二級(jí)鄰居節(jié)點(diǎn)；以此類推，直到所有節(jié)點(diǎn)的標(biāo)簽更新完畢。

當(dāng)節(jié)點(diǎn)標(biāo)簽首次更新時(shí)，將采用上述方式更新節(jié)點(diǎn)標(biāo)簽，并根據(jù)式（3）更新節(jié)點(diǎn)的影響力值。如果在更新過程中節(jié)點(diǎn)vi已有標(biāo)簽，那么在以影響力值最大的標(biāo)簽label（vk）更新label（vi）之前，需要先計(jì)算若以待更新標(biāo)簽label（vk）更新label（vi）后Snew（vi）的值。如果Snew（vi）＞Sold（vi）成立，以label（vk）更新label（vi），即執(zhí)行l(wèi)abelnew（vi）=label（vk）；否則label（vi）保持不變。當(dāng)這個(gè)網(wǎng)絡(luò)G 中的節(jié)點(diǎn)標(biāo)簽更新的變化率小于設(shè)定的閾值時(shí)，算法停止。

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

輸入：網(wǎng)絡(luò)G=（V，E），核心節(jié)點(diǎn)集K，節(jié)點(diǎn)S值

輸出：網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)簽集L

算法：

1）初始化核心節(jié)點(diǎn)集K 中每一節(jié)點(diǎn)的標(biāo)簽，并以Null值初始化其余節(jié)點(diǎn)標(biāo)簽；

2）初始化集合K″=K，V′=V；

3）若K′≠?，繼續(xù)執(zhí)行1）；否則跳轉(zhuǎn)至4）

（1）若K′≠?，從集合K′中任取一個(gè)節(jié)點(diǎn)vj，否則跳轉(zhuǎn)至（4）

//更新K中一個(gè)核心節(jié)點(diǎn)vj的所有近鄰的標(biāo)簽

（2）從集合V′中搜索節(jié)點(diǎn)vj的鄰居節(jié)點(diǎn)集合N=｛vi|vi∈Neighbor（vj）且vi∈V′｝；

①如果N≠?，任取其中一個(gè)節(jié)點(diǎn)vi；否則，跳轉(zhuǎn)至（3）；

②在vi的鄰居中搜索S 值最大且標(biāo)簽值不是Null 的節(jié)點(diǎn)vk，即S（vk）=max｛S（vi）|vi∈N且S（vi）≠Null｝；

③根據(jù)式（3）計(jì)算Snew(vi)，如果Snew(vi)＞Sold(vi)，以label（vk）更新label(vi)，否則保持label(vi)不變；

④將節(jié)點(diǎn)vi并入集合K″，跳轉(zhuǎn)至①；

（3）從V′中刪除節(jié)點(diǎn)vj；

（4）K′=K″，K″=?，返回3）

4）結(jié)束標(biāo)簽更新，算法終止。

3.3 CNE_LPA算法描述

CNE_LPA 算法從原始算法的節(jié)點(diǎn)初始化過程以及標(biāo)簽傳播過程兩個(gè)方向進(jìn)行了優(yōu)化。CNE_LPA算法的總體步驟如下：

輸入：網(wǎng)絡(luò)G=（V，E）

輸出：社區(qū)C

算法：

1）初始化迭代次數(shù)t=1

2）調(diào)用算法1，生成重要節(jié)點(diǎn)集K；

3）調(diào)用算法2，完成節(jié)點(diǎn)標(biāo)簽的一輪更新；

4）t=t+1，如果迭代次數(shù)t 小于閾值，返回到步驟2）；否則結(jié)束標(biāo)簽更新；

5）輸出社區(qū)劃分C。

3.4 CNE_LPA算法時(shí)間復(fù)雜度

在復(fù)雜網(wǎng)絡(luò)G=（V，E）中，有x 個(gè)節(jié)點(diǎn)和y 條邊，核心節(jié)點(diǎn)的候選節(jié)點(diǎn)為t，核心節(jié)點(diǎn)的個(gè)數(shù)為k。節(jié)點(diǎn)影響力的計(jì)算時(shí)間復(fù)雜度為O(x2)，核心節(jié)點(diǎn)的篩選時(shí)間復(fù)雜度為O(x+t2)，初始化核心節(jié)點(diǎn)集中的核心節(jié)點(diǎn)時(shí)間復(fù)雜度為O(k)，節(jié)點(diǎn)標(biāo)簽的更新迭代時(shí)間復(fù)雜度為O(x+xyk2)，將所有標(biāo)簽相同的節(jié)點(diǎn)劃分為同一個(gè)社區(qū)的時(shí)間復(fù)雜度為O(x)。那么CNE_LPA 算法的時(shí)間復(fù)雜度為O(x2+3x+t2+xyk2)。

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

實(shí)驗(yàn)數(shù)據(jù)主要采用LFR 人工數(shù)據(jù)集和五種真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集（Zachary，F(xiàn)ootball，Dolphin，Jazz，Netscience），在這些數(shù)據(jù)集的基礎(chǔ)上，將使用將使用其他社區(qū)檢測(cè)算法（LPA，LRLPA）來評(píng)估本文提出的CNE_LPA算法的性能。

4.1 實(shí)驗(yàn)數(shù)據(jù)

1）LFR人工數(shù)據(jù)集

LFR 準(zhǔn)基網(wǎng)絡(luò)數(shù)據(jù)集［13］是如今被廣泛用于評(píng)測(cè)社區(qū)發(fā)現(xiàn)算法優(yōu)劣性的人工數(shù)據(jù)集。LFR 中的信息如表1所示。實(shí)驗(yàn)數(shù)據(jù)集如表2所示。

表1 LFR數(shù)據(jù)集的信息

表2 4組LFR網(wǎng)絡(luò)的參數(shù)

2）真實(shí)數(shù)據(jù)集

真實(shí)數(shù)據(jù)集如表3所示。

表3 5組真實(shí)數(shù)據(jù)集

4.2 社區(qū)劃分評(píng)價(jià)標(biāo)準(zhǔn)

1）模塊度［14］

復(fù)雜網(wǎng)絡(luò)劃分社區(qū)質(zhì)量的評(píng)判指標(biāo)如式（6）所示：

其中，m代表社區(qū)中邊的數(shù)量，kv與kw分別表示節(jié)點(diǎn)v 和w 的度，A 為鄰接矩陣。若節(jié)點(diǎn)v 和節(jié)點(diǎn)w 之間沒有連接關(guān)系，那么Avw=0，反之，Avw=1。δ(cv,cw)表示節(jié)點(diǎn)v和節(jié)點(diǎn)w是否在同一個(gè)社區(qū)內(nèi)，若在同一個(gè)社區(qū)內(nèi)，δ(cv,cw)=1，否則δ(cv,cw)=0。

2）NMI［15］標(biāo)準(zhǔn)

標(biāo)準(zhǔn)化互信息（NMI）用以衡量一個(gè)方法下社區(qū)劃分結(jié)果與標(biāo)準(zhǔn)劃分的社區(qū)相似程度，其公式如下：

其中，CA為標(biāo)準(zhǔn)社區(qū)劃分的結(jié)果，CB為算法所檢測(cè)到的社區(qū)結(jié)果，N 代表著節(jié)點(diǎn)數(shù)，Ci是矩陣C 的第i 行的總和，Cj是矩陣C 的第j 列的總和。Cij是指實(shí)際的社區(qū)為i但出現(xiàn)在發(fā)現(xiàn)社區(qū)j中的節(jié)點(diǎn)數(shù)。

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

4.3.1 LFR人工數(shù)據(jù)集分析

在這些實(shí)驗(yàn)中，由于傳統(tǒng)的LPA算法有著較高的隨機(jī)性，將LPA 算法在B1、B2、B3、B4 這四組人工數(shù)據(jù)集上均運(yùn)行10次。測(cè)試效果如圖3所示，為了能夠體現(xiàn)LPA算法的不穩(wěn)定，將在四張圖中直接用誤差線進(jìn)行描述。

圖3 三個(gè)算法實(shí)驗(yàn)結(jié)果折線圖

從圖中可以明顯看出，隨著社區(qū)結(jié)構(gòu)越來越復(fù)雜，LPA 算法的波動(dòng)性也就越來越大，但CNE_LPA和LRLPA 依然能夠穩(wěn)定地檢測(cè)社區(qū)。總體來說，CNE_LPA 算法在量化節(jié)點(diǎn)標(biāo)簽的重要程度時(shí)，主要考慮了與其相連接的節(jié)點(diǎn)的局部重要性，從而導(dǎo)致在更新時(shí)，在精準(zhǔn)度上有著較大的提高。從穩(wěn)定性以及社區(qū)檢測(cè)質(zhì)量?jī)煞矫婢C合考慮，CNE_LPA算法相較于其他兩種算法能夠更加穩(wěn)定精確地實(shí)現(xiàn)社區(qū)檢測(cè)。

4.3.2 真實(shí)數(shù)據(jù)集分析

在本節(jié)中，使用模塊化度量將CNE_LPA 算法的性能與之前所提的其他兩種算法進(jìn)行了比較，其中由于LPA算法的不穩(wěn)定性，因此以LPA算法運(yùn)行30次的平均值來做對(duì)比。為了評(píng)估CNE_LPA算法的準(zhǔn)確性，本文將在兩個(gè)真實(shí)世界采集的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)集進(jìn)行多次試驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析。

1）Karate網(wǎng)絡(luò)分析

真實(shí)的Karate 網(wǎng)絡(luò)有兩個(gè)預(yù)定義的社區(qū)，CNE_LPA算法檢測(cè)到的結(jié)果如圖4所示，不同社區(qū)之間用不同的顏色表示。從圖中可以看出，CNE_LPA 算法不但可以準(zhǔn)確地檢測(cè)出兩個(gè)社區(qū)，而且在準(zhǔn)確劃分社區(qū)的基礎(chǔ)上可以發(fā)現(xiàn)兩個(gè)社區(qū)分別以節(jié)點(diǎn)1 和節(jié)點(diǎn)34 為中心，由此說明CNE_LPA算法能夠發(fā)現(xiàn)網(wǎng)絡(luò)中潛在的社區(qū)結(jié)構(gòu)。

為了比較LPA 和CNE_LPA 算法的穩(wěn)定性，本文將CNE_LPA 算法和原始算法在這兩個(gè)真實(shí)數(shù)據(jù)集上分別運(yùn)行30次，算法運(yùn)行結(jié)果的模塊度如圖5所示。從圖中可以明顯看出，CNE_LPA 算法有著較高的穩(wěn)定性，LPA算法波動(dòng)性較大。

圖5 LPA、CNE_LPA算法在Karate上的Q值變化

2）Dolphin網(wǎng)絡(luò)

Dolphin 網(wǎng)絡(luò)有兩個(gè)預(yù)定義的社區(qū)。本文在Dolphin 這個(gè)數(shù)據(jù)集上測(cè)試CNE_LPA 算法并檢測(cè)到如圖6 所示的三個(gè)社區(qū)，不同社區(qū)之間用不同的顏色加以區(qū)分。

圖6 CNE_LPA算法實(shí)現(xiàn)的社區(qū)劃分結(jié)果

從圖7 可以看出，LPA 算法因其自身的隨機(jī)性，產(chǎn)生較大的波動(dòng)性，并不能有效地檢測(cè)社區(qū)。CNE_LPA算法則能夠穩(wěn)定有效地檢測(cè)出社區(qū)。

圖7 LPA、CNE_LPA算法計(jì)算出的模塊度變化

在表4 中可以看出，從模塊化值以及社區(qū)發(fā)現(xiàn)數(shù)量上綜合考慮，LPA 算法因?yàn)槠涓唠S機(jī)性的影響，其社區(qū)檢測(cè)結(jié)果有著較大的波動(dòng)性。CNE_LPA 算法相對(duì)于其他兩種算法，則有著較高的模塊度，能夠穩(wěn)定有效地檢測(cè)出社區(qū)。

表4 五種真實(shí)數(shù)據(jù)集在不同算法上運(yùn)行的社區(qū)結(jié)果

5 結(jié)語

本文針對(duì)標(biāo)簽傳播算法的節(jié)點(diǎn)初始化進(jìn)行改進(jìn)以及給出新的標(biāo)簽傳播方法，引入LeaderRank算法衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力，在此基礎(chǔ)上選出核心節(jié)點(diǎn)作為初始標(biāo)簽傳播源，減少了傳播過程中的計(jì)算復(fù)雜度。算法采用逐層更新的方式進(jìn)行標(biāo)簽更新，并且在傳播更新過程中考慮到與更新節(jié)點(diǎn)相連接的節(jié)點(diǎn)標(biāo)簽重要性，消除了算法更新時(shí)極強(qiáng)的隨意性。多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明，相較于其他算法，CNE_LPA 算法能夠更加穩(wěn)定有效地實(shí)現(xiàn)社區(qū)的有效檢測(cè)。