費(fèi) 蓉,李莎莎,胡 博,唐 瑜,方金正

1(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,西安 710048)

2(北京華電優(yōu)控科技有限公司,北京 100193)

眾多復(fù)雜系統(tǒng)都可抽象成為網(wǎng)絡(luò)模型,如計(jì)算機(jī)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等得到了廣泛應(yīng)用[1],社區(qū)檢測(cè)問題對(duì)于研究復(fù)雜網(wǎng)絡(luò)以及人類生活具有重要意義.社區(qū)檢測(cè)期望將鏈接最緊密的節(jié)點(diǎn)劃分至同一社區(qū),有助于更好地了解整個(gè)社交網(wǎng)絡(luò),進(jìn)而有效利用資源[2].現(xiàn)實(shí)中,Facebook 等以朋友關(guān)系為基礎(chǔ)的社交網(wǎng)絡(luò)上,通過社區(qū)檢測(cè)可進(jìn)行朋友推薦[3,4].另外也可以用社區(qū)檢測(cè)對(duì)具有鏈接關(guān)系并且同興趣的用戶進(jìn)行興趣推送[5].除此之外,還可用于交通網(wǎng)絡(luò)中分析交通對(duì)城市功能社區(qū)(商業(yè)區(qū)、居民區(qū)、學(xué)校等)分布之間的關(guān)系[6].

近年來,社區(qū)檢測(cè)問題常歸于以下類型:基于圖分割的社區(qū)檢測(cè),需要提前定義分割社區(qū)個(gè)數(shù)及體積,通過最小化社區(qū)間的鏈接邊的數(shù)量實(shí)現(xiàn)社區(qū)劃分,如Kemighan-Lin 算法和譜劃分算法;基于聚類的社區(qū)檢測(cè)則是通過節(jié)點(diǎn)間的關(guān)系利用聚類的思想將其進(jìn)行社區(qū)檢測(cè),以GN 算法[7]、Newman 貪心算法和k-means算法為代表;基于模塊度最大化的社區(qū)檢測(cè)如Louvain算法,利用模塊度獲取最優(yōu)的網(wǎng)絡(luò)社區(qū)劃分;基于非負(fù)矩陣的社區(qū)檢測(cè),利用非負(fù)矩陣的思想將節(jié)點(diǎn)的鏈接矩陣進(jìn)行分解得到節(jié)點(diǎn)社區(qū)歸屬矩陣,如LANMF 算法[8];基于標(biāo)簽的社區(qū)檢測(cè)算法,以LPA 算法、CORP算法和LPPB 算法等為代表,對(duì)每個(gè)節(jié)點(diǎn)隨機(jī)生成標(biāo)簽,逐輪刷新所有節(jié)點(diǎn)的標(biāo)簽,直到所有節(jié)點(diǎn)的標(biāo)簽不再發(fā)生變化為止.

節(jié)點(diǎn)拓?fù)鋭?shì)的概念源于認(rèn)知物理學(xué)中的數(shù)據(jù)場理論[9],2009年,淦文燕提出了一種基于拓?fù)鋭?shì)的社區(qū)檢測(cè)方法,利用節(jié)點(diǎn)的鏈接信息構(gòu)造拓?fù)鋭?shì)場,在拓?fù)鋭?shì)場內(nèi)進(jìn)行社區(qū)劃分[10].拓?fù)鋭?shì)原理近年來得到了長足的發(fā)展.2018年,Wang 在山谷結(jié)構(gòu)的拓?fù)鋭?shì)場下基于節(jié)點(diǎn)位置進(jìn)行分析,設(shè)計(jì)DOCET 算法[11].但拓?fù)鋭?shì)社區(qū)算法在實(shí)踐中存在一種現(xiàn)象,當(dāng)獲得的模塊度值較高時(shí),社區(qū)的劃分?jǐn)?shù)量過大,當(dāng)社區(qū)網(wǎng)絡(luò)過于復(fù)雜時(shí),真實(shí)數(shù)據(jù)集出現(xiàn)了很多孤立性節(jié)點(diǎn)或孤立性小社區(qū).基于拓?fù)鋭?shì)原理進(jìn)行社區(qū)劃分,存在大量3-4 節(jié)點(diǎn)孤立為一個(gè)社區(qū)的現(xiàn)象出現(xiàn).這種孤立社區(qū)的出現(xiàn)為現(xiàn)實(shí)的推送,社區(qū)的擴(kuò)大等帶來影響.近期研究顯示,社區(qū)劃分不再單純的考慮鏈接結(jié)構(gòu),而是通過增加節(jié)點(diǎn)的屬性信息進(jìn)行社區(qū)劃分.節(jié)點(diǎn)的屬性信息越來越受到關(guān)注[12].

本文面向含標(biāo)簽屬性的社區(qū)檢測(cè)問題,針對(duì)上述基于拓?fù)鋭?shì)進(jìn)行的社區(qū)劃分存在的孤立性社區(qū)問題,提出了一種結(jié)合屬性標(biāo)簽的拓?fù)鋭?shì)社區(qū)檢測(cè)算法(TPCDLP).首先,將結(jié)合標(biāo)簽傳播思想將屬性信息構(gòu)造出節(jié)點(diǎn)間的鏈接權(quán)值.其次,把鏈接權(quán)值加入到拓?fù)鋭?shì)當(dāng)中構(gòu)造拓?fù)鋭?shì)場.然后,利用核心節(jié)點(diǎn)進(jìn)行子群社區(qū)的劃分.最后,利用子群社區(qū)間核心節(jié)點(diǎn)的距離進(jìn)行社區(qū)劃分.

