復(fù)雜網(wǎng)絡(luò)中基于WCC的并行可擴(kuò)展社團(tuán)挖掘算法

亞森·艾則孜　李衛(wèi)平　郭文強(qiáng)

1(新疆警察學(xué)院信息安全工程系　新疆 烏魯木齊 830013)2(鐵道警察學(xué)院公安技術(shù)系　河南 鄭州 450053)3(新疆財(cái)經(jīng)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院　新疆 烏魯木齊 830013)

?

復(fù)雜網(wǎng)絡(luò)中基于WCC的并行可擴(kuò)展社團(tuán)挖掘算法

亞森·艾則孜1李衛(wèi)平2郭文強(qiáng)3

1(新疆警察學(xué)院信息安全工程系新疆 烏魯木齊 830013)2(鐵道警察學(xué)院公安技術(shù)系河南 鄭州 450053)3(新疆財(cái)經(jīng)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院新疆 烏魯木齊 830013)

摘要WCC(Weighted Community Clustering)通過(guò)復(fù)雜網(wǎng)絡(luò)中社團(tuán)含有的三角數(shù)量來(lái)評(píng)價(jià)社團(tuán)挖掘算法的性能。在原始的WCC算法中，需要在每次迭代中對(duì)所有的社團(tuán)變化計(jì)算WCC值，因而計(jì)算量非常大。為了減小社團(tuán)變化帶來(lái)的WCC計(jì)算量，提出一種并行可擴(kuò)展的社團(tuán)挖掘算法。對(duì)應(yīng)用WCC進(jìn)行社團(tuán)評(píng)價(jià)的方法進(jìn)行分析，提出一種包含預(yù)處理、初始劃分和劃分改進(jìn)三個(gè)階段的并行社團(tuán)挖掘算法。在劃分改進(jìn)中，由于每次社團(tuán)變化都需要計(jì)算大量的WCC提升，基于社團(tuán)的統(tǒng)計(jì)量提出一種WCC近似計(jì)算方法。大量的真實(shí)數(shù)據(jù)集實(shí)驗(yàn)表明，提出的社團(tuán)挖掘算法與相關(guān)算法相比較，不僅社團(tuán)檢測(cè)的準(zhǔn)確性更高，而且具有更好的并行可擴(kuò)展性。

關(guān)鍵詞復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘并行算法可擴(kuò)展性

0引言

近些年，復(fù)雜網(wǎng)絡(luò)分析已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的重要研究?jī)?nèi)容之一。復(fù)雜網(wǎng)絡(luò)分析可廣泛應(yīng)用于社會(huì)學(xué)、生物學(xué)、信息科學(xué)等眾多領(lǐng)域[1,2]。在對(duì)這些復(fù)雜網(wǎng)絡(luò)進(jìn)行分析的方法之中，社團(tuán)挖掘是最重要的研究?jī)?nèi)容之一。在復(fù)雜網(wǎng)絡(luò)中，社團(tuán)又被稱為聚類，是一組緊密相連的節(jié)點(diǎn)集合。社團(tuán)內(nèi)部節(jié)點(diǎn)的鏈接是緊密的，而不同社團(tuán)節(jié)點(diǎn)之間的鏈接是松散的[3]。通過(guò)社團(tuán)檢測(cè)，研究人員可以深入地了解網(wǎng)絡(luò)的結(jié)構(gòu)信息[4]，網(wǎng)絡(luò)中節(jié)點(diǎn)之間的交互關(guān)系[5]，以及節(jié)點(diǎn)在網(wǎng)絡(luò)的進(jìn)化中起到的作用[6]。

社團(tuán)檢測(cè)往往需要很大的計(jì)算量，各種社團(tuán)挖掘算法很難擴(kuò)展到含有數(shù)十億邊規(guī)模的復(fù)雜網(wǎng)絡(luò)上。在2013年，Yang等[7]給出了真實(shí)網(wǎng)絡(luò)的基準(zhǔn)測(cè)試數(shù)據(jù)集，并包含了數(shù)據(jù)集中社團(tuán)的正確劃分。在該研究中，他們測(cè)試了不同最新社團(tuán)挖掘算法[8-12]的執(zhí)行時(shí)間，通過(guò)對(duì)比發(fā)現(xiàn)這些算法很難擴(kuò)展到邊規(guī)模為數(shù)千條的復(fù)雜網(wǎng)絡(luò)。雖然BigClam[7]算法是針對(duì)大規(guī)模網(wǎng)絡(luò)設(shè)計(jì)的，但是該算法仍然不能處理含有20億條邊的Friendster數(shù)據(jù)集。此外，雖然Louvain算法[8]可以處理和Friendster數(shù)據(jù)集具有相同規(guī)模的數(shù)據(jù)集，但是社團(tuán)挖掘的質(zhì)量卻很低。

