一種面向社區(qū)發(fā)現(xiàn)的高魯棒性標(biāo)簽傳播算法

鄭少?gòu)?qiáng),趙中英,2,3,馮慧子,李 超,2

1(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,山東 青島 266590) 2(中國(guó)科學(xué)院 深圳先進(jìn)技術(shù)研究院,廣東 深圳 518055) 3(桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004) E-mail:zyzhao@sdust.edu.cn或 lichao@sdust.edu.cn

1 引 言

社會(huì)網(wǎng)絡(luò)是指?jìng)€(gè)體間交互形成相對(duì)穩(wěn)定的社會(huì)關(guān)系,這種關(guān)系通常被形式化表示成圖的形式,圖中節(jié)點(diǎn)表示個(gè)體,邊表示個(gè)體之間存在的某種聯(lián)系.社區(qū)是社會(huì)網(wǎng)絡(luò)最重要的組成單元結(jié)構(gòu),也是分析社會(huì)網(wǎng)絡(luò)規(guī)律、性能等方面重要的參考依據(jù).所謂社區(qū)發(fā)現(xiàn),是指把網(wǎng)絡(luò)中聯(lián)系緊密或具有相似特征的節(jié)點(diǎn)劃分為一個(gè)簇,即同一社區(qū)內(nèi)部節(jié)點(diǎn)間鏈接稠密,不同社區(qū)之間的鏈接稀疏.研究網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)有助于揭示網(wǎng)絡(luò)的組織結(jié)構(gòu)、拓普信息等特性,具有十分重要的意義[1],因此,社會(huì)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)引起學(xué)術(shù)界與產(chǎn)業(yè)界學(xué)者的廣泛關(guān)注[2-4].

目前,針對(duì)社區(qū)發(fā)現(xiàn)的研究方法層出不窮,依據(jù)采用的求解策略問(wèn)題,可分為基于優(yōu)化的社區(qū)發(fā)現(xiàn)方法和基于啟發(fā)式的社區(qū)發(fā)現(xiàn)方法.基于優(yōu)化的方法是通過(guò)設(shè)置目標(biāo)函數(shù)來(lái)實(shí)現(xiàn)社區(qū)劃分,代表性方法有譜方法和模塊性最大化方法[5-7]等;基于啟發(fā)式策略的方法是通過(guò)設(shè)置啟發(fā)式規(guī)則尋找最優(yōu)社區(qū)劃分,代表性算法有GN算法[8]和WH算法[9]等.此外像基于層次聚類的社區(qū)發(fā)現(xiàn)方法也能有效劃分社區(qū)結(jié)構(gòu),但這種方法一般具有較高的時(shí)間復(fù)雜度,不適用大規(guī)模網(wǎng)絡(luò)挖掘.2007年,Raghavan等人[10]提出一種基于標(biāo)簽傳播的快速社區(qū)發(fā)現(xiàn)算法LPA(Label Propagation Algorithm),該算法具有線性的時(shí)間復(fù)雜度,在處理大規(guī)模網(wǎng)絡(luò)時(shí)具有較高的時(shí)間效率,并且不需要優(yōu)化預(yù)定義的目標(biāo)函數(shù),預(yù)知社區(qū)數(shù)量等先驗(yàn)知識(shí),因此得到學(xué)者的廣泛關(guān)注.但LPA算法在更新節(jié)點(diǎn)標(biāo)簽過(guò)程中存在不確定性,導(dǎo)致結(jié)果準(zhǔn)確性和穩(wěn)定性常不能達(dá)到預(yù)期效果.目前不同學(xué)者對(duì)原始的LPA算法進(jìn)行改進(jìn),其中LPAm[11]算法是一種帶約束的標(biāo)簽傳播算法,它將LPA等價(jià)為一個(gè)優(yōu)化問(wèn)題來(lái)發(fā)現(xiàn)社區(qū)結(jié)構(gòu);COPRA算法[12]可以通過(guò)標(biāo)簽傳播發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu),COPRA算法為每個(gè)節(jié)點(diǎn)保留若干個(gè)社區(qū)標(biāo)簽,并進(jìn)行標(biāo)簽傳播最終節(jié)點(diǎn)得到多個(gè)標(biāo)簽節(jié)點(diǎn)信息;趙卓翔[13]等人對(duì)初始網(wǎng)絡(luò)的部分節(jié)點(diǎn)進(jìn)行分析處理,并且從部分節(jié)點(diǎn)進(jìn)行標(biāo)簽傳播,在LPA算法的基礎(chǔ)上提高了社區(qū)發(fā)現(xiàn)質(zhì)量,黃佳鑫[14]等人在節(jié)點(diǎn)重要性和影響力的基礎(chǔ)上對(duì)其標(biāo)簽傳播的過(guò)程進(jìn)行優(yōu)化,該方法雖然提高了社區(qū)發(fā)現(xiàn)的質(zhì)量,但同時(shí)增加了算法運(yùn)行時(shí)間.

