李衛(wèi)疆+謝志勇+余正濤

摘 要：互聯(lián)網(wǎng)技術(shù)的發(fā)展使諸如微博等社會(huì)網(wǎng)絡(luò)的規(guī)模迅速增長(zhǎng)，對(duì)這些網(wǎng)絡(luò)進(jìn)行挖掘分析，揭示網(wǎng)絡(luò)特性對(duì)研究人們之間的聯(lián)系具有重要意義。因此，發(fā)現(xiàn)高質(zhì)量的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)是當(dāng)前社會(huì)網(wǎng)絡(luò)分析研究中的重要方向。傳統(tǒng)的關(guān)系圈挖掘算法復(fù)雜度高，在大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)中性能下降。相比于傳統(tǒng)社區(qū)發(fā)現(xiàn)算法，標(biāo)簽傳播算法（LPA）具有時(shí)間復(fù)雜度上的巨大優(yōu)勢(shì)，而且其改進(jìn)的SLPA還具有挖掘重疊社區(qū)的能力，但是標(biāo)簽傳播算法內(nèi)在的隨機(jī)策略使得算法穩(wěn)定性不高。針對(duì)標(biāo)簽傳播算法的缺點(diǎn)，提出一種基于節(jié)點(diǎn)相似度的標(biāo)簽傳播算法（NS-SLPA），根據(jù)節(jié)點(diǎn)相似度進(jìn)行節(jié)點(diǎn)標(biāo)簽的初始化過(guò)程，以降低傳播過(guò)程中的隨機(jī)選擇性。實(shí)驗(yàn)結(jié)果證明，NS-SLPA相比于SLPA，具有更高的穩(wěn)定性和有效性。

關(guān)鍵詞：社區(qū)發(fā)現(xiàn)；標(biāo)簽傳播；社區(qū)重疊；節(jié)點(diǎn)相似

DOIDOI：10.11907/rjdk.172310

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）002-0063-05

0 引言

近年來(lái)，隨著信息技術(shù)的高速發(fā)展，社會(huì)網(wǎng)絡(luò)諸如微博、論壇等社會(huì)媒體迅速發(fā)展，成為人們交流感情、分享經(jīng)驗(yàn)、傳達(dá)信息的重要平臺(tái)。

社會(huì)網(wǎng)絡(luò)由社會(huì)活動(dòng)中的個(gè)體及個(gè)體之間的關(guān)系所組成，社會(huì)網(wǎng)絡(luò)通常被抽象成一個(gè)圖G=（V，E）。其中，V表示頂點(diǎn)，代表社會(huì)網(wǎng)絡(luò)中的個(gè)體；E表示頂點(diǎn)所在的邊，表示個(gè)體之間的關(guān)系。而個(gè)體之間又組成各種大小不一的社區(qū)，社區(qū)結(jié)構(gòu)一直是社區(qū)研究的熱點(diǎn)問(wèn)題之一。社區(qū)網(wǎng)絡(luò)的社區(qū)概括而言是指社會(huì)網(wǎng)絡(luò)中一組相似頂點(diǎn)構(gòu)成的相互之間聯(lián)系緊密的群體，而群體之間的聯(lián)系相對(duì)較為稀疏[1]。例如某個(gè)人的朋友圈里有親人、同學(xué)、朋友等小群體，親人之間聯(lián)系緊密，而親人與同學(xué)之間聯(lián)系甚少，而這是關(guān)系圈中普遍存在的現(xiàn)象。