為了保持社團(tuán)挖掘結(jié)果的準(zhǔn)確性，同時(shí)提高應(yīng)對(duì)海量數(shù)據(jù)的能力，本文提出一種兩階段的社團(tuán)挖掘算法。在第一個(gè)階段，采用聚類系數(shù)作為啟發(fā)式方法獲得網(wǎng)絡(luò)的初始社團(tuán)分割。在第二階段，通過(guò)對(duì)不同社團(tuán)中的節(jié)點(diǎn)進(jìn)行移動(dòng)對(duì)第一階段得到的初始分割進(jìn)行優(yōu)化。在每次的社團(tuán)調(diào)整過(guò)程中，通過(guò)增加社團(tuán)的WCC[13]進(jìn)行節(jié)點(diǎn)的移動(dòng)。為了加速第二階段的社團(tuán)調(diào)整過(guò)程，本文提出一種新的WCC評(píng)估器。該WCC評(píng)估器類似于傳統(tǒng)的WCC評(píng)價(jià)方法，但是卻有著更高的計(jì)算效率。

1基于WCC的社團(tuán)挖掘算法

對(duì)于給定的無(wú)向無(wú)權(quán)圖G=(V,E)，本文的目標(biāo)是通過(guò)最大化WCC值來(lái)挖掘圖中的不相交社團(tuán)。本節(jié)首先描述了社團(tuán)挖掘的WCC指標(biāo)，然后基于WCC指標(biāo)提出了相應(yīng)的社團(tuán)挖掘算法，接下來(lái)分析如何應(yīng)用提出的算法對(duì)WCC值進(jìn)行估計(jì)，最后分析了算法的復(fù)雜性。

1.1WCC指標(biāo)

WCC是一種復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘評(píng)價(jià)指標(biāo)，該指標(biāo)認(rèn)為真實(shí)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)往往含有大量的三角。由于社團(tuán)是由緊密相連的節(jié)點(diǎn)組成，那么這些節(jié)點(diǎn)構(gòu)成三角的概率要相對(duì)較高，WCC應(yīng)用該特征對(duì)圖的節(jié)點(diǎn)集合劃分(即社團(tuán)劃分)進(jìn)行量化。

給定圖G=(V,E)，節(jié)點(diǎn)x以及社團(tuán)C，令t(x,C)表示x與C中節(jié)點(diǎn)構(gòu)成的三角的個(gè)數(shù)，vt(x,C)表示C中能與x構(gòu)成三角的節(jié)點(diǎn)的個(gè)數(shù)，那么將節(jié)點(diǎn)x與社團(tuán)C的凝聚水平WCC(x,C)進(jìn)行如下定義：

(1)

基于式(1)，社團(tuán)C的WCC的計(jì)算公式為：

(2)

給定集合C，WCC(C)是C中所有節(jié)點(diǎn)的WCC的值的平均值。給定圖分割P={C1,C2,…,Cn}，并且C1∩…∩Cn，那么P的WCC為該劃分中所有社團(tuán)的WCC的加權(quán)平均值，其計(jì)算公式如下：

(3)

1.2社團(tuán)挖掘算法

為了對(duì)圖G進(jìn)行劃分得到P，本文提出一種最大化WCC(P)社團(tuán)挖掘算法。該算法包含數(shù)據(jù)的預(yù)處理、初始劃分和劃分改進(jìn)三部分。

1.2.1預(yù)處理

在圖G=(V,E)的加載時(shí)，進(jìn)行如下的預(yù)處理操作：對(duì)于G中的每條邊e∈E，計(jì)算e可以構(gòu)成的不同三角的個(gè)數(shù)，并移除那些不能構(gòu)成三角的邊。

在預(yù)處理結(jié)束后，得到的圖為G′。預(yù)處理操作存在如下兩個(gè)優(yōu)點(diǎn)：(1)WCC的計(jì)算并不依賴于這些邊，因而可以提高計(jì)算效率；(2) 通過(guò)移除不能構(gòu)成三角的邊可以大幅壓縮圖的存儲(chǔ)空間，從而節(jié)省內(nèi)存開(kāi)銷。

1.2.2初始劃分

該階段對(duì)預(yù)處理得到的圖G′進(jìn)行初始劃分，其基本思想是：節(jié)點(diǎn)的聚類系數(shù)越大，那么該節(jié)點(diǎn)與鄰居節(jié)點(diǎn)形成的三角個(gè)數(shù)越多，因而該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)形成三角的概率也越大。依據(jù)式(1)，如果節(jié)點(diǎn)的聚類系數(shù)越大，那么與該節(jié)點(diǎn)同屬于一個(gè)社團(tuán)的那些鄰居節(jié)點(diǎn)的WCC概率越大。