本文主要工作是在標(biāo)簽傳播算法基礎(chǔ)上,融合考慮節(jié)點(diǎn)度數(shù)和聚集系數(shù)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的初始標(biāo)簽進(jìn)行分配,從而減少初始節(jié)點(diǎn)標(biāo)簽分配數(shù)量,提高標(biāo)簽傳播的穩(wěn)定性和社區(qū)發(fā)現(xiàn)質(zhì)量,在此基礎(chǔ)上減少標(biāo)簽傳播過(guò)程的迭代次數(shù).

2 相關(guān)工作

2.1 聚集系數(shù)概念

復(fù)雜網(wǎng)絡(luò)中,節(jié)點(diǎn)的聚集系數(shù)(Node Clustering Coefficient)是考慮節(jié)點(diǎn)的鄰居節(jié)點(diǎn)間關(guān)系緊密程度的重要參考依據(jù)之一,節(jié)點(diǎn)的聚集系數(shù)可以表示為該節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)間的實(shí)際連邊數(shù)與所有可能存在連邊數(shù)的比值.

一般地,假設(shè)在一個(gè)無(wú)向無(wú)權(quán)的復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)i的度為ki,表示節(jié)點(diǎn)i有k個(gè)鄰接點(diǎn),而這些鄰接點(diǎn)之間所有可能存在的連邊數(shù)為k·(k-1)/2.如果節(jié)點(diǎn)i的鄰接點(diǎn)之間的實(shí)際連邊數(shù)為E(i),用CC(i)表示該節(jié)點(diǎn)的點(diǎn)聚集系數(shù),則表示為:

(1)

顯然,節(jié)點(diǎn)聚集系數(shù)反應(yīng)了節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間的關(guān)系.聚集系數(shù)越大,說(shuō)明節(jié)點(diǎn)近鄰之間的關(guān)系越密切,他們屬于同一個(gè)社區(qū)的概率也就越大,反之聚集系數(shù)越小則它們聯(lián)系越疏遠(yuǎn),屬于同一個(gè)社區(qū)的概率也越小.

2.2 標(biāo)簽傳播基本思想

標(biāo)簽傳播算法[10](Label Propagation Algorithm)是一種啟發(fā)式的算法,其啟發(fā)規(guī)則是不斷在節(jié)點(diǎn)及近鄰間傳遞標(biāo)簽信息,經(jīng)過(guò)多次迭代,屬于同一社區(qū)節(jié)點(diǎn)的標(biāo)簽將趨于一致.其核心思想是給所有的節(jié)點(diǎn)標(biāo)記唯一標(biāo)簽,對(duì)每個(gè)節(jié)點(diǎn),它的標(biāo)簽代表所屬社區(qū),對(duì)節(jié)點(diǎn)進(jìn)行標(biāo)簽傳播的過(guò)程,即是對(duì)每個(gè)節(jié)點(diǎn)的標(biāo)簽進(jìn)行更新,其標(biāo)簽選擇權(quán)主要取決于該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的標(biāo)簽分布情況,選取鄰居節(jié)點(diǎn)標(biāo)簽數(shù)最多的節(jié)點(diǎn)來(lái)更新自己節(jié)點(diǎn)的標(biāo)簽,依次迭代直到所有節(jié)點(diǎn)的標(biāo)簽不再發(fā)生變化,最終標(biāo)簽相同的節(jié)點(diǎn)屬于同一個(gè)社區(qū),從而達(dá)到劃分社區(qū)目的.