對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)研究具有重要意義，如在人際關(guān)系圈中可以發(fā)現(xiàn)具有不同背景的社會(huì)團(tuán)體，以方便進(jìn)行不同的宣傳策略；在社交媒體中，不同社區(qū)代表不同興趣愛(ài)好的團(tuán)體，可以為他們推薦好友，以更好地進(jìn)行交流；在購(gòu)物網(wǎng)絡(luò)中，不同社區(qū)代表了具有不同購(gòu)買力的人群，可以為他們推薦更適合的商品；在商品網(wǎng)絡(luò)中，可以進(jìn)行商品歸類，對(duì)商品的價(jià)格、銷售進(jìn)行指導(dǎo)等。正是由于社區(qū)結(jié)構(gòu)研究的重要意義，人們?cè)谏鐓^(qū)網(wǎng)絡(luò)的定義、發(fā)現(xiàn)與識(shí)別等方面作了大量研究，并提出了很多關(guān)于社區(qū)發(fā)現(xiàn)的算法。社區(qū)發(fā)現(xiàn)算法的出現(xiàn)為網(wǎng)絡(luò)劃分提供了很好的手段。以前很多社區(qū)發(fā)現(xiàn)算法都集中于研究如何對(duì)社區(qū)進(jìn)行結(jié)構(gòu)方面的劃分，因此具有很大的局限性。因?yàn)樯鐓^(qū)網(wǎng)絡(luò)不僅具有結(jié)構(gòu)特性，還包括傳播特性和節(jié)點(diǎn)間聯(lián)系的緊密程度，而且這些算法未考慮到在大型網(wǎng)絡(luò)上的應(yīng)用要求，算法復(fù)雜度過(guò)高。近年來(lái)，研究人員主要考慮如何保證社區(qū)發(fā)現(xiàn)算法的效率和社區(qū)劃分的準(zhǔn)確性，并針對(duì)這些問(wèn)題提出了很多經(jīng)典算法，標(biāo)簽傳播算法即是其中一種。

1 相關(guān)工作

下面通過(guò)介紹社區(qū)發(fā)現(xiàn)相關(guān)算法，引出本文的問(wèn)題。

1.1 社區(qū)發(fā)現(xiàn)相關(guān)算法

Girvan和Newman[2]提出了GN算法，首先求解每條邊的介數(shù)，然后將介數(shù)最大的邊刪去，再重新求解每條邊新的介數(shù)，依此循環(huán)。但是求解介數(shù)時(shí)間復(fù)雜度高，在大圖上并不實(shí)用；Pons和Latapy[3]提出一種基于隨機(jī)游走策略的社區(qū)發(fā)現(xiàn)算法，該算法的基本思想是：首先用頂點(diǎn)相似性度量頂點(diǎn)間的距離，初始階段每個(gè)節(jié)點(diǎn)都屬于一個(gè)社區(qū)，然后根據(jù)某種策略進(jìn)行游走，使頂點(diǎn)劃分到其平方距離平均值最小的社區(qū)，而且每進(jìn)行一步，都重新更新社區(qū)間的距離。但是該算法穩(wěn)定性和效率不高；Radicchi等[4]提出另一種分裂的社區(qū)發(fā)現(xiàn)算法，該算法屬于層次分裂算法，基本思路是將那些需要進(jìn)行分離的樹(shù)圖進(jìn)行迭代，找出符合定義的節(jié)點(diǎn)。該算法引入了一種稱為邊聚集系數(shù)的度量，邊聚集系數(shù)定義為邊所在的三角形個(gè)數(shù)與所有三角形的比值，并以此作為邊移除的準(zhǔn)則，但該方法時(shí)間復(fù)雜度過(guò)高；2007年Raghavan等[5]首先提出基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法（LPA），并在數(shù)據(jù)集上進(jìn)行測(cè)試，結(jié)果顯示LPA具有良好的社區(qū)結(jié)構(gòu)測(cè)試效果。此后，LPA被不斷改進(jìn)。

1.2 基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法

算法基本步驟如下：

（1）節(jié)點(diǎn)標(biāo)簽初始化。在初始化階段給每一個(gè)節(jié)點(diǎn)賦予一個(gè)節(jié)點(diǎn)標(biāo)簽。

（2）節(jié)點(diǎn)標(biāo)簽更新。對(duì)每個(gè)節(jié)點(diǎn)x，其鄰居節(jié)點(diǎn)標(biāo)簽集合為N（y）={y1，y2，…，yk}，若N（y）中只有一個(gè)標(biāo)簽元素?fù)碛凶畲笾丿B數(shù)，節(jié)點(diǎn)x則以此元素作為新標(biāo)簽；如果多個(gè)標(biāo)簽元素?fù)碛凶畲笾丿B數(shù)，x隨機(jī)選擇一個(gè)最大的重疊元素作為新標(biāo)簽。重復(fù)以上操作，直到達(dá)到最大迭代次數(shù)T。