1.2.3劃分改進(jìn)

在得到初始劃分后，需要對(duì)劃分進(jìn)行不斷改進(jìn)直到找到最優(yōu)劃分。在劃分改進(jìn)階段，使用爬山搜索策略。在每次迭代中，通過(guò)一系列變換操作(3種)，依據(jù)原有的劃分得到WCC值更高的劃分。迭代終止的條件為迭代前后劃分的WCC值變化小于閾值，或者迭代到一定的次數(shù)。

在每次迭代中，對(duì)于圖中的所有節(jié)點(diǎn)v∈V，在下列三種變換操作中選取一個(gè)最佳變換，使得變化后得到的劃分較變換之前是最優(yōu)的：

? 不進(jìn)行變換：使節(jié)點(diǎn)v處于原來(lái)的劃分C中。

? 移除：將節(jié)點(diǎn)v從原來(lái)的劃分C中移除并作為單體社團(tuán)。用WCCR(v,C)來(lái)表示移除操作得到的WCC提升值，令P={C1,…,C,…,Ck}為原來(lái)的劃分，P'={C1,…,C′,…,Ck,{v}}為變換后的劃分，對(duì)于給定的圖G=(V,E)，WCCR(v,C)的計(jì)算公式如下：

WCCR(v,C)=WCC(P′)-WCC(P)=-WCCI(v,C′)

(4)

其中C=C′∪{v}。

WCCT(v,C1,C2)=WCC(P′)-WCC(P)

(5)

在每次迭代中，由于每個(gè)節(jié)點(diǎn)之間的變換操作是相互獨(dú)立的，所以可以并行地運(yùn)行，因此可以大大提高算法的運(yùn)行效率。

1.3WCCI值估計(jì)

WCC值的精確計(jì)算需要知道目標(biāo)節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)構(gòu)成的三角個(gè)數(shù)，對(duì)于含有d個(gè)鄰居的節(jié)點(diǎn)，該操作的計(jì)算復(fù)雜度為O(d2)。由于網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)的冪率分布特征，在并行計(jì)算模式下，極少數(shù)度數(shù)大的節(jié)點(diǎn)的計(jì)算時(shí)間往往影響著整個(gè)算法的運(yùn)行效率。此外，在每次迭代過(guò)程中都需要計(jì)算WCC的提高值WCCI，因此WCCI的計(jì)算性能決定著算法的整體效率。為了加速WCCI的計(jì)算，本文提出了一種近似計(jì)算方法，該方法的基本思想如圖1所示。

圖1　WCCI的計(jì)算示意圖

當(dāng)節(jié)點(diǎn)v被加入到社團(tuán)C時(shí)，WCC值的提高值為WCCI。對(duì)于節(jié)點(diǎn)v，僅僅考慮C中與v相連的節(jié)點(diǎn)的個(gè)數(shù)din。對(duì)于每個(gè)社團(tuán)C，記錄如下的統(tǒng)計(jì)量：節(jié)點(diǎn)個(gè)數(shù)r，邊的密度δ，社團(tuán)邊界的邊的個(gè)數(shù)b。同時(shí)，保存著圖G的聚類系數(shù)ω(常數(shù))?；谏鲜鼋y(tǒng)計(jì)量，應(yīng)用如下公式得到WCCI的估計(jì)值：

(6)

其中θ1、θ2和θ3分別為相應(yīng)變量的系數(shù)，并且和為1。

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

本節(jié)通過(guò)大量的真實(shí)數(shù)據(jù)集實(shí)驗(yàn)對(duì)算法的性能進(jìn)行了評(píng)估。

2.1數(shù)據(jù)集與性能指標(biāo)