1 相關(guān)工作

李德毅等2008年提出了社區(qū)檢測(cè)中的拓?fù)鋭?shì)理論,構(gòu)造了一種在網(wǎng)絡(luò)拓?fù)淇臻g中構(gòu)造的虛擬勢(shì)場[8].拓?fù)鋭?shì)借鑒了數(shù)學(xué)中的拓?fù)鋵W(xué)和物理中的場論思想,將網(wǎng)絡(luò)G看作一個(gè)包含n個(gè)節(jié)點(diǎn)的及其相互作用的抽象系統(tǒng).每一個(gè)結(jié)節(jié)周圍存在一個(gè)作用場,位于場中的任何節(jié)點(diǎn)都會(huì)收到其周圍節(jié)點(diǎn)的影響.但是節(jié)點(diǎn)的影響力隨著網(wǎng)絡(luò)距離的增加而快速衰減.

定義1.拓?fù)鋭?shì)場.一個(gè)網(wǎng)絡(luò)G=(V,E),網(wǎng)絡(luò)所有節(jié)點(diǎn)vi,1≤i≤n都存在一個(gè)拓?fù)鋭?shì)φ (vi),所有節(jié)點(diǎn)的拓?fù)鋭?shì)相互作用從而構(gòu)成拓?fù)鋭?shì)場.

定義2.拓?fù)鋭?shì).給定網(wǎng)絡(luò)G=(V,E),其中V={v1,v2,···,vn} 為網(wǎng)絡(luò)節(jié)點(diǎn),E={(vi,vj)|vi,vj∈V,i≠j}為節(jié)點(diǎn)邊集合,每個(gè)節(jié)點(diǎn)的拓?fù)鋭?shì)計(jì)算公式如下:

其中,dij表示節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的網(wǎng)絡(luò)距離或跳數(shù).影響因子 σ是用于控制每個(gè)節(jié)點(diǎn)的影響范圍.m(vj)表示節(jié)點(diǎn)vj的質(zhì)量,可以用來描述每個(gè)節(jié)點(diǎn)的固有屬性,但是通過相似研究,在本文設(shè)置為m(vj)=1.

本文首先利用了信息傳播的特性將節(jié)點(diǎn)的屬性結(jié)構(gòu)In和鏈關(guān)系E轉(zhuǎn)換成節(jié)點(diǎn)間的鏈接權(quán)重關(guān)系R.隨后,利用拓?fù)鋭?shì)將具有鏈接關(guān)系的網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)化成山脈形狀的拓?fù)鋭?shì)域.其次,在山脈形狀的立體結(jié)構(gòu)中找到局部最高點(diǎn),由局部最高點(diǎn)出發(fā)進(jìn)行子群社區(qū)的劃分.最后根據(jù)子群社區(qū)的分布情況,將子群社區(qū)進(jìn)行合并得到社區(qū)的劃分結(jié)果C.

2 一種基于標(biāo)簽傳播的拓?fù)鋭?shì)社區(qū)檢測(cè)算法

2.1 節(jié)點(diǎn)間鏈接權(quán)值計(jì)算

拓?fù)鋭?shì)算法利用的是鏈接關(guān)系構(gòu)造拓?fù)鋭?shì)場,未考慮結(jié)節(jié)間的屬性關(guān)系.社區(qū)的定義是將具有鏈接緊密程度的節(jié)點(diǎn)化為一個(gè)社區(qū),但是結(jié)節(jié)間的屬性關(guān)系同樣會(huì)影響到社區(qū)劃分的質(zhì)量和現(xiàn)實(shí)場景的應(yīng)用.

本文利用節(jié)點(diǎn)間的屬性關(guān)系和鏈接關(guān)系構(gòu)造節(jié)點(diǎn)間拓?fù)鋭?shì)的環(huán)境影響因子rij,從而保證節(jié)點(diǎn)i和 節(jié)點(diǎn)j之間的拓?fù)鋭?shì)能夠受到環(huán)境影響因子影響.公式如下:

借鑒標(biāo)簽傳播的思想,計(jì)算標(biāo)簽從節(jié)點(diǎn)vi傳播到節(jié)點(diǎn)vj的概率P(vi→vj),隨后令節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的環(huán)境影響因子rij=P(vi→vj).

2.2 標(biāo)簽傳播特性

定義3.節(jié)點(diǎn)影響力.設(shè)網(wǎng)絡(luò)G=(V,E)中每個(gè)節(jié)點(diǎn)vi都擁有一個(gè)影響力值,用In fi表示.由于大多網(wǎng)絡(luò)并不是連通圖,因此本文采用文獻(xiàn)[13]所提出LeaderRank算法,計(jì)算節(jié)點(diǎn)的LR 值.

LeaderRank 算法提到社交網(wǎng)絡(luò)不是一個(gè)強(qiáng)連通圖,所以引入一個(gè)節(jié)點(diǎn)g(Ground Node),與其他節(jié)點(diǎn)相互連接,使社交網(wǎng)絡(luò)變成一個(gè)強(qiáng)連通圖.LeaderRank 算法核心公式:

其中,aij表示節(jié)點(diǎn)j到節(jié)點(diǎn)i是否有鏈接,有為1,無為0;表示節(jié)點(diǎn)j的出度個(gè)數(shù);N表示節(jié)點(diǎn)總個(gè)數(shù);LRi(t)表示i節(jié)點(diǎn)在t時(shí)刻的得分;tc表示LRi(t)收斂的得分;表示tc時(shí)刻地節(jié)點(diǎn)的得分;LRi表示i節(jié)點(diǎn)最終的得分.