（3）社區(qū)劃分。具有相同標(biāo)簽的節(jié)點(diǎn)屬于同一社區(qū)。標(biāo)簽傳播算法LPA時(shí)間復(fù)雜度低、算法簡(jiǎn)單、易于實(shí)現(xiàn)，且實(shí)用性強(qiáng)、分類效果好，因此迅速成為社區(qū)研究的熱點(diǎn)，并得到了廣泛應(yīng)用，在網(wǎng)絡(luò)結(jié)構(gòu)分析和信息檢索等方面取得了很多成果。但是標(biāo)簽傳播算法存在自身的缺點(diǎn)，其標(biāo)簽在初始化和傳播階段都采用了一種隨機(jī)選擇策略，因此會(huì)產(chǎn)生很大的隨機(jī)性，使劃分結(jié)果不穩(wěn)定。由于LPA算法存在的這些缺點(diǎn)，研究人員對(duì)該算法進(jìn)行了很多改進(jìn)，以期能高效地解決隨機(jī)性問(wèn)題，使其更加穩(wěn)定、準(zhǔn)確。

Barber等[6]在2009年提出了一種模塊化標(biāo)簽傳播算法（LPAm），該算法在RAK算法基礎(chǔ)上引入了模塊度最大化尋優(yōu)目標(biāo)函數(shù)，成功解決了LPA算法不穩(wěn)定、易于產(chǎn)生大社區(qū)的問(wèn)題；Liu等[7]結(jié)合LPAm與多步貪婪凝聚算法（MSG）提出了模塊化專業(yè)化標(biāo)簽傳播算法（LPAm+），解決了LPAm算法在模塊空間中存在局部最大值的缺陷問(wèn)題，使社區(qū)發(fā)現(xiàn)結(jié)果更加準(zhǔn)確。此后，很多研究人員也針對(duì)標(biāo)簽傳播算法LPA存在的問(wèn)題對(duì)算法進(jìn)行了改進(jìn)，這些改進(jìn)一定程度上解決了算法的隨機(jī)性和不穩(wěn)定性，但這些都屬于非重疊社區(qū)發(fā)現(xiàn)算法，現(xiàn)實(shí)情況是在某個(gè)社區(qū)中的人可能和另外一些社區(qū)存在緊密關(guān)聯(lián)，例如某些人既喜歡籃球又喜歡足球，那么他們可能既是籃球愛(ài)好者協(xié)會(huì)又是足球愛(ài)好者協(xié)會(huì)的會(huì)員，這些人的歸屬問(wèn)題則不可忽略。因此，要求具有重疊社區(qū)挖掘能力的算法解決這些問(wèn)題。endprint

針對(duì)重疊的網(wǎng)絡(luò)結(jié)構(gòu)，Gregory等[8]提出可識(shí)別重疊社區(qū)結(jié)構(gòu)的COPRA算法。該算法基于LPA算法引入了社區(qū)從屬系數(shù)，具備了重疊社區(qū)挖掘能力，但該算法并沒(méi)有改變標(biāo)簽傳播算法的隨機(jī)選擇問(wèn)題，而且標(biāo)簽數(shù)量過(guò)多時(shí)，算法性能大幅降低；武志昊等[9]提出一種基于均衡多標(biāo)簽傳播的重疊社團(tuán)發(fā)現(xiàn)BMLPA算法。該算法對(duì)節(jié)點(diǎn)所屬的社區(qū)個(gè)數(shù)沒(méi)有限制，只要求同一節(jié)點(diǎn)的標(biāo)簽具有平衡的歸屬系數(shù)，但該算法的標(biāo)簽初始化策略使算法花費(fèi)時(shí)間較長(zhǎng)。

那有沒(méi)有什么辦法可以避免探測(cè)非重疊或重疊社區(qū)的時(shí)間復(fù)雜度問(wèn)題，又能保持LPA算法的原有優(yōu)點(diǎn)呢？針對(duì)該問(wèn)題，Xie等[10]提出一種能夠?qū)崿F(xiàn)動(dòng)態(tài)探測(cè)的重疊社區(qū)發(fā)現(xiàn)算法SLPA，SLPA 中引入了Listener和Speaker兩個(gè)比較形象的概念。

