基于時間加權的重疊社區(qū)檢測算法研究

李慧 馬小平 張舒 施珺 李存華 仲兆滿

社區(qū)結構是復雜網(wǎng)絡的重要特性,在網(wǎng)絡中發(fā)現(xiàn)社區(qū)就是把相似節(jié)點劃分為一個集合,使得集合內(nèi)節(jié)點之間的相互作用比它們與集合外節(jié)點的相互作用更強,即同一社區(qū)內(nèi)部節(jié)點間的鏈接較為稠密,不同社區(qū)之間的鏈接較為稀疏[1].但是社會化網(wǎng)絡中用戶的多重社會屬性導致用戶可以同時從屬于多個社區(qū),因此基于可重疊聚類的社區(qū)發(fā)現(xiàn)算法效果更佳.發(fā)現(xiàn)高質(zhì)量的社區(qū)有助于理解真實的復雜網(wǎng)絡,尤其是動態(tài)地分析社區(qū)重疊結構,對社區(qū)管理和演化具有重要意義[2?4].

在傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法中,網(wǎng)絡可以作為靜態(tài)拓撲圖處理而不用考慮節(jié)點間的信息交互因素,在微博等社交網(wǎng)絡中已經(jīng)不再適用.在微博及其應用所構成的社交網(wǎng)絡中頻繁地使用不同節(jié)點間的信息交互;拓撲結構僅代表用戶之間交互的可能性,而實際交互的程度則由節(jié)點之間的信息流動情況決定.這種社區(qū)劃分方法由于僅僅依賴拓撲結構,卻忽略了社交網(wǎng)絡中的信息流動,因此表現(xiàn)出明顯的局限性,這已經(jīng)與現(xiàn)代社交網(wǎng)絡的特征相背離,除此之外,社區(qū)劃分結果在這種體系下也無法得到較高的準確性.

本文的重疊社區(qū)檢測算法是針對傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法在解決社交網(wǎng)絡中社區(qū)劃分時所面臨的問題所提出的,稱為基于時間加權關聯(lián)規(guī)則的時域重疊社區(qū)檢測算法(Time-weighted overlapping community detection,TWOCD).TWOCD算法的主要創(chuàng)新點在于重疊社區(qū)檢測時充分考慮了用戶興趣的時間因素,重疊社區(qū)檢測時充分考慮了用戶興趣的時間因素,根據(jù)帶有時間加權鏈接的用戶–用戶圖實現(xiàn)重疊社區(qū)檢測.

本文第1節(jié)介紹了重疊社區(qū)檢測的相關工作,并描述了一些主流的重疊社區(qū)發(fā)現(xiàn)算法;第2節(jié)具體地闡述了重疊社區(qū)的檢測算法及社區(qū)合并方案;第3節(jié)是算法性能驗證實驗;第4節(jié)是我們的工作的總結以及對未來研究工作的展望.

1 相關工作

目前已出現(xiàn)5類重疊社區(qū)發(fā)現(xiàn)算法,即派系過濾算法、局部擴展社區(qū)發(fā)現(xiàn)算法、模糊重疊社區(qū)發(fā)現(xiàn)算法、邊社區(qū)發(fā)現(xiàn)算法、標簽傳播算法.

1.1 派系過濾算法

2005年,Gergely等提出了派系過濾(Clique percolation method,CPM)算法[5].其核心思想是發(fā)現(xiàn)基于k極大團的重疊社區(qū).由k個節(jié)點構成的完全連通子圖稱為k極大團.Gergely 等引入一種新的概念,即將具有k ?1個相同節(jié)點的兩個k極大團稱為鄰接的k極大團.派系過濾算法(Cluster porcdation method,CPM)旨在尋找鄰接的k極大團.由于極大團的內(nèi)部節(jié)點之間的全連通性可以形成一種內(nèi)部緊密而外部稀疏的社區(qū)結構,這是一種理想的社區(qū)結構.鄰接的k極大團就是派系過濾算法(CPM)尋找的重疊社區(qū)結構.但是CPM算法具有只能夠發(fā)現(xiàn)基于k極大團的重疊社區(qū)結構的缺陷.Farkas等對CPM算法進行改進,將其擴展應用到有權圖上,提出子圖密度的概念實現(xiàn)對k極大團的搜索[6].2015年,Zhang 等提出一種新的重疊社區(qū)發(fā)現(xiàn)方法,稱為MOHCC算法[7].該算法在尋找圖中極大團的基礎上結合Wang 提出的Coupling Strength[8]作為目標函數(shù)進行極大團的合并,從而得到最佳的層次劃分.

1.2 局部擴展社區(qū)發(fā)現(xiàn)算法