圖1是一個(gè)小社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖,一共有18 個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)代表一個(gè)人,每個(gè)人都有一個(gè)興趣愛好,將興趣愛好分為兩類,并用兩種不同的圖標(biāo)表示人們的興趣愛好.節(jié)點(diǎn)間的連線代表人們之間的關(guān)系.通過上述的公式,計(jì)算得到這個(gè)簡單的社交網(wǎng)絡(luò)數(shù)據(jù)集每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)影響力,如表1所示.

圖1 小社交網(wǎng)絡(luò)

表1 小社區(qū)網(wǎng)絡(luò)的節(jié)點(diǎn)影響力LR

定義4.傳播特性k.定義ki←j為標(biāo)簽從節(jié)點(diǎn)j到節(jié)點(diǎn)i的傳播特性度量值.

該傳播特性是由節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的節(jié)點(diǎn)影響力決定的.當(dāng)LRi遠(yuǎn)大于In fj時(shí),ki←j≈1,說明vj的影響力較大,節(jié)點(diǎn)vi容易受節(jié)點(diǎn)vj的影響.反之,當(dāng)LRj遠(yuǎn)大于LRi時(shí),ki←j≈0,說明vi的影響力較大,節(jié)點(diǎn)vi不容易受節(jié)點(diǎn)vj的影響.

以節(jié)點(diǎn)1、2、3 為例,已知LR1=0.762 913,LR2=0.915 51,LR3=1.068 08,根據(jù)定義4 的公式,可得:

節(jié)點(diǎn)1 的影響力LR1小于節(jié)點(diǎn)3 和節(jié)點(diǎn)4 的影響力.通過比較發(fā)現(xiàn)節(jié)點(diǎn)1 到節(jié)點(diǎn)2 的傳播特性要低于節(jié)點(diǎn)2 到節(jié)點(diǎn)1 的傳播特性,同樣的節(jié)點(diǎn)1 到節(jié)點(diǎn)3的傳播特性也低于節(jié)點(diǎn)3 到節(jié)點(diǎn)1 的傳播特性.由此,傳播特性值可以反映出影響力高的節(jié)點(diǎn)與影響力低的節(jié)點(diǎn)之間受影響程度的差異.

2.3 節(jié)點(diǎn)間的相似度計(jì)算

社會(huì)網(wǎng)絡(luò)不僅具有拓?fù)浣Y(jié)構(gòu)特征,而且網(wǎng)絡(luò)中節(jié)點(diǎn)的內(nèi)在屬性也容易獲取,如C-DBLP 中的學(xué)者記錄都擁有研究方向、工作單位等信息,因此節(jié)點(diǎn)的屬性特征S(節(jié)點(diǎn)的相似度)包含兩部分:結(jié)構(gòu)屬性S t和節(jié)點(diǎn)內(nèi)在屬性In.

結(jié)構(gòu)屬性:

節(jié)點(diǎn)內(nèi)在屬性:

N(i)表示節(jié)點(diǎn)i的所有鄰居與節(jié)點(diǎn)i的集合.ini={in1,in2,···,inz}為 節(jié)點(diǎn)i的內(nèi)在屬性集合,iniz是節(jié)點(diǎn)vi的第z個(gè)屬性值;z是內(nèi)在屬性總個(gè)數(shù).

圖1所示的社交網(wǎng)絡(luò)數(shù)據(jù)集中,節(jié)點(diǎn)1 和節(jié)點(diǎn)2 都有一個(gè)相同的鄰居節(jié)點(diǎn)3 和節(jié)點(diǎn)4,所以結(jié)構(gòu)屬性節(jié)點(diǎn)1 和節(jié)點(diǎn)2 節(jié)點(diǎn)都有相同的興趣愛好,所以內(nèi)在屬性Ln1,2=(1/2)×(1+1)=1.由此節(jié)點(diǎn)1 和節(jié)點(diǎn)2 間的屬性特征S1,2=0.577 35+1=1.577 35.同理,S1,3=1.516 40,S1,4=1.516 40.

2.4 節(jié)點(diǎn)間的傳播概率計(jì)算

定義5.標(biāo)簽傳播概率(節(jié)點(diǎn)間的關(guān)聯(lián)強(qiáng)度,也就是邊的權(quán)值).節(jié)點(diǎn)j的標(biāo)簽以概率P(i←j)傳 播到節(jié)點(diǎn)i,P(i←j)取 決于節(jié)點(diǎn)i和j的相似性度量Si,j、傳播特性度量ki←j和鄰接矩陣δ (i,j).

節(jié)點(diǎn)j到節(jié)點(diǎn)i的標(biāo)簽傳播概率體現(xiàn)了標(biāo)簽從節(jié)點(diǎn)j傳播到節(jié)點(diǎn)i的能力,也可以認(rèn)為是節(jié)點(diǎn)j到節(jié)點(diǎn)i的有向邊的權(quán)值.由此可得,節(jié)點(diǎn)j到節(jié)點(diǎn)i的有向邊的權(quán)值:

由上述公式可以計(jì)算r12=S1,2×k1→2×δ(1,2)=1.577 35×0.465 892×1=0.734 87,r13=0.664 62,r14=0.664 63.由于節(jié)點(diǎn)的拓?fù)鋭?shì)公式φ(vi)=可以先計(jì)算節(jié)點(diǎn)vi的如圖2所示,節(jié)點(diǎn)1 的=r12+r13+r14=0.734 87+0.664 62+0.664 63=2.064 12.節(jié)點(diǎn)1 到節(jié)點(diǎn)2 的標(biāo)簽傳播概率決定了節(jié)點(diǎn)1 將信息傳遞到節(jié)點(diǎn)2 的能力強(qiáng)度,由此也決定了節(jié)點(diǎn)1 到節(jié)點(diǎn)2 節(jié)點(diǎn)的屬性信息和鏈接信息影響后拓?fù)鋭?shì)變化.表2是將每個(gè)節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的環(huán)境影響因子進(jìn)行加和的結(jié)果.

