基于時(shí)間加權(quán)的重疊社區(qū)檢測(cè)算法研究

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

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

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

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

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

1 相關(guān)工作

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

1.1 派系過濾算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 利用時(shí)間加權(quán)鏈接構(gòu)建用戶–用戶圖

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

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

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

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

2.2 用戶全局相似度的計(jì)算

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

2.2.1 節(jié)點(diǎn)的影響度

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

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

2.2.2 用戶全局相似度

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

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

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

2.3 社區(qū)中心點(diǎn)的計(jì)算

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

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

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

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

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

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

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

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

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

2.4 重疊社區(qū)檢測(cè)

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

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

算法1.Overlapping community detection algorithm

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

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

1)利用被選節(jié)點(diǎn)對(duì)社區(qū)C初始化,將社區(qū)的初始適應(yīng)度設(shè)置為0;

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

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

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

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

6)重復(fù)步驟5),直到社區(qū)C中沒有節(jié)點(diǎn)的適應(yīng)度為負(fù).

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

2.5 社區(qū)融合

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

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

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)方法與評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

標(biāo)準(zhǔn)化互信息(NMI)指標(biāo)定義為:

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

模塊度(Q)定義為:

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

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

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

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

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

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

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

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

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

3.4.1 人工數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

3.4.2 真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

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

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

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

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

3.5 算法運(yùn)行時(shí)間性能分析

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

圖6 不同算法運(yùn)行時(shí)間比較Fig.6 Execution time comparison of different algorithms

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

4 結(jié)論

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