基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法,通常從不同種子節(jié)點開始,根據(jù)設定的某優(yōu)化函數(shù),探索種子所在的局部社區(qū)結構,各個局部社區(qū)結構融合形成網(wǎng)絡整體的重疊社區(qū)結構[9].代表算法有LFM算法[10]和GCE算法[11].LFM算法的基本思想是每次在網(wǎng)絡中隨機選取一個尚無社區(qū)標簽的節(jié)點作為種子,然后采用一種貪心的策略將種子擴展為一個局部自然社區(qū),直到網(wǎng)絡中所有節(jié)點都有社區(qū)標簽為止.在局部擴展的過程中,LFM算法通過不斷對當前子圖增加或者刪除節(jié)點使得適應度函數(shù)值達到局部最大值.GCE 算法在整個算法執(zhí)行的初始階段,在網(wǎng)絡中找出所有節(jié)點規(guī)模不小于k的最大團(全連通子圖)作為種子;然后同樣采用貪心的策略對種子進行擴展得到局部自然社區(qū),其設定的適應度函數(shù)與LFM算法相同.該算法在擴展的每一次迭代中僅添加使得適應度函數(shù)最大的節(jié)點,得到新的社區(qū)之后重復執(zhí)行直到適應度函數(shù)不再增大,然后將此時的社區(qū)同之前已檢測到的所有社區(qū)計算二者的距離,根據(jù)設定的閾值決定是否保留該社區(qū).

2011年,Lancichinetti 等又提出了OSLOM算法[12],該算法提出了一種帶有隨機擾動的用于表達社區(qū)的統(tǒng)計學重要性局部優(yōu)化適應度函數(shù).根據(jù)該適應度函數(shù)尋找重要的社區(qū),直至收斂.2017 年,Yang 等[13]提出了一種種子節(jié)點選擇策略,并基于節(jié)點影響力和模塊度定義目標函數(shù),從而實現(xiàn)社區(qū)的初始化和社區(qū)優(yōu)化.Su等[14]根據(jù)節(jié)點的中心性從網(wǎng)絡中選取種子節(jié)點,并計算其與鄰居節(jié)點的局部簇系數(shù)來決定是否和鄰居節(jié)點進行合并,從而實現(xiàn)社區(qū)結構的發(fā)現(xiàn).

1.3 模糊重疊社區(qū)發(fā)現(xiàn)算法

模糊重疊社區(qū)發(fā)現(xiàn)算法通過確定節(jié)點與社區(qū)之間的隸屬度來確定節(jié)點與社區(qū)的從屬關系,為重疊社區(qū)發(fā)現(xiàn)中的另一類重要算法.2011年Gregory針對社交網(wǎng)絡的社區(qū)檢測首次提出了“模糊重疊劃分(Fuzzy overlapping partition)”的概念[15].模糊重疊社區(qū)檢測與傳統(tǒng)離散重疊社區(qū)檢測的區(qū)別在于:允許重疊節(jié)點對所屬社區(qū)具有不完全且不一致的隸屬關系,利用[0,1]連續(xù)區(qū)間內(nèi)分布的模糊隸屬度量化重疊節(jié)點對不同社區(qū)的相對隸屬程度.

2015年,Eustace等的鄰居比例矩陣模型結合非負矩陣分解算法,使用Perron clusters進行網(wǎng)絡中的社區(qū)數(shù)目的求解,并將其應用到重疊社區(qū)發(fā)現(xiàn)中[16],實現(xiàn)了將網(wǎng)絡中低于平均鄰居節(jié)點數(shù)目的節(jié)點之間關系的過濾功能.文獻[17]提出了一種在社交網(wǎng)絡下基于模糊自適應推理理論的重疊社區(qū)發(fā)現(xiàn)算法,該算法包含比較和預測兩個階段,通過兩個階段的循環(huán)迭代較好地解決社區(qū)發(fā)現(xiàn)問題.文獻[18]提出了一種模糊模塊度最大化方法,利用模塊度優(yōu)化模型確定節(jié)點的最優(yōu)隸屬度.此外,還有一些研究以非負矩陣分解為工具,提出一些節(jié)點隸屬度的計算方法[19?20].

1.4 邊社區(qū)發(fā)現(xiàn)算法