2.3 標(biāo)簽傳播步驟

1)網(wǎng)絡(luò)初始化階段,為網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)分配唯一的標(biāo)簽,表示該節(jié)點(diǎn)所屬的社區(qū)編號(hào);

2)對(duì)圖中的所有節(jié)點(diǎn)以隨機(jī)的順序進(jìn)行標(biāo)簽的迭代更新.在每次迭代過(guò)程中,每個(gè)節(jié)點(diǎn)的標(biāo)簽由其鄰居節(jié)點(diǎn)的標(biāo)簽中數(shù)目最多的那個(gè)標(biāo)簽來(lái)決定,如果鄰居節(jié)點(diǎn)中有數(shù)目相同的最多個(gè)標(biāo)簽存在,則在這些數(shù)量相同的標(biāo)簽中隨機(jī)選取一個(gè)作為該節(jié)點(diǎn)的標(biāo)簽;

3)反復(fù)迭代,直到其所有節(jié)點(diǎn)都擁有鄰居節(jié)點(diǎn)中數(shù)目最多的標(biāo)簽為止;

4)具有相同標(biāo)簽的節(jié)點(diǎn)就可以歸在同一個(gè)社區(qū)中,完成社區(qū)劃分,算法結(jié)束.

3 LPA_D_CC算法

在社會(huì)網(wǎng)絡(luò)中,節(jié)點(diǎn)度被認(rèn)為是重要的評(píng)價(jià)指標(biāo)之一,它能夠直觀衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性,一般來(lái)說(shuō),節(jié)點(diǎn)度數(shù)越大,說(shuō)明節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性越明顯,其相鄰節(jié)點(diǎn)數(shù)越多,形成社區(qū)的概率越大.而在社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間的關(guān)系也同樣重要,如果一個(gè)節(jié)點(diǎn)與它鄰居節(jié)點(diǎn)之間可以形成穩(wěn)定的三角關(guān)系這說(shuō)明節(jié)點(diǎn)之間存在緊密的聯(lián)系,且具有某種相同性質(zhì)的可能性越大.

目前所做的工作中,大多數(shù)標(biāo)簽傳播算法只考慮算法在標(biāo)簽更新階段情況,未在網(wǎng)絡(luò)初始化過(guò)程中對(duì)節(jié)點(diǎn)的標(biāo)簽進(jìn)行處理,這種情況導(dǎo)致標(biāo)簽傳播存在不穩(wěn)定因素.本文針對(duì)這一問(wèn)題在網(wǎng)絡(luò)初始化階段對(duì)節(jié)點(diǎn)標(biāo)簽賦值做一些改進(jìn)措施,從而改善節(jié)點(diǎn)標(biāo)簽傳播隨機(jī)性問(wèn)題,同時(shí)減少傳播過(guò)程的迭代次數(shù),提高社區(qū)劃分的穩(wěn)定性和劃分質(zhì)量.

3.1 主要思想及步驟