本文的實(shí)驗(yàn)采用Stanford提供的公開(kāi)網(wǎng)絡(luò)數(shù)據(jù)集SNAP(http://snap.stanford.edu)，其中包括Amazon、Dblp、Youtube、LiveJournal、Orkut和Friendster六個(gè)網(wǎng)絡(luò)數(shù)據(jù)集。這些數(shù)據(jù)集的基本統(tǒng)計(jì)信息如表1所示。

表1　數(shù)據(jù)集基本信息

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

在實(shí)驗(yàn)中，我們將本文提出的可擴(kuò)展的社團(tuán)檢測(cè)算法記為scd，并將該算法與walktrap[8]、louvain[9]、oslom[10]、infoman[11]和bigclam[12]五種社團(tuán)挖掘算法進(jìn)行了對(duì)比。

首先，應(yīng)用六種社團(tuán)挖掘算法對(duì)上述的6個(gè)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行社團(tuán)檢測(cè)，并對(duì)比了社團(tuán)挖掘結(jié)果的準(zhǔn)確性。圖2和圖3分別為六種算法在不同數(shù)據(jù)集上的F1值和NMI對(duì)比圖。在這兩個(gè)柱狀圖中，如果數(shù)據(jù)集對(duì)應(yīng)的柱為空，說(shuō)明相應(yīng)算法的F1值或NMI值幾乎為0。從這兩幅圖中可以看出，除了walktrap和louvain兩種算法在Amazon數(shù)據(jù)集上的NMI值大于scd算法外，scd算法在其他數(shù)據(jù)集上的NMI和F1值都高于其他算法。這說(shuō)明本文提出的社團(tuán)挖掘算法對(duì)于不同類型的網(wǎng)絡(luò)都具有更好的社團(tuán)檢測(cè)性能。

圖2　算法的F1值對(duì)比

圖3　算法的NMI對(duì)比

其次，通過(guò)實(shí)驗(yàn)對(duì)比了六種算法在這些數(shù)據(jù)集上的執(zhí)行效率，實(shí)驗(yàn)結(jié)果如圖4所示。在該組實(shí)驗(yàn)中，我們省略了那些準(zhǔn)確性幾乎為0的算法，令相應(yīng)的柱值為空。從該圖可以看出本文提出的算法的執(zhí)行時(shí)間在6個(gè)數(shù)據(jù)集上的執(zhí)行時(shí)間都是最短的，而louvain算法次之。我們對(duì)算法進(jìn)行并行化，分析了scd算法在不同數(shù)量線程下的運(yùn)行效率。在圖5中，橫軸表示算法的線程數(shù)量，縱軸為算法的運(yùn)行時(shí)間，由于算法在單線程下的運(yùn)行時(shí)間大于1秒，為了更好地對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行展示并在1秒處進(jìn)行了截?cái)?。從圖5可以看出，由于對(duì)scd算法進(jìn)行了并行化，因此算法的執(zhí)行時(shí)間明顯減少了，并且在LiveJournal、Orkut和Friendster三個(gè)數(shù)據(jù)集上的并行效果要優(yōu)于其他三個(gè)數(shù)據(jù)集。

圖4　算法的執(zhí)行效率對(duì)比

圖5　scd算法的執(zhí)行時(shí)間評(píng)估

最后，我們進(jìn)一步分析了scd算法的并行化性能。圖6為scd算法在不同算法下的運(yùn)行時(shí)間，橫軸表示網(wǎng)絡(luò)中邊的規(guī)模，縱軸為scd算法在相應(yīng)網(wǎng)絡(luò)中進(jìn)行社團(tuán)挖掘所需的執(zhí)行時(shí)間。圖6表明當(dāng)網(wǎng)絡(luò)中邊的數(shù)量不斷增加時(shí)，scd算法的執(zhí)行時(shí)間近似呈線性增長(zhǎng)，因而可以認(rèn)定scd算法具有更好的并行化性能，其執(zhí)行時(shí)間隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)具有很好的可擴(kuò)展性。

圖6　scd算法的可擴(kuò)展性分析

3結(jié)語(yǔ)

社團(tuán)挖掘是復(fù)雜網(wǎng)絡(luò)的重要研究?jī)?nèi)容之一。通過(guò)社團(tuán)檢測(cè)，可以深入了解網(wǎng)絡(luò)的結(jié)構(gòu)信息，網(wǎng)絡(luò)中節(jié)點(diǎn)之間的交互關(guān)系，以及節(jié)點(diǎn)在網(wǎng)絡(luò)的進(jìn)化中起到的作用。為了減小社團(tuán)變化帶來(lái)的WCC計(jì)算量，本文提出了一種并行可擴(kuò)展的社團(tuán)挖掘算法。對(duì)應(yīng)用WCC進(jìn)行社團(tuán)評(píng)價(jià)的方法進(jìn)行了分析，提出了一種包含預(yù)處理、初始劃分和劃分改進(jìn)三個(gè)階段的并行社團(tuán)挖掘算法。在劃分改進(jìn)中，由于每次社團(tuán)變化都需要計(jì)算大量的WCC提升，本文基于社團(tuán)的統(tǒng)計(jì)量提出一種WCC近似計(jì)算方法。大量的真實(shí)數(shù)據(jù)集實(shí)驗(yàn)表明，本文提出的社團(tuán)挖掘算法與相關(guān)算法相比較，不僅社團(tuán)檢測(cè)的準(zhǔn)確性更高，而且具有更好的并行可擴(kuò)展性。