重疊社區(qū)發(fā)現(xiàn)的焦點問題可以歸結到節(jié)點的社區(qū)結構研究上,忽略了邊對于重疊社區(qū)發(fā)現(xiàn)問題研究的重要性.邊聚類算法的核心思想是在將邊轉換為聚類算法能夠處理的模型的基礎上,利用聚類算法對邊進行聚類,從而實現(xiàn)邊社區(qū)的發(fā)現(xiàn).相繼產(chǎn)生了一些邊聚類算法中的代表性算法,如Ahn等[21]提出的經(jīng)典的邊聚類(Link clustering,LC)算法的核心思想是將Jaccard方法應用到邊的相似度計算中,從而得到邊的相似度矩陣.Shi等在經(jīng)典的邊聚類算法基礎上又提出了將遺傳算法應用到邊聚類的方法,稱為GaoCD算法[22],該算法將分割密度作為目標函數(shù),基于一種新的基因表達方法實現(xiàn)邊社區(qū)到節(jié)點社區(qū)的轉換.2014年,Lim等提出的LinkScan 算法[23]用于邊社區(qū)發(fā)現(xiàn).Li等[24]提出了一種以線圖模型為基礎的加權模型,對模塊密度函數(shù)進行優(yōu)化識別,設計一種新的基因表示模型將鏈路社區(qū)映射為節(jié)點社區(qū),從而實現(xiàn)重疊社區(qū)的檢測.目前邊社區(qū)發(fā)現(xiàn)算法已經(jīng)成為一類重要的重疊社區(qū)發(fā)現(xiàn)算法.

1.5 標簽傳播算法

標簽傳播算法的核心思想為節(jié)點通過與鄰域節(jié)點之間交互社區(qū)歸屬標簽信息,更新節(jié)點自身的社區(qū)歸屬標簽,使網(wǎng)絡中所有節(jié)點對應的標簽分布達到動態(tài)平衡,具有相同標簽的節(jié)點構成社區(qū),而具有多個社區(qū)標簽的節(jié)點為重疊節(jié)點,由此得到重疊社區(qū)結構.這類方法的典型代表是基于多標簽的COPRA算法[25]和基于Speaker-listener模型的SLPA算法[26].COPRA是Gregory 于2010年提出的首個基于標簽傳播的模糊重疊社區(qū)檢測算法,節(jié)點標簽對中不僅含有社區(qū)名稱,而且包含節(jié)點對該社區(qū)的歸屬系數(shù).SLPA算法是由Xie等于2011年提出的,該算法為每個節(jié)點提供存儲信息(標簽)的記憶空間,將從記憶空間中獲取標簽的概率作為節(jié)點隸屬度,無需社區(qū)數(shù)目等先驗信息.Gaiter等[27]于2015年提出了一種SpeakEasy聚類方法,根據(jù)節(jié)點的局部連接性和網(wǎng)絡全局信息將節(jié)點加入社區(qū),該方法在社區(qū)結構穩(wěn)定性上給出了定量分析與評價.

上述介紹的5種方法是一些經(jīng)典的重疊社區(qū)發(fā)現(xiàn)算法,每種算法適用于不同的場合.本文所提出的算法是對邊社區(qū)發(fā)現(xiàn)算法的擴充,通過加入用戶相似度和社區(qū)中心點提升重疊社區(qū)發(fā)現(xiàn)算法的準確率.

2 重疊社區(qū)的生成

已知一組用戶和一組對象,這些用戶和對象間的交互關系可表示為一個用戶–對象關系圖,該圖中的用戶節(jié)點只與其感興趣的對象相連.然后,可將用戶–對象關系圖轉化為用戶–用戶關系圖,且用戶–用戶關系圖中兩個用戶間的鏈接表示這兩個用戶共同喜歡某些對象,且鏈接權重表示這些共同對象的數(shù)量.考慮到用戶興趣會隨著時間的變化而變化,我們假設兩個用戶發(fā)生交互的時間越近,則這兩個用戶具有共同興趣的概率越大,越會在用戶–用戶圖中形成相應的時間加權鏈接.

2.1 利用時間加權鏈接構建用戶–用戶圖

根據(jù)數(shù)據(jù)的時間標簽,將訓練數(shù)據(jù)集分成不同時間段的數(shù)據(jù)子集.假設第i個用戶在第t段時間對第j個對象打分,其中i=1,···,n.j=1,···,m.t∈{1,···,TL},用n表示用戶數(shù)量,m表示對象數(shù)量,TL表示訓練數(shù)據(jù)集中所有交互的總時間.如果沒有交互信息或者打分低于預期閾值,則將t設置為0.

于是,利用如下類似于遺忘曲線的函數(shù),將交互情況表示為時間加權用戶–對象矩陣G=[gij]n×m:

其中,θ1>0表示預先指定的實數(shù),用于反映交互的時間效應.θ1數(shù)值越大,時間對用戶和對象間交互的影響越少.例如,當θ1→+∞時,gij=1,時間加權用戶–對象圖轉化為沒有考慮時間效應的傳統(tǒng)用戶評分矩陣.然后,對具有相同對象喜好的用戶間添加鏈路,將用戶–對象圖轉化為時間加權用戶–用戶圖.從矩陣角度講,可將用戶–用戶圖描述為用戶–用戶矩陣.