SLPA設(shè)置了兩個(gè)參數(shù)（T，r），T是最大迭代次數(shù)，r是過(guò)濾社區(qū)標(biāo)簽的閾值。與LPA相比，SLPA最大的特點(diǎn)在于它會(huì)記錄每一個(gè)節(jié)點(diǎn)在刷新迭代過(guò)程中的歷史標(biāo)簽序列（例如迭代T次，則每個(gè)節(jié)點(diǎn)將保存一個(gè)長(zhǎng)度為T的序列）。當(dāng)?shù)Ｖ购螅瑢?duì)每一個(gè)節(jié)點(diǎn)歷史標(biāo)簽序列中各互異標(biāo)簽出現(xiàn)的頻率作統(tǒng)計(jì)。通過(guò)改變閾值r的值，可以去除那些概率較小的標(biāo)簽，只保留概率較大的標(biāo)簽。而且SLPA算法可以很容易地轉(zhuǎn)換為L(zhǎng)PA算法，當(dāng)標(biāo)簽隊(duì)列只能存儲(chǔ)一個(gè)標(biāo)簽時(shí)，SLAP算法則退化為L(zhǎng)PA算法，只能識(shí)別出非重疊社區(qū)。當(dāng)r的值在0～0.5之間時(shí)，SLPA可以識(shí)別出重疊社區(qū)；當(dāng)r的值大于0.5時(shí)，SLPA用于發(fā)現(xiàn)非重疊社區(qū)。

SLPA算法的實(shí)現(xiàn)步驟為：首先，在每一個(gè)節(jié)點(diǎn)的存儲(chǔ)器中初始化一個(gè)唯一標(biāo)簽，然后重復(fù)以下步驟，直到達(dá)到最大迭代次數(shù)：①選擇當(dāng)前節(jié)點(diǎn)作為L(zhǎng)istener；②當(dāng)前節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)根據(jù)一定的Speaking策略傳遞標(biāo)簽信息；③當(dāng)前節(jié)點(diǎn)從鄰居節(jié)點(diǎn)傳播的標(biāo)簽信息集中，根據(jù)一定的Listener策略選擇一個(gè)標(biāo)簽加載到自己的標(biāo)簽隊(duì)列中，作為本次更新的標(biāo)簽。最后，后處理階段根據(jù)節(jié)點(diǎn)的標(biāo)簽信息進(jìn)行社區(qū)發(fā)現(xiàn)。

SLPA算法存在的問(wèn)題包括：

（1）在標(biāo)簽初始化過(guò)程中，SLPA算法為每一個(gè)節(jié)點(diǎn)都分配一個(gè)唯一標(biāo)簽，對(duì)于復(fù)雜節(jié)點(diǎn)眾多的復(fù)雜網(wǎng)絡(luò)，標(biāo)簽分配會(huì)消耗大量資源。而且標(biāo)簽選擇仍然存在隨機(jī)性選擇問(wèn)題，因?yàn)榈谝淮蔚鷷r(shí)待更新標(biāo)簽會(huì)有多個(gè)候選標(biāo)簽，它會(huì)從鄰居標(biāo)簽集合中隨機(jī)選擇一個(gè)作為新標(biāo)簽加載到自己的標(biāo)簽隊(duì)列中。

（2）在標(biāo)簽傳播過(guò)程中，Speaker策略是從鄰居節(jié)點(diǎn)的標(biāo)簽隊(duì)列中隨機(jī)選擇一個(gè)標(biāo)簽作為鄰居節(jié)點(diǎn)標(biāo)簽集合的元素，而Listener策略是選擇鄰居節(jié)點(diǎn)標(biāo)簽集合中個(gè)數(shù)最多的那個(gè)標(biāo)簽作為當(dāng)前節(jié)點(diǎn)的新標(biāo)簽，這種隨機(jī)性選擇造成了SLPA算法的隨機(jī)性和不穩(wěn)定性。

2 基于節(jié)點(diǎn)相似度的標(biāo)簽傳播算法