本文主要考慮標(biāo)簽傳播初始階段,結(jié)合節(jié)點(diǎn)度數(shù)和聚集系數(shù)兩方面對(duì)初始化節(jié)點(diǎn)賦值進(jìn)行處理.首先在給定網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)度數(shù),并根據(jù)度數(shù)大小對(duì)節(jié)點(diǎn)進(jìn)行排序.當(dāng)節(jié)點(diǎn)度數(shù)相等時(shí),分析節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間的關(guān)系,即聚集系數(shù)大小,根據(jù)兩個(gè)判定條件對(duì)網(wǎng)絡(luò)所有節(jié)點(diǎn)做影響力排序.然后對(duì)影響力高的節(jié)點(diǎn),訪問(wèn)該節(jié)點(diǎn)和它鄰居節(jié)點(diǎn)并將它們構(gòu)成一個(gè)集合,對(duì)沒有訪問(wèn)過(guò)的節(jié)點(diǎn),繼續(xù)對(duì)影響力高的節(jié)點(diǎn)進(jìn)行訪問(wèn),將它和它沒有被訪問(wèn)過(guò)的鄰居節(jié)點(diǎn)構(gòu)成集合,每個(gè)節(jié)點(diǎn)只能被訪問(wèn)一次,依次訪問(wèn)直到所有節(jié)點(diǎn)被訪問(wèn)過(guò)為止,這樣構(gòu)成若干個(gè)集合.對(duì)若干個(gè)集合內(nèi)的節(jié)點(diǎn)賦相同標(biāo)簽,集合之間標(biāo)簽不同.根據(jù)網(wǎng)絡(luò)中已賦予的標(biāo)簽節(jié)點(diǎn)進(jìn)行標(biāo)簽傳播,最終當(dāng)所有節(jié)點(diǎn)標(biāo)簽都擁有鄰居節(jié)點(diǎn)標(biāo)簽數(shù)最大的標(biāo)簽算法結(jié)束,標(biāo)簽相同的節(jié)點(diǎn)屬于同一個(gè)社區(qū).該方法主要分為兩個(gè)階段,第一階段是網(wǎng)絡(luò)節(jié)點(diǎn)賦標(biāo)簽的準(zhǔn)備階段;第二階段是節(jié)點(diǎn)賦標(biāo)簽和標(biāo)簽傳播過(guò)程.

3.2 網(wǎng)絡(luò)節(jié)點(diǎn)準(zhǔn)備階段

第一階段主要根據(jù)節(jié)點(diǎn)度數(shù)和聚集系數(shù)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力進(jìn)行排序,并對(duì)所有節(jié)點(diǎn)劃分集合,為下一步的標(biāo)簽傳播做準(zhǔn)備.

算法1.基于度與聚集系數(shù)的節(jié)點(diǎn)影響力排序算法

輸入:網(wǎng)絡(luò)G(V,E)

輸出:網(wǎng)絡(luò)G的若干集合Si

1.網(wǎng)絡(luò)初始化G(V,E);

2.計(jì)算V(G)度數(shù)D(V)并排序

3.如果D(V)相等,根據(jù)節(jié)點(diǎn)聚集系數(shù)CC(V)排序;

4.FOR V IN S:

IF V 沒有被訪問(wèn)過(guò);

將 V 加入集合S中;

標(biāo)記節(jié)點(diǎn)V;

FOR U IN V的鄰居節(jié)點(diǎn):

IF U 沒有被訪問(wèn)過(guò):

將U加入集合S中;

標(biāo)記加入過(guò)的節(jié)點(diǎn)U;

END

END

END

END

返回若干集合Si

3.3 社區(qū)劃分階段

第二階段是對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)賦標(biāo)簽,對(duì)于若干個(gè)集合的節(jié)點(diǎn),我們認(rèn)為集合內(nèi)節(jié)點(diǎn)在某方面具有相同的特性,將這些集合中的節(jié)點(diǎn)賦予相同標(biāo)簽,利用標(biāo)簽傳播原理根據(jù)每個(gè)節(jié)點(diǎn)鄰居的標(biāo)簽數(shù)量決定自己標(biāo)簽,依次迭代直到所有節(jié)點(diǎn)的標(biāo)簽不再發(fā)生變化,完成社區(qū)劃分.

算法2.基于LPA的社區(qū)發(fā)現(xiàn)算法

輸入:若干個(gè)集合Si

輸出:網(wǎng)絡(luò)G的社區(qū)劃分

1.針對(duì)若干個(gè)集合Si;