因此,用戶間的鏈接反映了用戶興趣的相似度,且用戶興趣的相似度主要取決于用戶共同喜歡的對象數(shù)量以及喜歡這些對象的時間.矩陣U中的元素uil表示第i個和第l個用戶間的興趣相似度,且i=1,···,n,l=1,···,n.但是這個相似度只能反映節(jié)點的局部相似性,要想真實反映網(wǎng)絡中節(jié)點間的相似度必須從全局角度計算用戶的全局相似度.

2.2 用戶全局相似度的計算

網(wǎng)絡中節(jié)點間的相似度計算大多基于節(jié)點的局部信息.如果兩個節(jié)點共享更多的鄰居,它們就會被認為更加相似.但是,該方法沒有考慮到網(wǎng)絡中節(jié)點的全局重要性.在本節(jié)中,我們?nèi)诤狭司W(wǎng)絡的全局結構來計算用戶間全局相似度.首先基于原始PageRank 算法定義節(jié)點影響度,以測量網(wǎng)絡中節(jié)點的影響程度.節(jié)點的影響程度越大,節(jié)點在網(wǎng)絡中的全局重要性就越大.

2.2.1 節(jié)點的影響度

我們使用PageRank 算法[28]來計算網(wǎng)絡中的節(jié)點影響程度.PageRank 算法的主要思想是網(wǎng)頁中節(jié)點的PageRank值等于指向它的所有節(jié)點PageRank 值的總和.同樣,網(wǎng)絡中節(jié)點的影響度是指向它的所有節(jié)點的影響度總和.節(jié)點i影響度Inf(i)計算方法如下:

其中,Inf(i)代表節(jié)點l的影響度,即網(wǎng)絡中節(jié)點l的度數(shù).F(i)是節(jié)點i的一個鄰居集合,N(l)是節(jié)點l的鄰居數(shù)量,N是圖中節(jié)點的總數(shù).為了便于計算,在方程中加入常數(shù)c,c ∈(0,1)為阻尼因子,一般設為0.85.阻尼因子的取值是基于原PageRank算法的經(jīng)驗分析.

2.2.2 用戶全局相似度

為了計算用戶間的全局相似度,我們將由式(2)計算出的局部相似度與節(jié)點的結構聚合度相結合,計算用戶全局相似度.在網(wǎng)絡中,可以用公共鄰居的個數(shù)來計算兩個節(jié)點的結構聚合度.兩個節(jié)點共享的公共鄰居越多,它們就越相似.如果一個節(jié)點具有較大的影響力,那么它將與其他節(jié)點更加聚集.節(jié)點結構聚合度(SCD)定義為:

節(jié)點的全局相似度考慮了基于局部相似度uil與節(jié)點的結構聚合度SCD,利用加權和將這兩個因素相結合,即可得到用戶全局相似度Sim,其定義如下:

其中,參數(shù)α∈[0,1]是根據(jù)實際情況設置的權重因子,用以控制兩個因素的比例大小,具體的取值在實驗部分給出.

2.3 社區(qū)中心點的計算

在進行重疊檢測之前,首先要選擇一個初始節(jié)點,最簡單的方法是根據(jù)節(jié)點度排序選擇節(jié)點度最大的節(jié)點為初始節(jié)點,但這種方法并不可取,因為節(jié)點度最大的節(jié)點并不能保證是最重要的.在一個網(wǎng)絡社區(qū)中,其中心節(jié)點是社區(qū)的核心,應該與其他節(jié)點有著較為密切的聯(lián)接,從而中心節(jié)點通常會具有較高的度.同時,由社區(qū)中心節(jié)點關聯(lián)的節(jié)點間應該具有較高的相似性.本節(jié)通過計算節(jié)點的內(nèi)聚度和分離度作為度量節(jié)點對社區(qū)結構影響力的重要性指標,從而提出了一種社區(qū)中心點的選取方法.

定義1.節(jié)點內(nèi)聚度.網(wǎng)絡中節(jié)點i的內(nèi)聚度是指該節(jié)點的時間加權用戶–用戶矩陣及其與鄰居節(jié)點的最大全局相似度之積,形式化表示為:

由上式可知節(jié)點i的內(nèi)聚度Ii同時考慮了節(jié)點的連接數(shù)量和全局相似度兩個因素,節(jié)點的內(nèi)聚度越高,表示該節(jié)點對社區(qū)內(nèi)其他節(jié)點的聚合能力會越強.

由于網(wǎng)絡社區(qū)的外部連接通常是相對稀疏的,因此社區(qū)中心節(jié)點與其他內(nèi)聚度較高的節(jié)點應該具有較低的相似性.這一特征可以用節(jié)點的分離度來表示.