圖2 小社交網(wǎng)絡(luò)的節(jié)點(diǎn)1 的環(huán)境影響因子

表2 小社交網(wǎng)絡(luò)的節(jié)點(diǎn)環(huán)境影響因子求和

表3是通過改進(jìn)后的拓?fù)鋭?shì)公式計(jì)算出圖1的社交網(wǎng)絡(luò)數(shù)據(jù)集的每個(gè)節(jié)點(diǎn)的拓?fù)鋭?shì)值.并且將節(jié)點(diǎn)中拓普勢(shì)局部最高的節(jié)點(diǎn)用五角星標(biāo)記在圖3中.

2.5 子群社區(qū)劃分

通過節(jié)點(diǎn)拓?fù)鋭?shì)的計(jì)算,將網(wǎng)絡(luò)的鏈接結(jié)構(gòu)轉(zhuǎn)變成山脈形狀的拓?fù)鋭?shì)場.社區(qū)的劃分就如同山的劃分,山峰、山谷和斜坡,對(duì)應(yīng)社區(qū)的核心節(jié)點(diǎn)、重疊節(jié)點(diǎn)以及內(nèi)部節(jié)點(diǎn).

定義6.核心節(jié)點(diǎn).假設(shè)在一個(gè)社交網(wǎng)絡(luò)G=(V,E)中,其拓?fù)鋭?shì)域G′=(V,E,?),Ni是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn).?vj∈Ni,如果? (vi)>?(vj),則節(jié)點(diǎn)vi是拓?fù)鋭?shì)域的局部最高點(diǎn).

通過上述的定義,可以看出核心節(jié)點(diǎn)是局部最高點(diǎn),也就是山峰節(jié)點(diǎn).如果根據(jù)當(dāng)前的核心節(jié)點(diǎn)進(jìn)行社區(qū)劃分,將會(huì)影響社區(qū)劃分的質(zhì)量和數(shù)量.由此,當(dāng)前通過核心節(jié)點(diǎn)劃分的社區(qū)被稱為子群社區(qū),后續(xù)需要進(jìn)一步處理.圖3中五角星標(biāo)識(shí)的節(jié)點(diǎn)為拓?fù)鋭?shì)局部最高點(diǎn),也就是當(dāng)前子群社區(qū)的核心節(jié)點(diǎn).

定義7.重疊節(jié)點(diǎn).假設(shè)在一個(gè)社交網(wǎng)絡(luò)G=(V,E)中,其拓?fù)鋭?shì)域G′=(V,E,?),Ni是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn).?vj∈Ni,如果? (vi)

當(dāng)山谷節(jié)點(diǎn)就直接歸屬于它鄰居節(jié)點(diǎn)所在的社區(qū).由此,山谷節(jié)點(diǎn)i處在兩個(gè)不同核心節(jié)點(diǎn)的社區(qū)之間,才能被稱為重疊節(jié)點(diǎn).

定義8.內(nèi)部節(jié)點(diǎn).假設(shè)在一個(gè)社交網(wǎng)絡(luò)G=(V,E)中,其拓?fù)鋭?shì)域G′=(V,E,?),Ni是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn).內(nèi)部節(jié)點(diǎn)滿足下面任意一種情況成立:(1)?vj∈Ni,如果?(vi)?(vj),則節(jié)點(diǎn)vi處于斜波位置,也就是拓?fù)鋭?shì)域的內(nèi)部節(jié)點(diǎn).(2)如果?(vi)

定義9.邊緣節(jié)點(diǎn).假設(shè)在一個(gè)社交網(wǎng)絡(luò)G=(V,E)中,其拓?fù)鋭?shì)域G′=(V,E,?),Ni是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn),Coverlap是重疊節(jié)點(diǎn)的集合,Cno?overlap是不重疊節(jié)點(diǎn)的集合.(1)如果vi∈Coverlap,則節(jié)點(diǎn)vi是邊緣節(jié)點(diǎn);(2)?vj∈Nj,如果vi∈Cno?overlap,而NjCno?overlap,并且NjCoverlap,則節(jié)點(diǎn)vi是邊緣節(jié)點(diǎn).

邊緣節(jié)點(diǎn)可以是社區(qū)的內(nèi)部節(jié)點(diǎn)也可以是社區(qū)的重疊節(jié)點(diǎn).每個(gè)節(jié)點(diǎn)vi都記錄它到它歸屬社區(qū)的核心節(jié)點(diǎn)的最短距離NCDi.

2.6 子群合并

在子群社區(qū)劃分中,拓?fù)鋭?shì)值為局部最大值的節(jié)點(diǎn)視為山峰節(jié)點(diǎn),一個(gè)山峰節(jié)點(diǎn)對(duì)應(yīng)一個(gè)社區(qū).但子群社區(qū)劃分中存在特殊兩種情況.1)當(dāng)社交網(wǎng)絡(luò)數(shù)據(jù)集節(jié)點(diǎn)鏈接稀疏、節(jié)點(diǎn)度數(shù)相似時(shí),很容易導(dǎo)致劃分社區(qū)數(shù)量過多,社區(qū)包含節(jié)點(diǎn)過少等問題,從而影響到社區(qū)的劃分質(zhì)量和現(xiàn)實(shí)應(yīng)用.2)劃分出的社區(qū)為孤立子群社區(qū).這種孤立的子群社區(qū)不能通過核心節(jié)點(diǎn)間的距離關(guān)系進(jìn)行合并.下面對(duì)兩種情況給出相應(yīng)解決方案.