2.將這些集合Si賦予不同標(biāo)簽,集合中節(jié)點(diǎn)的標(biāo)簽相同;

3.根據(jù)標(biāo)簽傳播理論,對(duì)節(jié)點(diǎn)標(biāo)簽進(jìn)行傳播;

4.反復(fù)迭代直到節(jié)點(diǎn)標(biāo)簽不再發(fā)生變化,算法結(jié)束;

5.標(biāo)簽相同的節(jié)點(diǎn)屬于同一個(gè)社區(qū).

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

4.1 實(shí)驗(yàn)數(shù)據(jù)及運(yùn)行環(huán)境

本文選用社會(huì)網(wǎng)絡(luò)中常用的四個(gè)數(shù)據(jù)集對(duì)算法進(jìn)行分析驗(yàn)證,實(shí)驗(yàn)數(shù)據(jù)采取Mark Newman等人個(gè)人網(wǎng)頁(yè)上提供的網(wǎng)絡(luò)數(shù)據(jù)集,包括Karate club、Polbooks、Netscience和Power數(shù)據(jù)集.數(shù)據(jù)集詳細(xì)描述如下:

1)Karate Club空手道俱樂(lè)部網(wǎng)絡(luò):Karate Club空手道俱樂(lè)部網(wǎng)絡(luò)數(shù)據(jù)集是Zachary用三年時(shí)間觀察了美國(guó)一所大學(xué)空手道俱樂(lè)部成員之間的關(guān)系構(gòu)成的社會(huì)網(wǎng)絡(luò).網(wǎng)絡(luò)中節(jié)點(diǎn)表示俱樂(lè)部成員,節(jié)點(diǎn)之間的連邊表示成員之間的朋友關(guān)系.該網(wǎng)絡(luò)包括34個(gè)節(jié)點(diǎn)、78條邊.

2)Polbooks:該數(shù)據(jù)集是V.Krebs從Amazon上銷售的美國(guó)政治相關(guān)書籍頁(yè)面上建立的網(wǎng)絡(luò),網(wǎng)絡(luò)中的節(jié)點(diǎn)表示在Amazon在線書店上銷售的美國(guó)政治相關(guān)圖書,邊表示一定數(shù)量的讀者同時(shí)購(gòu)買了這兩本書的情況.政治書籍網(wǎng)絡(luò)包括105個(gè)節(jié)點(diǎn)、441條邊.

3)Netscience:科學(xué)家共同作者網(wǎng)絡(luò)描述的是在網(wǎng)絡(luò)上科學(xué)家之間的合作關(guān)系,通過(guò)網(wǎng)絡(luò)上科學(xué)家合作實(shí)驗(yàn)以及共同提出相關(guān)理論構(gòu)成的關(guān)系網(wǎng)絡(luò).網(wǎng)絡(luò)中節(jié)點(diǎn)表示網(wǎng)絡(luò)上的科學(xué)家,邊表示科學(xué)家之間的合作關(guān)系.該網(wǎng)絡(luò)是由1589個(gè)節(jié)點(diǎn)和2742條邊構(gòu)成.

4)Power:美國(guó)西部地區(qū)電網(wǎng)拓?fù)鋽?shù)據(jù)集網(wǎng)絡(luò),該網(wǎng)絡(luò)主要涉及美國(guó)西部地區(qū)發(fā)電設(shè)備之間的關(guān)系.網(wǎng)絡(luò)中的節(jié)點(diǎn)表示發(fā)電器、變壓器和變電站設(shè)備,網(wǎng)絡(luò)中的邊表示這些設(shè)備之間高壓輸電的關(guān)系.美國(guó)西部電網(wǎng)一共由4941個(gè)節(jié)點(diǎn)和6594條邊構(gòu)成.

表1 實(shí)驗(yàn)數(shù)據(jù)描述Table 1 Description of experimental data