定義2.節(jié)點分離度.網(wǎng)絡中節(jié)點i的分離度是內(nèi)聚度高于i的節(jié)點與該節(jié)點之間的最大全局相似度的倒數(shù),形式化表示為:

其中,Oi為節(jié)點i的分離度,其取值越大表明節(jié)點i與內(nèi)聚度更大的節(jié)點之間具有較低的相似性.

社區(qū)的中心點是對社區(qū)結構具有最大影響力、與內(nèi)部具有較高的內(nèi)聚度以及與其他內(nèi)聚度較高的節(jié)間具有較低的相似性的節(jié)點.因此,可以用節(jié)點的中心度來表示其影響力.

定義3.節(jié)點中心度.網(wǎng)絡中節(jié)點i的中心度是該節(jié)點的內(nèi)聚度與分離度的乘積,形式化表示為:

其中,Ri為節(jié)點i的中心度,節(jié)點的中心度越高,則該節(jié)點成為社區(qū)中心的可能性就越大.

2.4 重疊社區(qū)檢測

我們檢測時間加權用戶–用戶圖中的重疊社區(qū)之前,首先根據(jù)節(jié)點的中心度排序來選擇初始節(jié)點.其次,我們規(guī)定社區(qū)中的節(jié)點停止增長了才能進行節(jié)點刪除操作.再次,為了避免死循環(huán),我們規(guī)定初始節(jié)點不得刪除.利用節(jié)點中心度的概念來衡量節(jié)點的重要性,選擇節(jié)點中心度最大的節(jié)點為初始節(jié)點,通過使如下效用函數(shù)最大化便可實現(xiàn)社區(qū)檢測:

重疊社區(qū)的檢測步驟如下所示.

算法1.Overlapping community detection algorithm

步驟1.選擇整個節(jié)點中心度最高的節(jié)點A作為起始節(jié)點;

步驟2.通過如下步驟檢測出這個節(jié)點的自然社區(qū):

1)利用被選節(jié)點對社區(qū)C初始化,將社區(qū)的初始適應度設置為0;

2)確定社區(qū)C有哪些相鄰節(jié)點沒有包含在C中但與C中節(jié)點具有直接聯(lián)系;

3)確定每個相鄰節(jié)點對于社區(qū)C的適應度,即存在和不存在相鄰節(jié)點時社區(qū)C的適應度變化.從所有相鄰節(jié)點中選擇正值適應度最大的節(jié)點納入社區(qū)C,然后再次計算社區(qū)的適應度.

4)重復步驟2)和3),直到?jīng)]有相鄰節(jié)點對社區(qū)C的適應度為正;

5)計算C中各個節(jié)點的適應度,即包含和不包含該節(jié)點時社區(qū)C的適應度變化.刪除與社區(qū)C的適應度為負且數(shù)值最大的節(jié)點(該社區(qū)的起始節(jié)點例外),然后再次計算社區(qū)的適應度;

6)重復步驟5),直到社區(qū)C中沒有節(jié)點的適應度為負.

步驟3.如果存在部分節(jié)點未被分配到任何當前社區(qū),則從這些節(jié)點中選擇節(jié)點中心度最高的節(jié)點,然后跳到步驟2);否則,輸出最終社區(qū).

2.5 社區(qū)融合

如果利用社區(qū)檢測算法獲得的兩個社區(qū)中包含了太多重疊節(jié)點,則應該將這些節(jié)點融入到一個社區(qū)中.通過計算重疊比例可以確定這兩個社區(qū)是否應該融合.當兩個社區(qū)重疊節(jié)點的比例均較高時,則可將這兩個社區(qū)進行合并.

其中,Cp和Cq表示第p個和第q個重疊社區(qū)的用戶集合,min(|Cp|,|Cq|)表示社區(qū)p或q中節(jié)點最少的某個社區(qū)的節(jié)點數(shù)目.|·|表示社區(qū)集或節(jié)點集中的節(jié)點數(shù)量,設置融合閾值β ∈[0,1].如果δpq >β,則將兩個社區(qū)進行合并.融合閾值具體的取值在實驗部分給出.

3 實驗與性能分析

3.1 實驗數(shù)據(jù)集

1)人工網(wǎng)絡數(shù)據(jù)集

LFR 基準程序是近年來廣泛使用的人工基準網(wǎng)絡生成工具,因為其生成的網(wǎng)絡可以很好地表示出節(jié)點度和社區(qū)規(guī)模分布的異質(zhì)性.通過設置不同的參數(shù)可以生成不同的網(wǎng)絡結構,表1給出了LFR 基準網(wǎng)絡生成參數(shù)的說明,表2給出了根據(jù)LFR 中參數(shù)的不同取值所生成的三個數(shù)據(jù)集信息,分別記為S1,S2和S3.