2.6.1 子群社區(qū)劃分

由于社交網(wǎng)絡(luò)數(shù)據(jù)集的節(jié)點(diǎn)數(shù)多,如果利用深度遍歷的方法計(jì)算核心節(jié)點(diǎn)間的距離,計(jì)算的復(fù)雜度很高,時(shí)間耗費(fèi)長,所以為了快速得到上峰節(jié)點(diǎn)間的距離,在子群社區(qū)劃分的同時(shí),計(jì)算子群社區(qū)中每個(gè)節(jié)點(diǎn)到達(dá)其社區(qū)的上峰節(jié)點(diǎn)的距離,最后分析了3 種情況計(jì)算子群社區(qū)間的距離.

由于社交網(wǎng)絡(luò)數(shù)據(jù)集的節(jié)點(diǎn)數(shù)多,在子群社區(qū)劃分的同時(shí),計(jì)算子群社區(qū)中每個(gè)節(jié)點(diǎn)到達(dá)其社區(qū)的山峰節(jié)點(diǎn)的距離,并分析了計(jì)算子群社區(qū)間的距離的3 種情況.

(1)兩個(gè)子群社區(qū)不重疊但邊緣節(jié)點(diǎn)相連接

兩個(gè)子群社區(qū)沒有重疊節(jié)點(diǎn),但是社區(qū)間的邊緣節(jié)點(diǎn)互聯(lián).該情況下,由于每個(gè)邊緣節(jié)點(diǎn)都存儲(chǔ)了到達(dá)它自身歸屬的子群社區(qū)的最短距離NCD,可以利用邊緣節(jié)點(diǎn)進(jìn)行信息交互,得到兩個(gè)子群社區(qū)的核心節(jié)點(diǎn)之間的距離.但是,邊緣節(jié)點(diǎn)自身歸屬的子群社區(qū)的核心節(jié)點(diǎn)的距離不一定相同,需要選取其中最短的距離為兩個(gè)子群社區(qū)不重疊但邊緣節(jié)點(diǎn)相連接的距離CCD.

(2)子群社區(qū)不重疊并且邊緣節(jié)點(diǎn)相也不連接

子群社區(qū)的劃分是根據(jù)節(jié)點(diǎn)的拓?fù)鋭?shì)值由高到低進(jìn)行的,但是一旦碰到當(dāng)前劃分的節(jié)點(diǎn)其拓普勢(shì)值為局部最低點(diǎn)的時(shí)候,也就是劃分到山谷節(jié)點(diǎn)時(shí),就結(jié)束當(dāng)前子群社區(qū)的劃分.為了計(jì)算不重疊且邊緣節(jié)點(diǎn)不相連的兩個(gè)子群社區(qū)的核心節(jié)點(diǎn)間的距離,采用邊緣節(jié)點(diǎn)探測(cè)方法進(jìn)行計(jì)算.即利用當(dāng)前子群社區(qū)的邊緣節(jié)點(diǎn),根據(jù)設(shè)置的步長向子群社區(qū)外部進(jìn)行跳轉(zhuǎn).每當(dāng)跳到下一個(gè)節(jié)點(diǎn),首先判斷當(dāng)前節(jié)點(diǎn)是否歸屬于其他子群社區(qū),是,根據(jù)跳轉(zhuǎn)的步長以及初始節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的信息計(jì)算兩個(gè)社區(qū)的距離;否,跳轉(zhuǎn)到下一個(gè)節(jié)點(diǎn).在做邊緣探測(cè)的時(shí)候,探測(cè)步長值設(shè)置為當(dāng)前邊緣節(jié)點(diǎn)到達(dá)子群社區(qū)核心節(jié)點(diǎn)的歐式距離的1/2.

(3)子群社區(qū)重疊

當(dāng)子群社區(qū)之間有重疊節(jié)點(diǎn),需根據(jù)子群社區(qū)間的重疊節(jié)點(diǎn)到達(dá)核心節(jié)點(diǎn)的距離加和,取其最短的路徑長度.

對(duì)于子群社區(qū)間的距離的計(jì)算,首先分別對(duì)上述3 種情況進(jìn)行處理和計(jì)算得到社區(qū)的最短距離,然后將3 種情況的結(jié)果進(jìn)行比較取其最小值,最終得到相近兩兩社區(qū)的最短距離.

2.6.2 子群社區(qū)合并

通過上述的3 種情況分析和計(jì)算,得到了相近的兩個(gè)社區(qū)之間核心節(jié)點(diǎn)的最短路徑.根據(jù)核心節(jié)點(diǎn)的距離,可以將相近的社區(qū)進(jìn)行合并,但是實(shí)際上很多數(shù)據(jù)集其節(jié)點(diǎn)的鏈接關(guān)系很稀疏,也就是存在很多孤立的節(jié)點(diǎn)以及非常小的“孤立”社區(qū),如圖4所示.

圖4是citeseer 數(shù)據(jù)集的數(shù)據(jù)節(jié)點(diǎn)分布,圖中顯示,左上方的節(jié)點(diǎn)有著緊密聯(lián)系,但下方的節(jié)點(diǎn)非常稀疏.節(jié)點(diǎn)的稀疏易導(dǎo)致劃分的社區(qū)數(shù)被這些稀疏分布的節(jié)點(diǎn)所決定,使得社區(qū)劃分范圍過小失去意義.因此在子群社區(qū)劃分后,需要將子群社區(qū)針對(duì)稀疏分布情況進(jìn)行合并.所以子群社區(qū)合并分為兩種.