參考文獻(xiàn)

[1] 汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].清華大學(xué)出版社有限公司,2006.

[2]BoccalettiS,LatoraV,MorenoY,etal.Complexnetworks:Structureanddynamics[J].Physicsreports,2006,424(4):175-308.

[3] 駱志剛,丁凡,蔣曉舟,等.復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J].國(guó)防科技大學(xué)學(xué)報(bào),2011,33(1):47-52.

[4] 汪小帆.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)分析算法研究綜述[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2005,2(3):1-12.

[5] 王林,戴冠中.基于復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的論壇熱點(diǎn)主題發(fā)現(xiàn)[J].計(jì)算機(jī)工程,2008,34(11):214-216.

[6] 呂金虎.復(fù)雜網(wǎng)絡(luò)的同步:理論,方法,應(yīng)用與展望[J].力學(xué)進(jìn)展,2008,38(6):713-722.

[7]YangJ,LeskovecJ.Overlappingcommunitydetectionatscale:anonnegativematrixfactorizationapproach[C]//ProceedingsofthesixthACMinternationalconferenceonWebsearchanddatamining.ACM,2013:587-596.

[8]BlondelVD,GuillaumeJL,LambiotteR,etal.Fastunfoldingofcommunitiesinlargenetworks[J].JournalofStatisticalMechanics:TheoryandExperiment,2008,28(10):100-108.

[9]AhnYY,BagrowJP,LehmannS.Linkcommunitiesrevealmultiscalecomplexityinnetworks[J].Nature,2010,466(7307):761-764.

[10]BagrowJP.Communitiesandbottlenecks:Treesandtreelikenetworkshavehighmodularity[J].PhysicalReviewE,2012,85(6):66-78.

[11]FortunatoS,BarthelemyM.Resolutionlimitincommunitydetection[J].ProceedingsoftheNationalAcademyofSciences,2007,104(1):36-41.

[12]LancichinettiA,FortunatoS.Communitydetectionalgorithms:acomparativeanalysis[J].PhysicalreviewE,2009,80(5):056117.

[13]Prat-PérezA,Dominguez-SalD,BrunatJM,etal.Shapingcommunitiesoutoftriangles[C]//Proceedingsofthe21stACMinternationalconferenceonInformationandknowledgemanagement.ACM,2012:1677-1681.

[14]LancichinettiA,FortunatoS,KertészJ.Detectingtheoverlappingandhierarchicalcommunitystructureincomplexnetworks[J].NewJournalofPhysics,2009,11(3):33-45.

WCC-BASED PARALLEL AND SCALABLE COMMUNITY MINING ALGORITHMINCOMPLEXNETWORKS

Yasen·Aizezi1Li Weiping2Guo Wenqiang3

1(Department of Information Security and Engineering,Xinjiang Police College,Urumqi 830013,Xinjiang,China)2(Department of Police Technology,Railway Police College,Zhengzhou 450053,Henan,China)3(School of Computer Science and Engineering,Xinjiang University of Finance and Economic, Urumqi 830013,Xinjiang,China)

AbstractWeighted community clustering (WCC) evaluates the performance of community mining algorithms according to triangles number of a community in complex networks. In primitive WCC algorithm it has the need to compute WCC scores for all community changes in each iteration, therefore the computation burden is very heavy. In order to minimise WCC computation brought about by communities change, this paper proposes a parallel and scalable community mining algorithm. We analysed the methods of community evaluation using WCC, and proposed a parallel community mining algorithm including three stages of preprocessing, initial partitioning and partition refinement. During the process of partition refinement, since every change in community needs much computation for WCC improvements, so we proposed a WCC approximated computation algorithm based on the statistics of community. Massive experiments on real datasets show that, the proposed community mining algorithm is more accurate and has better scalability than related works.

KeywordsComplex networksCommunity miningParallel algorithmScalability

收稿日期：2014-12-02。國(guó)家自然科學(xué)基金項(xiàng)目(61163066，6090 2074)；新疆維吾爾自治區(qū)高?？蒲杏?jì)劃科學(xué)研究重點(diǎn)項(xiàng)目(XJEDU 2013134)；國(guó)家社會(huì)科學(xué)基金項(xiàng)目(13CFX055)；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(14A520011)。亞森·艾則孜，教授，主研領(lǐng)域：信息安全，自然語(yǔ)言處理，信息檢索。李衛(wèi)平，副教授。郭文強(qiáng)，教授。

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.009