所有實(shí)驗(yàn)均運(yùn)行于配置為AMD A4-3300M APU with Radeon(tm)HD Graphics 1.90GHz、2核處理器且內(nèi)存為4GB的Windows機(jī)器上.算法均在pycharm 4.5環(huán)境上,用python2.7編程語(yǔ)言實(shí)現(xiàn).為避免實(shí)驗(yàn)過(guò)程中偶然性的發(fā)生,我們?nèi)?shí)驗(yàn)運(yùn)行100次的平均結(jié)果作為最終結(jié)果進(jìn)行分析驗(yàn)證.

4.2 評(píng)價(jià)指標(biāo)

本文根據(jù)模塊度評(píng)價(jià)指標(biāo)評(píng)價(jià)社區(qū)劃分情況,模塊度(Modularity)由Newman[15]等人提出,該度量是對(duì)于給定網(wǎng)絡(luò)的任意社區(qū)劃分都有一個(gè)評(píng)價(jià)值,以此判斷社區(qū)發(fā)現(xiàn)算法的優(yōu)劣.模塊度定義為社區(qū)內(nèi)實(shí)際連接數(shù)目與對(duì)應(yīng)隨機(jī)網(wǎng)絡(luò)同等連接情況下社區(qū)期望連接數(shù)目之差,用來(lái)定量地刻畫網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的優(yōu)劣,模塊度的形式化定義如下:

Q=∑i[eii-(ai)2]

(2)

其中,eii是節(jié)點(diǎn)在社區(qū)i內(nèi)部的邊的權(quán)值所占的比例,ai表示與社區(qū)i中節(jié)點(diǎn)相關(guān)聯(lián)的所有邊的權(quán)值所占的比例,ai表示為:

(3)

其中,kv表示節(jié)點(diǎn)v的度,cv表示節(jié)點(diǎn)v所在的社區(qū),m表示網(wǎng)絡(luò)中總邊數(shù).模塊度Q的取值在0和1之間,Q值越接近1說(shuō)明社區(qū)結(jié)構(gòu)越明顯.

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

我們對(duì)改進(jìn)的LPA_D_CC算法和原始的LPA算法在四種數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn),為驗(yàn)證算法劃分質(zhì)量和穩(wěn)定性等,我們從模塊度、迭代次數(shù)等方面進(jìn)行分析與比較.

4.3.1 Karate數(shù)據(jù)集可視化效果

Karate數(shù)據(jù)集具有標(biāo)準(zhǔn)的社區(qū)劃分,其中34個(gè)成員節(jié)點(diǎn)主要分成以主管(節(jié)點(diǎn)0)和校長(zhǎng)(節(jié)點(diǎn)32)為中心的兩個(gè)集合.我們將LPA算法和LPA_D_CC算法在Karate數(shù)據(jù)集上做可視化效果,如圖1所示,原始的LPA算法在社區(qū)劃分過(guò)程中并沒有合理地將這兩個(gè)主要節(jié)點(diǎn)作為影響力較大節(jié)點(diǎn)進(jìn)行社區(qū)劃分,并分成四個(gè)社區(qū)集合.LPA_D_CC算法可以穩(wěn)定的將Karate數(shù)據(jù)集以節(jié)點(diǎn)0和32為中心劃分為兩個(gè)社區(qū),圖中不同顏色代表不同社區(qū).

圖1 Karate數(shù)據(jù)中的社區(qū)可視化Fig.1 Visualization of communities detected in Karate data

4.3.2 社區(qū)發(fā)現(xiàn)數(shù)量

為了驗(yàn)證社區(qū)劃分的穩(wěn)定性,我們從社區(qū)劃分?jǐn)?shù)量方面分析,如表2所示,原始LPA算法在社區(qū)劃分?jǐn)?shù)量方面起伏較大,并隨著網(wǎng)絡(luò)規(guī)模增大方差變大,穩(wěn)定性效果差.LPA_D_CC算法社區(qū)劃分?jǐn)?shù)量方面比較穩(wěn)定,社區(qū)數(shù)量變化浮動(dòng)小,社區(qū)劃分?jǐn)?shù)量的隨機(jī)性弱,表現(xiàn)出算法的穩(wěn)定性.