表1 LFR 基準網(wǎng)絡生成參數(shù)說明Table 1 Parameter setting of LFR benchmark network generation

表2 人工網(wǎng)絡數(shù)據(jù)集Table 2 Artificial network datasets

2)真實網(wǎng)絡數(shù)據(jù)集

為了檢測算法在真實網(wǎng)絡上的性能,選用6個真實網(wǎng)絡數(shù)據(jù)集對本章提出算法進行驗證,包括Zachary空手道俱樂部成員關系網(wǎng)絡(Karate)、海豚社會網(wǎng)絡(Dolphins)、美國政治書網(wǎng)絡(Polbooks)和美國大學足球網(wǎng)絡(Football)等.本文選取了兩個具有代表性的真實數(shù)據(jù)集:Polblogs和DBLP.數(shù)據(jù)集如表3所示.

3.2 實驗方法與評價指標

為了對比本文提出的TWOCD算法性能,選取目前重疊社區(qū)發(fā)現(xiàn)的主流算法CPM[5]、COPRA[25]、LFM[10]對比實驗,對比實驗將在不同的人工數(shù)據(jù)集和真實數(shù)據(jù)集上進行驗證,從而對TWOCD算法的性能進行分析.對比算法的簡介如下:

CPM:由Palla 等提出的基于派系過濾的算法,基于K極大團發(fā)現(xiàn)重疊社區(qū).

LFM:由Lancichinetti等提出的一種基于局部擴展的重疊社區(qū)發(fā)現(xiàn)算法,通過局部適應度函數(shù)決定是否加入社區(qū).

COPRA:由Gregory等提出的一種基于標簽傳播的重疊社區(qū)發(fā)現(xiàn)算法,為每個節(jié)點保留了多個標簽,根據(jù)標簽進行重疊社區(qū)的發(fā)現(xiàn).

表3 真實數(shù)據(jù)集Table 3 Real datasets

本節(jié)介紹算法性能評估指標,包括標準化互信息(NMI)和模塊度(Q).當時效網(wǎng)絡的社區(qū)結構真實情況已知時,采用NMI和錯誤率指標;否則,使用模塊度指標.

標準化互信息(NMI)指標定義為:

其中,n表示網(wǎng)絡節(jié)點的數(shù)量,K r和K s分別表示真實網(wǎng)絡結構的社區(qū)數(shù)量及本文算法獲得的社區(qū)數(shù)量;和nij分別表示真實網(wǎng)絡結構第i個社區(qū)的節(jié)點數(shù)量,本文算法獲得的第j個社區(qū)的節(jié)點數(shù)量,以及第i和第j個社區(qū)的共同節(jié)點數(shù)量;NMI的數(shù)值范圍在0～1之間.數(shù)值越接近于1,表明社區(qū)發(fā)現(xiàn)結果越接近真實值.

模塊度(Q)定義為:

其中,m表示網(wǎng)絡中邊緣總量,Aij表示網(wǎng)絡鄰接矩陣的元素,di表示節(jié)點i的度,Ci表示節(jié)點i所隸屬的社區(qū).如果節(jié)點i和第j屬于同一社區(qū),則δ(Ci,Cj)=1;否則,δ(Ci,Cj)=0.總體來說,Q值越接近1,社區(qū)劃分的結果越好.

3.3 參數(shù)α和β 取值的驗證實驗

參數(shù)α是用戶全局相似度計算的權重因子,用以控制局部相似度與結構聚合度在全局相似度計算時的比例大小.為分析參數(shù)α對本文算法社區(qū)發(fā)現(xiàn)結果產(chǎn)生的影響,我們在社區(qū)取不同數(shù)量下計算參數(shù)α的取值對社區(qū)發(fā)現(xiàn)結果的Q值影響情況.圖1顯示Polblogs數(shù)據(jù)集中各種α值對Q值的影響值.通過比較圖1中K取不同值時Q值的結果,可以看到當K=2時社會結構最優(yōu).這是由于Polblogs數(shù)據(jù)集中的包括了保守主義和自由主義兩類不同政治傾向的節(jié)點,因此該數(shù)據(jù)集很自然地分為兩個社區(qū).這也說明我們的社區(qū)發(fā)現(xiàn)算法結果與實際情況一致.

圖2顯示了各種α值對DBLP數(shù)據(jù)集Q值的影響情況.與政治觀點是社區(qū)重要特征的Polblogs數(shù)據(jù)不同,DBLP社區(qū)考慮了合作者關系.因此,由圖2可以看出,通過重復實驗,當K=50時,Q的平均值最佳.由圖1和圖2的驗證結果可知,當參數(shù)α=0.4時,社區(qū)模塊度Q達到了最佳值,因此本算法中的參數(shù)α最終取值為0.4.