圖4 Citeseer 數(shù)據(jù)集的節(jié)點(diǎn)分布

(1)相鄰子群社區(qū)合并

相近的兩個(gè)社區(qū)之間核心節(jié)點(diǎn)的最短路徑存放在CCD中,計(jì)算d=max(CCD),設(shè)置φ 為合并參數(shù)取值0-1,φd為合并距離.當(dāng)CCDij<φd時(shí),將兩個(gè)社區(qū)進(jìn)行合并,隨機(jī)將兩個(gè)子群社區(qū)中的一個(gè)核心節(jié)點(diǎn)設(shè)置為合并后社區(qū)的核心節(jié)點(diǎn).

(2)稀疏子群社區(qū)合并

設(shè)定規(guī)則:核心節(jié)點(diǎn)的信息屬性相同的稀疏子群社區(qū)合并成為一個(gè)大社區(qū).

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

所有實(shí)驗(yàn)均在Intel(R)Core(TM)i7- CPU 3300 和8.00 GB RAM 的個(gè)人計(jì)算機(jī)(PC)上使用Visual Studio 2015 上實(shí)現(xiàn).

3.1 標(biāo)準(zhǔn)實(shí)驗(yàn)數(shù)據(jù)集

為驗(yàn)證算法有效性,以下給出3 個(gè)同時(shí)擁有鏈接和屬性的社區(qū)網(wǎng)絡(luò)數(shù)據(jù)集信息,見表4.

表4 數(shù)據(jù)集信息

3.2 評(píng)估標(biāo)準(zhǔn)方法

(1)改進(jìn)的模塊度由于本文是對(duì)重疊社區(qū)進(jìn)行社區(qū)劃分,所以對(duì)于模塊度的評(píng)估標(biāo)準(zhǔn)采用的是一種引入隸屬系數(shù)的優(yōu)化基礎(chǔ)上同時(shí)發(fā)現(xiàn)重疊和層次社區(qū)結(jié)構(gòu)的方法,節(jié)點(diǎn)的隸屬系數(shù)被重新定義為該節(jié)點(diǎn)歸屬社區(qū)的個(gè)數(shù).并且改進(jìn)的模塊度值越高,說明社區(qū)內(nèi)部鏈接更為緊密.其具體公式如下:

其中,Oi表示的是節(jié)點(diǎn)i所歸屬社團(tuán)的數(shù)量,其余和非重疊社團(tuán)發(fā)現(xiàn)評(píng)價(jià)指標(biāo)模塊度Q類似.

(2)信息熵Entropy.信息熵將社區(qū)內(nèi)部節(jié)點(diǎn)用于不相同屬性的情況利用公式進(jìn)行放大,由此判斷社區(qū)對(duì)于屬性劃分的合理性.信息熵值越大,說明劃分出的社區(qū)內(nèi)部節(jié)點(diǎn)擁有不同屬性的情況越多,從屬性的角度分析社區(qū)劃分不合理,由此希望信息熵值小.信息熵的公式如下:

其中,entropy(ai,cj)=?pijlog2pij,pij為 社區(qū)j中的節(jié)點(diǎn)具有屬性值ai的比例.

(3)社區(qū)重疊度Overlap.社區(qū)重疊節(jié)點(diǎn)的個(gè)數(shù)決定了社區(qū)重疊度Overlap的值.它體現(xiàn)了網(wǎng)絡(luò)耦合度,計(jì)算公式如下:

其中,|c|表示社區(qū)c的節(jié)點(diǎn)個(gè)數(shù),m表示網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù).

(4)綜合指標(biāo)F.一般情況下,重疊度高的網(wǎng)絡(luò)其模塊度相對(duì)較低,兩者呈現(xiàn)負(fù)相關(guān)性.而對(duì)于實(shí)驗(yàn)結(jié)果而言,模塊度越大,信息熵和重疊度越小,社區(qū)挖掘的質(zhì)量就越好.所以綜合以上情況,為了輸出更為合適的社區(qū)結(jié)果,定義F值為綜合評(píng)估指標(biāo):

3.3 對(duì)比實(shí)驗(yàn)

3.3.1 有屬性數(shù)據(jù)集實(shí)驗(yàn)對(duì)比

在有屬性數(shù)據(jù)集實(shí)驗(yàn)中,將子群社區(qū)的劃分與合并進(jìn)行詳細(xì)的分析.并且為了更好地展示本文提出的算法的優(yōu)越性,將本文提出的算法與DOCET 算法、LANMF 算法、LPPB 算法[14]、Louvain 算法[15]、SCD算法[16]和DEMON 算法[17]進(jìn)行實(shí)驗(yàn)對(duì)比.DOCET 算法、Louvain 算法、SCD 算法和DEMON算法只考慮了社交網(wǎng)絡(luò)數(shù)據(jù)集中節(jié)點(diǎn)的鏈接信息,而LANMF 算法和LPPB 算法利用社交網(wǎng)絡(luò)數(shù)據(jù)集中節(jié)點(diǎn)的鏈接信息和屬性信息進(jìn)行社區(qū)劃分.這3 個(gè)數(shù)據(jù)集中,DOCET算法、LANMF 算法、LPPB 算法、SCD 算法和DEMON算法都能進(jìn)行重疊社區(qū)的劃分,而Louvain 算法主要針對(duì)的是非重疊節(jié)點(diǎn)的劃分.