表2 社區(qū)數(shù)量對(duì)比Table 2 Quantitative comparison of communities

表3 迭代次數(shù)對(duì)比Table 3 Comparison of iterations

4.3.3 迭代次數(shù)

原始LPA算法在傳播過(guò)程中,每次迭代都可能面臨隨機(jī)選擇標(biāo)簽情況,這將導(dǎo)致社區(qū)劃分結(jié)果不穩(wěn)定,盡量減少迭代次數(shù)能有效降低社區(qū)隨機(jī)性產(chǎn)生.原始LPA算法與本文提出的LPA_D_CC算法在社區(qū)劃分過(guò)程中的迭代次數(shù)對(duì)比結(jié)果如表3所示.從表3可以看出,LPA_D_CC算法在任何情況下的迭代次數(shù)都小于LPA算法,并且迭代次數(shù)變化幅度小,遠(yuǎn)遠(yuǎn)優(yōu)于原始LPA算法.

4.3.4 模塊度評(píng)價(jià)

為了驗(yàn)證算法能夠降低隨機(jī)性造成模塊度較低的影響,本次實(shí)驗(yàn)從模塊度變化范圍和平均模塊度方面做了分析.從表4可以看出,LPA算法雖然在少數(shù)情況下模塊度值要高于LPA_D_CC算法,但大部分時(shí)間LPA_D_CC算法模塊度值優(yōu)勢(shì)明顯.從平均模塊度(圖2)角度分析LPA_D_CC算法平均模塊度值都高于LPA算法,并且LPA_D_CC算法方差小,具有較好的穩(wěn)定性,顯著提高了社區(qū)劃分質(zhì)量.

表4 模塊度對(duì)比Table 4 Comparison of modularity values

5 總結(jié)與展望

目前在復(fù)雜網(wǎng)絡(luò)中關(guān)于社區(qū)發(fā)現(xiàn)方面還有很多值得研究的問(wèn)題,例如算法在大型數(shù)據(jù)集中社區(qū)發(fā)現(xiàn)質(zhì)量和效率問(wèn)題,社區(qū)本身的定義問(wèn)題等等.傳統(tǒng)的標(biāo)簽傳播算法需要給每個(gè)節(jié)點(diǎn)賦予不同的初始標(biāo)簽,這導(dǎo)致傳播過(guò)程中時(shí)常存在不穩(wěn)定因素,影響社區(qū)劃分質(zhì)量.本文提出的算法分為兩個(gè)階段,第一階段根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)和聚集系數(shù),對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)做影響力排序,并將影響力高的節(jié)點(diǎn)和它鄰居節(jié)點(diǎn)劃分一個(gè)集合,重復(fù)此步驟直到網(wǎng)絡(luò)被劃分為若干個(gè)集合,此時(shí)可以對(duì)網(wǎng)絡(luò)做一個(gè)粗劃分.第二階段對(duì)若干個(gè)集合賦標(biāo)簽,并依靠標(biāo)簽傳播算法進(jìn)行調(diào)整得到最終的社區(qū)結(jié)構(gòu).實(shí)驗(yàn)結(jié)果表明,本文提出的算法能有效減少迭代次數(shù),同時(shí)保證社區(qū)劃分的準(zhǔn)確性和穩(wěn)定性,并且生成的社區(qū)質(zhì)量模塊度指標(biāo)優(yōu)于LPA算法.總體而言,所提出的LPA_D_CC算法有效解決了傳統(tǒng)LPA算法的魯棒性差等問(wèn)題.在將來(lái)的工作中,我們將嘗試在異構(gòu)網(wǎng)絡(luò)中對(duì)同一個(gè)節(jié)點(diǎn)賦多個(gè)標(biāo)簽,旨在研究重疊社區(qū)發(fā)現(xiàn)等工作.

圖2 平均模塊度比較Fig.2 Comparison of the average modularity values