由于SLPA的隨機(jī)選擇策略降低了算法的穩(wěn)定性和準(zhǔn)確性，因此本文提出一種基于節(jié)點(diǎn)相似度的標(biāo)簽傳播算法NS-SLPA。本算法利用節(jié)點(diǎn)相似度改變標(biāo)簽的標(biāo)簽初始化過(guò)程，并在標(biāo)簽傳播過(guò)程中降低SLPA的隨機(jī)性選擇。

2.1 節(jié)點(diǎn)相似度度量

2.1.1 基于共同鄰居數(shù)的CN指標(biāo)

從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)角度出發(fā)，考慮兩個(gè)節(jié)點(diǎn)的共同鄰居數(shù)，即Common Neighbors（CN）[11]。共同鄰居CN是基于網(wǎng)絡(luò)半結(jié)構(gòu)信息定義相似度最簡(jiǎn)單的方法。兩個(gè)節(jié)點(diǎn)擁有更多共同鄰居，說(shuō)明兩個(gè)節(jié)點(diǎn)的聯(lián)系更緊密，相似性也越大，因此越有可能歸屬于同一社區(qū)。例如，兩個(gè)共同愛(ài)好籃球的人，他們彼此互不相識(shí)，但是兩人有一些共同認(rèn)識(shí)的喜歡籃球的人，如果他們相互認(rèn)識(shí)的人很多，則兩個(gè)人在同一地區(qū)或在同一個(gè)愛(ài)好者協(xié)會(huì)的可能性很大。

對(duì)于網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)Vx，其鄰居節(jié)點(diǎn)集用Γ（x）表示，則任意兩個(gè)節(jié)點(diǎn)Vx和Vy的相似度可表示為：

2.1.2 其它規(guī)范化指標(biāo)

在CN指標(biāo)的基礎(chǔ)上增加節(jié)點(diǎn)度的影響，得到6 種規(guī)范的相似性指標(biāo)，包括Salton指標(biāo)[12]、Adamic-Adar指標(biāo)[13]等，本文選用比較靈敏的Salton指標(biāo)。Salton指標(biāo)的定義是兩個(gè)節(jié)點(diǎn)共同鄰居數(shù)比上它們各自節(jié)點(diǎn)度之積的平方根，又稱為余弦相似性：

2.2 基于節(jié)點(diǎn)相似度的標(biāo)簽傳播算法NS-SLPA

本算法根據(jù)SLPA自身的特性，利用節(jié)點(diǎn)相似度改變標(biāo)簽的初始化過(guò)程，使節(jié)點(diǎn)初始化時(shí)按照節(jié)點(diǎn)度進(jìn)行順序排列，并給度最大的節(jié)點(diǎn)分配一個(gè)標(biāo)簽；然后計(jì)算當(dāng)前節(jié)點(diǎn)和鄰居節(jié)點(diǎn)的相似度，相似度大于與所有鄰居的平均相似度時(shí)則分配與當(dāng)前節(jié)點(diǎn)相同的標(biāo)簽；所有鄰居判斷完成后根據(jù)節(jié)點(diǎn)順序重復(fù)以上操作，直到所有節(jié)點(diǎn)都有標(biāo)簽。標(biāo)簽傳播過(guò)程若有多個(gè)最大重?cái)?shù)標(biāo)簽時(shí)，則計(jì)算最大重?cái)?shù)標(biāo)簽節(jié)點(diǎn)與待更新節(jié)點(diǎn)的平均相似度，待更新節(jié)點(diǎn)選擇擁有最大平均相似度節(jié)點(diǎn)的標(biāo)簽進(jìn)行更新。算法的全部描述如下：

輸入：圖G=（V，E）；

輸出：各個(gè)社區(qū)C。

Begin

（1）為每個(gè)節(jié)點(diǎn)x提取出網(wǎng)絡(luò)鄰居集合N（x），并按照節(jié)點(diǎn)度進(jìn)行排序。

（2）選取當(dāng)前未處理的度最大的節(jié)點(diǎn)，為其分配唯一標(biāo)簽y。

（3）當(dāng)前節(jié)點(diǎn)鄰居集合為N（x），若當(dāng)前節(jié)點(diǎn)與某個(gè)節(jié)點(diǎn)的相似度Sxy≥與所有鄰居節(jié)點(diǎn)的平均相似度，則為其分配與當(dāng)前節(jié)點(diǎn)相同的標(biāo)簽，并標(biāo)記為已處理。