圖1 Polblogs數(shù)據(jù)集中參數(shù)α對Q值的影響結果Fig.1 The influence of differentαon the Q in Polblogs data set

圖2 DBLP數(shù)據(jù)集中參數(shù)α對Q值的影響結果Fig.2 The influence of differentα on the Q in DBLP data set

參數(shù)β是社區(qū)融合閾值,用以控制兩個相似社區(qū)是否應該合并,因此控制重疊度的閾值β直接影響了最終社區(qū)數(shù)量.本節(jié)實驗用模塊度Q、社區(qū)數(shù)量對β的最佳取值進行驗證.根據(jù)不同社區(qū)數(shù)K下的模塊度Q進行對比,結果如圖3所示.

一般社區(qū)模塊度在[0.3,0.7]之間被認為是一個好的社區(qū)發(fā)現(xiàn)算法.圖3中S1的模塊度在社區(qū)數(shù)量為12時達到最優(yōu),S2和S3則分別在社區(qū)數(shù)量為15和18時達到最優(yōu).其次,再將不同β下的社區(qū)個數(shù)進行對比,結果如圖4所示,可以發(fā)現(xiàn)β取值為0.8時社區(qū)數(shù)量在15～18之間,說明此時劃分結果中的重疊比例最接近真實情況,因此社區(qū)融合閾值β的值最終設置為0.8.

圖3 重疊社區(qū)的模塊度隨社區(qū)數(shù)量的變化情況Fig.3 The influence of different community number on the K

圖4 社區(qū)數(shù)量隨閾值β 的變化情況Fig.4 The influence of differentβ on different community number K

3.4 算法性能驗證實驗

本節(jié)分別在人工數(shù)據(jù)集和6個真實網(wǎng)絡數(shù)據(jù)集上進行算法性能的驗證實驗,以此檢驗本文所提出的重疊社區(qū)檢測算法在檢測性能和檢測效率上的正確性和高效性.

3.4.1 人工數(shù)據(jù)集上的實驗結果

表4給出了人工網(wǎng)絡參數(shù)mu在不同取值時各算法在人工網(wǎng)絡S1上的NMI 實驗結果.從表4中數(shù)據(jù)可以看出,隨著mu逐漸增大,各算法的NMI值在逐漸減小,當mu值增大到一定程度時,社區(qū)識別算法將會失效.本文提出的TWOCD算法在mu取不同值時均具有較好的NMI值,這主要是由于TWOCD算法在執(zhí)行過程中構建了更合理的用戶–用戶關系圖,使得用戶的邊集合更高效,即便在處理復雜的網(wǎng)絡時,也能保證算法具有較高的精度和社區(qū)發(fā)現(xiàn)的穩(wěn)定性.

表4 mu 在不同取值時各算法在人工網(wǎng)絡S1上的NMI實驗結果Table 4 NMI experimental results of different algorithms on S1 under different mu value

表5給出了人工網(wǎng)絡參數(shù)om取不同值時,各算法在人工網(wǎng)絡S2上的NMI實驗結果.從表中的結果可以觀察到,當參數(shù)om增大時,即網(wǎng)絡中每個重疊節(jié)點隸屬的社區(qū)數(shù)增加時,各算法的NMI值隨之減小.盡管如此,本文提出的TWOCD算法在om取不同值時均具有較好的NMI值,這主要是由于TWOCD算法在最后通過社區(qū)重疊度進行判斷,將重疊度高的社區(qū)進行了合并,有效緩解社區(qū)結構過度重疊的問題,提高算法的識別效率與社區(qū)發(fā)現(xiàn)的穩(wěn)定性.

表5 om 在不同取值時各算法在人工網(wǎng)絡S2上的NMI 實驗結果Table 5 NMI experimental results of different algorithms on S2 under different om value

表6給出了人工網(wǎng)絡參數(shù)on取不同值時各算法在人工網(wǎng)絡S3上的NMI實驗結果.參數(shù)on的增大意味著網(wǎng)絡中更多的節(jié)點隸屬于重疊社區(qū).由表中的結果可以看出,隨著參數(shù)on的增大,各算法的NMI值都不斷減小.但是,TWOCD的NMI值下降趨勢較其他算法較慢.而且本文提出的TWOCD算法在on取不同值時均具有較好的NMI 值,這主要是由于TWOCD算法在社區(qū)發(fā)現(xiàn)時的初始種子節(jié)點選取時選擇了中心度最大的節(jié)點,中心度大說明該節(jié)點的影響力強,因此將這樣的節(jié)點作為起始節(jié)點將更加合理.