(1)子群社區(qū)劃分

對(duì)3 個(gè)有屬性數(shù)據(jù)集進(jìn)行子群社區(qū)的劃分.首先,根據(jù)節(jié)點(diǎn)拓?fù)鋭?shì)值的局部最高點(diǎn)確定核心節(jié)點(diǎn).再利用核心節(jié)點(diǎn)進(jìn)行子群社區(qū)劃分.最后,將子群社區(qū)劃分結(jié)果進(jìn)行計(jì)算匯總,具體如表5所示.

表5 有屬性數(shù)據(jù)集的子群社區(qū)劃分

如表5所示,在citeseer 數(shù)據(jù)集的子群社區(qū)數(shù)489 個(gè)但其中有262 個(gè)孤立的子群社區(qū)數(shù),也就是一半的社區(qū)是孤立子群社區(qū).而這些孤立子群社區(qū)節(jié)點(diǎn)的數(shù)量都小于10,由此citeseer 數(shù)據(jù)集一半的子群社區(qū)的節(jié)點(diǎn)數(shù)過小.cora 數(shù)據(jù)集的子群社區(qū)數(shù)是233 個(gè),其中1/4 的子群社區(qū)是孤立子群社區(qū).而WebKB 數(shù)據(jù)集子群社區(qū)數(shù)是35 個(gè),它的子群社區(qū)劃分?jǐn)?shù)量相對(duì)于其它兩個(gè)有屬性數(shù)據(jù)集最小但綜合指標(biāo)最高.通過表中的群社區(qū)數(shù)和綜合指標(biāo)的數(shù)據(jù)看,WebKB 數(shù)據(jù)集當(dāng)前的子群劃分效果好,而citeseer 數(shù)據(jù)集和cora 數(shù)據(jù)集子群社區(qū)數(shù)多,孤立子群社區(qū)數(shù)占子群社區(qū)數(shù)的比例大,需要將這些數(shù)據(jù)集進(jìn)行進(jìn)一步的合并,確保社區(qū)劃分的綜合質(zhì)量.

(2)子群社區(qū)合并

子群劃分實(shí)驗(yàn)中,已經(jīng)將3 個(gè)有屬性的數(shù)據(jù)集進(jìn)行的子群社區(qū)的劃分,接下來根據(jù)子群社區(qū)間的距離CCD和設(shè)置的合并范圍φd進(jìn)行社區(qū)的合并,φ 的取值為0.2,結(jié)果如表6所示.

如表5和表6所示,citeseer 數(shù)據(jù)集由498 個(gè)子群社區(qū)合并成為了132 個(gè)社區(qū),是合并前子群社區(qū)數(shù)量的1/4;cora 數(shù)據(jù)集由233 個(gè)子群社區(qū)合并成為45 個(gè)社區(qū),是合并前子群社區(qū)數(shù)量的1/5;WebKB 數(shù)據(jù)集由于數(shù)據(jù)量小,合并后一共由20 個(gè)社區(qū),是合并前子群社區(qū)數(shù)量的4/7.所以本文提出的算法在社區(qū)合并后,3 個(gè)有屬性數(shù)據(jù)集的社區(qū)數(shù)都有所下降.而綜合指標(biāo)方面,citeseer 數(shù)據(jù)集由合并前0.995442 降到0.909849,而cora 數(shù)據(jù)集也由合并前0.994164 降到0.876 022.citeseer 數(shù)據(jù)集和cora 數(shù)據(jù)集合并后綜合指標(biāo)和合并前的綜合指標(biāo)差距在0.1 左右.然而,造成這兩個(gè)數(shù)據(jù)集在合并后綜合指標(biāo)下降的原因是合并子群社區(qū)后改進(jìn)后的模塊度下降導(dǎo)致.citeseer 數(shù)據(jù)集的改進(jìn)模塊度由合并前0.684279 降到0.612224,而重疊度和信息熵的變化不明顯.同樣的cora 數(shù)據(jù)集的改進(jìn)模塊度也由合并前0.654599 降到0.563148,而重疊度和信息熵的變化也不明顯.相反,WebKB 數(shù)據(jù)集的綜合指標(biāo)比合并前的綜合指標(biāo)高,由合并前1.259545 升高到1.309186,差距在0.05 左右.在進(jìn)行子群社區(qū)的合并過程中,綜合指標(biāo)在0.1 左右浮動(dòng),但是社區(qū)數(shù)量明顯減少.

表6 子群社區(qū)合并結(jié)果

表6中,將文本提出的TPCDLP 算法和其他3 個(gè)社區(qū)檢測(cè)的算法進(jìn)行了比較.通過比較可以看出,在citeseer 數(shù)據(jù)集中,Louvain 算法的綜合指標(biāo)最高,再是本文提出的算法.出現(xiàn)這種情況的原因是由于Louvain 算法是用模塊度最優(yōu)的方法進(jìn)行社區(qū)的劃分.所以與其他四個(gè)算法的改進(jìn)模塊度比較,Louvain算法的改進(jìn)模塊度最高.雖然本文用改進(jìn)的模塊度作為評(píng)估標(biāo)準(zhǔn),但是當(dāng)社區(qū)為非重疊社區(qū)時(shí),改進(jìn)的模塊度計(jì)算公式其實(shí)就是模塊度的公式.所以Louvain算法的改進(jìn)模塊度相對(duì)其他算法會(huì)高,由此綜合指標(biāo)也高.然而在cora 數(shù)據(jù)集和WebKB 數(shù)據(jù)集中,本文提出的算法與其他6 個(gè)社區(qū)檢測(cè)的算法比較,改進(jìn)的模塊度和綜合指標(biāo)都是最高.本文算法在cora 數(shù)據(jù)集上,改進(jìn)的模塊度為0.922984,與其他4 個(gè)算法的改進(jìn)的模塊度高出最小為0.1 左右;而綜合指標(biāo)為1.212 7985,與其他6 個(gè)算法的綜合指標(biāo)高出最小為0.2 左右.本文算法在WebKB 數(shù)據(jù)集上,改進(jìn)的模塊度為0.839338,同樣與其他6 個(gè)算法的改進(jìn)的模塊度高出最小為0.1 左右;而綜合指標(biāo)為1.292 0815,同樣與其他6 個(gè)算法的綜合指標(biāo)高出最小為0.2 左右.所以,通過上述分析,TPCDLP 相對(duì)其它6 個(gè)算法具有一定的優(yōu)勢(shì).