重復(fù)以上操作，直到所有節(jié)點(diǎn)x都有唯一的標(biāo)簽y。

（4）判斷，t≤最大迭代次數(shù)T：①當(dāng)前節(jié)點(diǎn)x作為L(zhǎng)istener；②當(dāng)前節(jié)點(diǎn)x的鄰居根據(jù)Speaking策略，選擇該節(jié)點(diǎn)在其存儲(chǔ)器中出現(xiàn)頻率最高的標(biāo)簽，進(jìn)行標(biāo)簽傳播；③當(dāng)前節(jié)點(diǎn)x從鄰居節(jié)點(diǎn)傳播的標(biāo)簽信息集N（y）中選擇最大重疊數(shù)標(biāo)簽y加載到自己的標(biāo)簽隊(duì)列中，若有多個(gè)最大重疊數(shù)標(biāo)簽時(shí)，則計(jì)算擁有相同最大重疊數(shù)標(biāo)簽的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的平均相似度，選擇與當(dāng)前節(jié)點(diǎn)x擁有最大平均相似度節(jié)點(diǎn)的標(biāo)簽作為更新標(biāo)簽。

（5）節(jié)點(diǎn)更新完畢，令t=t+1。endprint

（6）當(dāng)t>T時(shí)，根據(jù)閾值r劃分節(jié)點(diǎn)x所屬的社區(qū)C。

End

3 實(shí)驗(yàn)分析

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

3.1.1 模塊度Q

對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，需要有一些評(píng)價(jià)指標(biāo)，以評(píng)判算法對(duì)網(wǎng)絡(luò)劃分結(jié)果的好壞優(yōu)劣。Newman等提出了模塊度Q函數(shù)，該函數(shù)被廣泛應(yīng)用于社會(huì)網(wǎng)絡(luò)分析中衡量關(guān)系圈挖掘的好壞，是最常用的一種評(píng)價(jià)標(biāo)準(zhǔn)。其表示公式如下：

3.1.2 標(biāo)準(zhǔn)化互信息NMI

NMI是一種基于信息論理論的社區(qū)質(zhì)量評(píng)價(jià)指標(biāo)[14]，它通過(guò)計(jì)算已知社區(qū)結(jié)構(gòu)和由算法得到的社區(qū)結(jié)構(gòu)之間的相似度實(shí)現(xiàn)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)質(zhì)量的測(cè)度。其值越大，說(shuō)明算法結(jié)果社區(qū)與真實(shí)社區(qū)結(jié)構(gòu)相一致的程度越高，具體公式如下：

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

3.2.1 小規(guī)模數(shù)據(jù)集實(shí)驗(yàn)

選取“Social Analysis 973”區(qū)兩個(gè)規(guī)模較小的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別是科學(xué)家合作網(wǎng)絡(luò)和Enron電子郵件網(wǎng)絡(luò)，科學(xué)家合作網(wǎng)絡(luò)只選取相似度大于0.5的用戶節(jié)點(diǎn)，用戶若相互合作，則建立一條邊。網(wǎng)絡(luò)屬性如表1所示。

從模塊度Q、規(guī)范化互信息NMI角度衡量算法性能，如圖1、圖2所示。

從圖1、圖2中可以看出，在比較簡(jiǎn)單的網(wǎng)絡(luò)中，NS-SLPA算法所獲得的模塊度和準(zhǔn)確性都要高于SLPA算法。雖然模塊度Q提升并不是很明顯，但在準(zhǔn)確度方面，NS-SLPA有著SLPA算法無(wú)可比擬的優(yōu)勢(shì)，使準(zhǔn)確度有了較大程度的提升。

3.2.2 較大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)

選用兩個(gè)人工生成網(wǎng)絡(luò)，人工網(wǎng)絡(luò)是由網(wǎng)絡(luò)數(shù)據(jù)生成器LFR模擬生成的，通過(guò)LFR提供的豐富接口可靈活設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)、平均節(jié)點(diǎn)度與網(wǎng)絡(luò)模塊化度等參數(shù)，從而獲得不同類型的網(wǎng)絡(luò)數(shù)據(jù)。兩個(gè)人工網(wǎng)絡(luò)的網(wǎng)絡(luò)屬性如表2所示。