表6 on 在不同取值時各算法在人工網(wǎng)絡S3上的NMI實驗結果Table 6 NMI experimental results of different algorithms on S3 under different on value

綜上,在不同人工數(shù)據(jù)集上本文算法獲得了優(yōu)于其他算法的重疊社區(qū)發(fā)現(xiàn)結果.

3.4.2 真實數(shù)據(jù)集上的實驗結果

在真實網(wǎng)絡上對將本文算法與各種重疊社區(qū)發(fā)現(xiàn)算法的性能進行對比,各算法的參數(shù)選取均使用最優(yōu)參數(shù)配置,圖5給出了各算法在真實網(wǎng)絡上社區(qū)發(fā)現(xiàn)的對比結果.

幾種算法的參數(shù)均根據(jù)文獻建議進行設置,實驗中各算法的參數(shù)取值設置如下:COPRA中參數(shù)v表示節(jié)點攜帶的最大標簽數(shù),參數(shù)v的取值在2～15之間;LFM中的參數(shù)α用于控制社區(qū)規(guī)模,參數(shù)α的取值在0.5～1.5之間;CPM的參數(shù)K在1～10之間.通過實驗結果可以發(fā)現(xiàn)相對于其他4種算法,由于考慮到了用戶全局相似度和時效因素,TWOCD算法在多數(shù)網(wǎng)絡上取得了最好的重疊模塊度值.

圖5 真實數(shù)據(jù)集上各算法性能對比實驗Fig.5 Comparison results of different algorithms on real networks

表7 給出了各算法在真實網(wǎng)絡上社區(qū)發(fā)現(xiàn)結果及最優(yōu)參數(shù)值,在不同數(shù)據(jù)集下,計算出了參數(shù)取不同值時算法的模塊度指標性能.由于本文算法在用戶相似度計算及中心度計算上都較對比算法有所改進,因此在這些真實網(wǎng)絡中,本文算法TWOCD在大部分情況下都取了最高的模塊度Q.并且,本文算法在不同網(wǎng)絡上獲得最大模塊度時對應的參數(shù)α和β取值變化不大,這也驗證了這兩個參數(shù)最優(yōu)取值的有效性和通用性.

3.5 算法運行時間性能分析

本節(jié)將通過對比不同算法在LFR 基準數(shù)據(jù)集上的實驗效果來驗證本文所提算法的時間性能優(yōu)勢.在S1網(wǎng)絡上,固定mu=0.1,N取10 000～70 000,保持其他參數(shù)不變.各算法在不同規(guī)模人工網(wǎng)絡數(shù)據(jù)集上的運行性能如圖6所示.由圖6可知,CFinder 算法運行效率最低,由于該算法以派系為單位計算社區(qū)的重疊度,因此計算量過大,當網(wǎng)絡數(shù)量增加到一定值后算法失效;CPM算法的時間復雜度為非多項式級;COPRA算法的計算量與算法的迭代次數(shù)有關,因此當網(wǎng)絡規(guī)模較小時算法性能具有較大的優(yōu)勢;LFM算法是隨機選擇種子節(jié)點進行擴展,其局部最優(yōu)化的思想使得算法具有較高的計算效率.本文算法TWOCD在社區(qū)發(fā)現(xiàn)算法中的初始節(jié)點選擇上,優(yōu)化了社區(qū)中心度的計算方法,使得初始種子節(jié)點的選取更有價值,因此較好地降低了算法的計算復雜度.

圖6 不同算法運行時間比較Fig.6 Execution time comparison of different algorithms

表7 真實數(shù)據(jù)集上各算法在不同參數(shù)取值下性能對比結果Table 7 Comparison results of different algorithms on different parameter in real networks

4 結論

本文提出一種新穎的重疊社區(qū)發(fā)現(xiàn)算法TWOCD,該算法充分考慮了用戶興趣的時間因素,根據(jù)帶有時間加權鏈接的用戶–用戶圖實現(xiàn)重疊社區(qū)檢測.在社區(qū)發(fā)現(xiàn)迭代計算時選擇中心度最大的節(jié)點為種子節(jié)點,提高了社區(qū)發(fā)現(xiàn)在精準度.最后通過重疊度計算將重疊過多的社區(qū)進行合并,從而提高了算法執(zhí)行的效率.在仿真實驗中,利用人工網(wǎng)絡數(shù)據(jù)和真實網(wǎng)絡數(shù)據(jù)進行有效性驗證,實驗結果表明,本文提出的算法在社區(qū)發(fā)現(xiàn)質(zhì)量和計算效率上優(yōu)于已有算法.未來的工作計劃將該算法應用于為各類復雜網(wǎng)絡提供社區(qū)識別服務,進而為用戶提供更加個性化的社區(qū)服務.