4 真實(shí)社區(qū)應(yīng)用

為了驗(yàn)證本文算法在現(xiàn)實(shí)應(yīng)用中的有效性,選擇了3 個(gè)真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù),如表7所示.

表7 真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集

Karate 為美國空手道俱樂部跆拳道俱樂部的真實(shí)劃分.

Dolphin 數(shù)據(jù)集是 D.Lusseau 等人使用長達(dá) 7年的時(shí)間觀察新西蘭 Doubtful Sound 海峽 62 只海豚群體的交流情況而得到的海豚社會(huì)關(guān)系網(wǎng)絡(luò).這個(gè)網(wǎng)絡(luò)具有 62 個(gè)節(jié)點(diǎn),159 條邊.節(jié)點(diǎn)表示海豚,而邊表示海豚間的頻繁接觸,該圖為無權(quán)圖.

Football 網(wǎng)絡(luò),根據(jù)美國大學(xué)生足球聯(lián)賽而創(chuàng)建的一個(gè)復(fù)雜的社會(huì)網(wǎng)絡(luò).該網(wǎng)絡(luò)包含 115 個(gè)節(jié)點(diǎn)和616 條邊,其中網(wǎng)絡(luò)中的結(jié)點(diǎn)代表足球隊(duì),兩個(gè)結(jié)點(diǎn)之間的邊表示兩只球隊(duì)之間進(jìn)行過一場比賽.參賽的115 支大學(xué)生代表隊(duì)被分為12 個(gè)聯(lián)盟.比賽的流程是聯(lián)盟內(nèi)部的球隊(duì)先進(jìn)行小組賽,然后再是聯(lián)盟之間球隊(duì)的比賽.

此處選擇了標(biāo)準(zhǔn)化互信息(NMI)評(píng)價(jià)指標(biāo)來衡量算法得到的社區(qū)劃分結(jié)果與實(shí)際社區(qū)的相似性分區(qū)結(jié)果比較.NMI的計(jì)算公式如下:

其中,A和B代表社區(qū)網(wǎng)絡(luò)的兩個(gè)分區(qū),C是混淆矩陣,混淆矩陣C中的元素Cij表示社區(qū)i除以A和社區(qū)j除以B的節(jié)點(diǎn)數(shù).CA(CB)表示A(B)分區(qū)中的社區(qū)數(shù),Ci(Cj)是混淆矩陣C中第i行 (j列)元素的和,N是原始社區(qū)網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù).當(dāng)NMI值為1 時(shí),表示A和B在社區(qū)網(wǎng)絡(luò)中的劃分相同.

由于3 個(gè)真實(shí)社區(qū)數(shù)據(jù)集不含屬性信息,此處采用Louvain 算法、DEMON 算法和DOCET 算法與提出的TPCDLP 算法進(jìn)行比較.實(shí)驗(yàn)結(jié)果如表8所示:在海豚數(shù)據(jù)集(dolphins)上,本文提出的MIFCD算法的NMI值最高;在空手道數(shù)據(jù)集(karate)上,本文提出的TPCDLP 算法的NMI 值優(yōu)于DEMON 算法;在足球數(shù)據(jù)集(football)上,TPCDLP 表現(xiàn)好于DOCET算法.可以看出,TPCDLP 能夠基本實(shí)現(xiàn)真實(shí)社區(qū)劃分.

表8 歸一化互信息評(píng)價(jià)指標(biāo)的實(shí)驗(yàn)結(jié)果

5 總結(jié)

本文提出了一種基于標(biāo)簽屬性的拓?fù)鋭?shì)社區(qū)檢測(cè)算法.該算法利用標(biāo)簽傳播方法構(gòu)造節(jié)點(diǎn)間的鏈接權(quán)重,保證分割社區(qū)中的節(jié)點(diǎn)具有緊密的鏈接,并保持區(qū)域內(nèi)部屬性特征高度一致.由于實(shí)際網(wǎng)絡(luò)數(shù)據(jù)具有冗余關(guān)系、數(shù)據(jù)存儲(chǔ)量大、數(shù)據(jù)分布離散等特點(diǎn),采用拓?fù)鋭?shì)最高的局部節(jié)點(diǎn)作為社區(qū)的核心節(jié)點(diǎn)進(jìn)行社區(qū)劃分的算法容易導(dǎo)致社區(qū)重疊度高、數(shù)量多,因此,在劃分子社區(qū)之后,利用子節(jié)點(diǎn)與屬性特征之間的距離劃分社區(qū),在保證社區(qū)節(jié)點(diǎn)之間的鏈接緊密性和屬性相關(guān)性的同時(shí),能夠解決細(xì)粒度獨(dú)立社區(qū)問題.