其中，μ是指網(wǎng)絡(luò)中社區(qū)間的連接數(shù)占所有邊總和的比例，實(shí)驗(yàn)結(jié)果如圖3、圖4所示。

從圖3、圖4可以看出，在迭代次數(shù)較小時(shí)，NS-SLPA算法的模塊度和精確度明顯高于SLPA算法；隨著迭代次數(shù)增加，兩種算法在模塊度和準(zhǔn)確度上都有增長(zhǎng)趨勢(shì)，但SLPA的波動(dòng)幅度更大，且穩(wěn)定性差，在大型網(wǎng)絡(luò)中表現(xiàn)得尤為明顯，而NS-SLPA算法更加穩(wěn)定。

4 結(jié)語(yǔ)

本文針對(duì)社區(qū)發(fā)現(xiàn)算法SLPA的缺陷提出了一種基于節(jié)點(diǎn)相似度的標(biāo)簽傳播算法NS-SLPA，通過(guò)在標(biāo)簽初始化階段，讓節(jié)點(diǎn)按節(jié)點(diǎn)度進(jìn)行排序，并根據(jù)節(jié)點(diǎn)相似度對(duì)鄰居節(jié)點(diǎn)賦予標(biāo)簽，大大簡(jiǎn)化了標(biāo)簽初始化過(guò)程中的資源消耗；在標(biāo)簽傳播過(guò)程中，通過(guò)標(biāo)簽節(jié)點(diǎn)的平均相似度降低標(biāo)簽的隨機(jī)行選擇，增加了算法的穩(wěn)定性與準(zhǔn)確性。在多個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，證明了NS-SLPA算法比SLPA算法擁有更高的準(zhǔn)確性和穩(wěn)定性，而且在較復(fù)雜的網(wǎng)絡(luò)中表現(xiàn)更加明顯。

參考文獻(xiàn)：

[1] 王恒軍.社團(tuán)網(wǎng)絡(luò)的有限時(shí)間聚類同步研究[D].南昌：江西師范大學(xué)，2016.

[2] NEWMAN ME， GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E，2004，69（2）：026113.

[3] P PONS， M LAPATY. Computing communities in large networks using random walks[J]. Journal of Graph Algorithms& Applications，2004，3733（2）：284-293.

[4] RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in Networks[J]. The National Academy of Sciences，2004，101（9）：2658-2663.

[5] U N RAGHAVAN， R ALBERT， S KUMARA. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E，2007，76（3）：036106.

[6] BARBERMJ， CLARKJW. Detecting network communities by propagating labels under constraint[J]. Physical Review E，2009，80（2）：129-139.

[7] LIU X， MURATA T. Advanced modularity-specialized label propagation algorithm fordetecting communities in networks[J]. Physical a Statistical Mechanics and Its Applications，2010，389（7）：1493-1500.

[8] GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics，2010，12（10）：103-123.

[9] 武志昊，林友芳，田盛豐，等.高度重疊社區(qū)的社區(qū)合并優(yōu)化算法[J].北京交通大學(xué)學(xué)報(bào)，2011，35（3）：116-122.

[10] XIE J， SZYMANKI BK， LIU X. SLPA： uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]. 2011 11th IEEE International Conference on Data MiningWorkshops. IEEE Computer Society，2011：344-349.

[11] 郭婷婷，趙承業(yè).基于共同鄰居的鏈路預(yù)測(cè)新指標(biāo)[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào)，2016，27（1）：121-124.

[12] G SALTON， M J MCGILL. Introduction to modern information retrieval[M]. McGraw-Hill，1983，41（4）：305-306.

[13] LA ADAMIC，E ADAR. Friends and neighbors on the Web[J].Social Networks，2003，25（3）：211-230.

[14] 汪焱，黃發(fā)良，元昌安.基于標(biāo)簽影響力的半同步社區(qū)發(fā)現(xiàn)算法[C].計(jì)算機(jī)應(yīng)用，2016，36（6）：1573-1578.endprint