孟彩霞，李楠楠，張 琰

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 700121)

0 引 言

在現(xiàn)實(shí)世界中存在各種復(fù)雜系統(tǒng)，這些系統(tǒng)通常可以以網(wǎng)絡(luò)的形式表達(dá)，比如常見的電力網(wǎng)絡(luò)、航空網(wǎng)絡(luò)以及社交網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)具有小世界、無標(biāo)度、社區(qū)結(jié)構(gòu)等許多基本特性，而其中最為重要的特性是社區(qū)結(jié)構(gòu)。為了挖掘這些社區(qū)結(jié)構(gòu)，可以使用一些不同領(lǐng)域的方法，如數(shù)據(jù)挖掘中的聚類或圖論中的圖分區(qū)等，挖掘社區(qū)結(jié)構(gòu)的過程統(tǒng)稱為社區(qū)發(fā)現(xiàn)[1]。通常將網(wǎng)絡(luò)表示為圖，圖中的點(diǎn)表示網(wǎng)絡(luò)中具體的實(shí)體，邊表示網(wǎng)絡(luò)中實(shí)體與實(shí)體之間的關(guān)聯(lián)[2-3]。大多數(shù)關(guān)于社區(qū)檢測的論文使用圖作為網(wǎng)絡(luò)的數(shù)學(xué)表示，更精確地說是無向圖。然而，很多真實(shí)網(wǎng)絡(luò)具有復(fù)雜的關(guān)系，并且都是有權(quán)值和方向的。此外，將有向圖轉(zhuǎn)化為無向圖會(huì)導(dǎo)致信息的丟失，從而使檢測到的社區(qū)結(jié)構(gòu)沒有真正意義[4]。由于很少有文獻(xiàn)提出在有向網(wǎng)絡(luò)中進(jìn)行社區(qū)檢測，因此對(duì)有向有權(quán)的復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)是一項(xiàng)艱巨而有意義的任務(wù)[5]。

2007年，Raghavan等[6]提出了一種標(biāo)簽傳播算法(LPA)，該算法是一種近似線性復(fù)雜度的社區(qū)發(fā)現(xiàn)算法，并且不需要預(yù)先知道社區(qū)的規(guī)模大小和所需要?jiǎng)澐值纳鐓^(qū)個(gè)數(shù)等，因此受到學(xué)者們的廣泛關(guān)注和應(yīng)用。但LPA在標(biāo)簽傳播過程中存在隨機(jī)性、振蕩、不穩(wěn)定，劃分社區(qū)效果差等缺點(diǎn)，為此大量研究人員進(jìn)行了相關(guān)研究。Sun等[7]提出了一種基于α-degree鄰域影響的標(biāo)簽傳播算法，緩解了節(jié)點(diǎn)更新中隨機(jī)更新的問題，提高了算法的穩(wěn)定性。Yan Xing等[8]提出了KBLPA和NIBLPA算法，該算法以K-shell算法為依據(jù)分析節(jié)點(diǎn)的重要性。易秀雙等[9]提出了一種基于頂點(diǎn)影響的局部社區(qū)發(fā)現(xiàn)算法，提高了算法的計(jì)算速度和效率。黃佳鑫等[10]在標(biāo)簽傳播的思想上綜合考慮了節(jié)點(diǎn)的重要性和標(biāo)簽的影響力，因此提高了原始標(biāo)簽傳播算法的穩(wěn)定性和準(zhǔn)確性。彭磊等[11]依據(jù)節(jié)點(diǎn)相似度進(jìn)行更新，提出了NSLPA算法。許合利等[12]提出了一種基于核心節(jié)點(diǎn)的加權(quán)網(wǎng)絡(luò)中的局部檢測算法CRD-LPA。但是以上這些算法大多數(shù)是基于無向圖的，因此失去了一些有用的信息，只對(duì)社區(qū)檢測結(jié)果進(jìn)行定量分析。

文中考慮邊的方向和權(quán)值，將標(biāo)簽傳播思想應(yīng)用于有向加權(quán)網(wǎng)絡(luò)，并且通過加權(quán)的ClusterRank獲得節(jié)點(diǎn)重要性列表，以避免LPA中的隨機(jī)選擇。其次，采用Jaccard系數(shù)度量節(jié)點(diǎn)的相似度，結(jié)合節(jié)點(diǎn)重要性列表計(jì)算出一個(gè)新的度量CRJ(重要度和相似度)，提高算法的穩(wěn)定性和社區(qū)發(fā)現(xiàn)質(zhì)量。

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

標(biāo)簽傳播算法是一種接近線性復(fù)雜度的社區(qū)發(fā)現(xiàn)算法，其基本思想是用已知節(jié)點(diǎn)標(biāo)簽信息預(yù)測未知節(jié)點(diǎn)的標(biāo)簽。

具體算法描述如下：

(1)將所有節(jié)點(diǎn)的標(biāo)簽初始化為唯一值，例如初始化節(jié)點(diǎn)標(biāo)簽為其ID號(hào)。

(2)隨機(jī)地對(duì)圖中的所有節(jié)點(diǎn)進(jìn)行排序。

(3)根據(jù)步驟2按順序更新每個(gè)節(jié)點(diǎn)，將節(jié)點(diǎn)的標(biāo)簽更新為鄰居中出現(xiàn)次數(shù)最多的標(biāo)簽；若當(dāng)個(gè)數(shù)最多的標(biāo)簽不唯一時(shí)，隨機(jī)選一個(gè)標(biāo)簽賦給當(dāng)前節(jié)點(diǎn)。

(4)如果網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的標(biāo)簽均穩(wěn)定不變，則算法終止。否則，返回步驟2繼續(xù)。

基于標(biāo)簽傳播算法的社區(qū)檢測的具體過程如圖1所示。

圖1 基于LPA的標(biāo)簽傳播過程

在圖1中有四個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)ID為1,2,3,4，它們的標(biāo)簽被初始化為A，B，C和D。

在標(biāo)簽傳播過程中，節(jié)點(diǎn)1的標(biāo)簽隨機(jī)選擇為節(jié)點(diǎn)4的標(biāo)簽D后，與節(jié)點(diǎn)2相鄰的節(jié)點(diǎn)中，標(biāo)簽D的數(shù)量最多，因此節(jié)點(diǎn)2的標(biāo)簽也設(shè)置為D，這樣的過程不斷持續(xù)下去，直到所有可能聚集到一起的節(jié)點(diǎn)都具有了相同的社區(qū)標(biāo)簽，此時(shí)圖1中所有節(jié)點(diǎn)的標(biāo)簽都變成了D，所有節(jié)點(diǎn)都已達(dá)到算法的終止然后退出循環(huán)。

標(biāo)簽的更新策略分為:同步更新和異步更新。同步更新是指對(duì)于節(jié)點(diǎn)x，在第t代時(shí)，根據(jù)其鄰居在t-1代時(shí)的社區(qū)標(biāo)簽進(jìn)行更新。異步更新是指節(jié)點(diǎn)x，在第t代時(shí)，根據(jù)其鄰居最新的社區(qū)標(biāo)簽進(jìn)行更新。同步更新標(biāo)簽的方法對(duì)于二分或者近似二分的網(wǎng)絡(luò)來說，可能會(huì)導(dǎo)致標(biāo)簽的振蕩，所以選擇異步更新節(jié)點(diǎn)標(biāo)簽的方式。

LPA算法的隨機(jī)性有以下兩個(gè)方面的問題:

(1)節(jié)點(diǎn)更新順序的隨機(jī)性。每次迭代開始時(shí)，都需要重新隨機(jī)生成節(jié)點(diǎn)更新的順序。但是，這種隨機(jī)性的方法不僅可以產(chǎn)生最佳值，也可能會(huì)產(chǎn)生最差值，因此，增加了算法的不穩(wěn)定性。

(2)當(dāng)個(gè)數(shù)最多的標(biāo)簽不唯一時(shí)，標(biāo)簽選擇是隨機(jī)的。這種隨機(jī)性可能會(huì)使得算法的迭代次數(shù)增加，并且導(dǎo)致算法不穩(wěn)定，劃分出來的結(jié)果也會(huì)相對(duì)較差。

針對(duì)第1個(gè)問題，提出基于加權(quán)的ClusterRank算法獲得節(jié)點(diǎn)重要性列表來依次更新節(jié)點(diǎn)，避免隨機(jī)選擇；針對(duì)第2個(gè)問題，采用Jaccard系數(shù)度量節(jié)點(diǎn)的相似度，結(jié)合節(jié)點(diǎn)重要性列表計(jì)算出一個(gè)新的度量CRJ(重要度和相似度)，選擇度量值最高的標(biāo)簽進(jìn)行更新，提高算法的穩(wěn)定性和社區(qū)發(fā)現(xiàn)質(zhì)量。

2 CRJ-LPA：改進(jìn)的標(biāo)簽傳播算法

LPA的效率吸引了眾多學(xué)者和研究人員的關(guān)注和研究。有很多算法可以改善LPA的上述問題。NSLPA算法最大改進(jìn)之處在隨機(jī)選擇。如果有多個(gè)可選標(biāo)簽，則節(jié)點(diǎn)將選擇相似度的鄰居節(jié)點(diǎn)的標(biāo)簽，而不是隨機(jī)選擇。此方法在一定程度上避免了LPA的隨機(jī)性問題，

但仍存在逆流問題。CRD-LPA算法將ClusterRank系數(shù)與節(jié)點(diǎn)局部密度(local density of node，LDN)結(jié)合起來進(jìn)行節(jié)點(diǎn)更新。此方法提高了LPA的準(zhǔn)確性和穩(wěn)定性，但CRD函數(shù)降低了節(jié)點(diǎn)影響力相同的概率，仍存在隨機(jī)選擇的可能性，同時(shí)該算法也忽略了節(jié)點(diǎn)邊的方向性對(duì)結(jié)果的影響。

2.1 加權(quán)的ClusterRank算法

Chen等[13]根據(jù)節(jié)點(diǎn)的度和聚類系數(shù)對(duì)有向復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要性進(jìn)行了分析，并以此為基礎(chǔ)提出了ClusterRank算法。該算法在考慮節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的數(shù)量的同時(shí)，還考慮到聚類系數(shù)對(duì)網(wǎng)絡(luò)中信息傳播的巨大影響。ClusterRank算法是對(duì)LeaderRank和PageRank算法做了進(jìn)一步的優(yōu)化和改進(jìn)[14]，但是ClusterRank沒有考慮網(wǎng)絡(luò)中節(jié)點(diǎn)周圍的結(jié)構(gòu)信息和邊的權(quán)值，因此，無法有效地衡量有向加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性?？紤]到這個(gè)問題，文中結(jié)合含權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)強(qiáng)度的定義提出了基于加權(quán)的ClusterRank算法。

2.1.1 含權(quán)網(wǎng)絡(luò)中的節(jié)點(diǎn)強(qiáng)度

(1)

(2)

上面定義的缺點(diǎn)很明顯，忽視了節(jié)點(diǎn)的度，在網(wǎng)絡(luò)中往往存在節(jié)點(diǎn)的鄰居多而節(jié)點(diǎn)強(qiáng)度卻很小的情況。Garas等[15]提出了另一種節(jié)點(diǎn)強(qiáng)度的定義方式，即用節(jié)點(diǎn)的鄰居數(shù)量和邊權(quán)重共同表示節(jié)點(diǎn)的度值，更加細(xì)致地刻畫了節(jié)點(diǎn)的屬性。在這里，節(jié)點(diǎn)vi的強(qiáng)度為：

(3)

其中，ki為節(jié)點(diǎn)vi的度；wij為節(jié)點(diǎn)vi與其鄰居vj之間連邊的權(quán)值；α和β為自由參數(shù)，用來調(diào)節(jié)度和權(quán)值之間的比重。

2.1.2 含權(quán)的局部聚類系數(shù)

許多社交網(wǎng)絡(luò)把有向網(wǎng)絡(luò)從i到j(luò)的連接表示為j是i的追隨者，意味著j從i接收信息。將Γi表示為i的追隨者集合，即i的出邊集合，并且i的追隨者之間的相互作用密度可以用i的局部聚類系數(shù)表示。有向網(wǎng)絡(luò)的聚類系數(shù)定義為：

(4)

現(xiàn)有研究提出了計(jì)算適用于有向網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)的局部聚類系數(shù)的方法，但這些并不適用于加權(quán)定向網(wǎng)絡(luò)?？紤]到這一點(diǎn)，文中融合Garas等提出的節(jié)點(diǎn)強(qiáng)度概念和信息傳播的因素，定義了加權(quán)定向網(wǎng)絡(luò)上的局部聚類系數(shù)，如下所示：

(5)

2.1.3 含權(quán)的ClusterRank算法

對(duì)于ClusterRank只考慮節(jié)點(diǎn)的聚類系數(shù)，不適用于加權(quán)網(wǎng)絡(luò)的問題，提出了適用于加權(quán)定向網(wǎng)絡(luò)的ClusterRank算法。根據(jù)式5定義的加權(quán)定向網(wǎng)絡(luò)上的局部聚類系數(shù)，重新定義了節(jié)點(diǎn)vi的ClusterRank的評(píng)分si：

(6)

s.t.f(ci)=10-ci

其中，Γι是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合；wij是節(jié)點(diǎn)vi與節(jié)點(diǎn)vj直接相連的邊的權(quán)值；f(ci)是節(jié)點(diǎn)vi的聚類系數(shù)的函數(shù)。

在復(fù)雜網(wǎng)絡(luò)中，聚類系數(shù)越大，越會(huì)阻礙信息的傳播，因此隨著ci增大的f(ci)值將變小。

2.2 Jaccard相似度

在復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)之間通常具有一定的相似性，Jaccard為描述相似度的重要指標(biāo)。在包含節(jié)點(diǎn)集V和邊集E的圖G(V,E)中，節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的Jaccard相似度定義如下：

(7)

其中，Ni表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)的集合，Jaccard的值介于0～1之間，該值越接近1，表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的相似度越高。

在LPA算法中，即使通過文中提出的基于加權(quán)的ClusterRank算法進(jìn)行節(jié)點(diǎn)重要性排序后進(jìn)行標(biāo)簽的更新，仍然有可能會(huì)出現(xiàn)一定的隨機(jī)選擇。因此，定義了一種新的度量CRJ，通過綜合考慮節(jié)點(diǎn)重要性和相似性來提高LPA算法的準(zhǔn)確性，定義如下：

(8)

2.3 CRJ-LPA算法描述

針對(duì)有向加權(quán)網(wǎng)絡(luò)，基于原始的LPA算法，文中提出了一種基于節(jié)點(diǎn)重要性和相似性的改進(jìn)CRJ-LPA算法。該算法具體步驟如下：

Step1:初始化，根據(jù)節(jié)點(diǎn)ID為每個(gè)節(jié)點(diǎn)分配一個(gè)唯一的標(biāo)簽；

Step2:根據(jù)式6計(jì)算所有節(jié)點(diǎn)的重要性，并根據(jù)節(jié)點(diǎn)重要性由高到低對(duì)節(jié)點(diǎn)集合V進(jìn)行排序；

Step3:根據(jù)式7計(jì)算節(jié)點(diǎn)的相似度；

Step4:從節(jié)點(diǎn)集合V中依次取出節(jié)點(diǎn)進(jìn)行更新，并且優(yōu)先更新鄰居節(jié)點(diǎn)間具有最大影響力的節(jié)點(diǎn)，如果出現(xiàn)影響力相同的情況，則根據(jù)式8計(jì)算鄰居節(jié)點(diǎn)的CRJ(v,v')，然后將節(jié)點(diǎn)v的標(biāo)簽更新為具有最高CRJ(v,v')的鄰居節(jié)點(diǎn)v'的標(biāo)簽；其次，在標(biāo)簽更新過程中，如果節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中個(gè)數(shù)最多的標(biāo)簽出現(xiàn)兩個(gè)或多個(gè)時(shí)，同樣根據(jù)CRJ(v,v')來更新節(jié)點(diǎn)v的標(biāo)簽；

Step5:如果網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的標(biāo)簽均穩(wěn)定不變，則循環(huán)停止并退出算法。否則，跳轉(zhuǎn)到Step4繼續(xù)循環(huán)。

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

選取Lesmis與Celegansneural兩種國際上公認(rèn)的真實(shí)數(shù)據(jù)集，對(duì)CRJ-LPA算法進(jìn)行測試。算法的實(shí)驗(yàn)環(huán)境為Python3.5軟件，硬件配置為i5-3230M，RAM：4.00G；軟件配置:64 位WIN7操作系統(tǒng)。

3.1 有向加權(quán)網(wǎng)絡(luò)模塊度

文獻(xiàn)[13]中Newman和Girvan提出了模塊度的概念，后來作為衡量社區(qū)算法性能的公認(rèn)評(píng)價(jià)標(biāo)準(zhǔn)。再后來，Newman等將其拓展到有向、加權(quán)網(wǎng)絡(luò)上[16]，定義如下：

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

數(shù)據(jù)集Lesmis與Celegansneural是兩種有向有權(quán)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集，其基本信息如表1所示。

表1 真實(shí)復(fù)雜的網(wǎng)絡(luò)數(shù)據(jù)集信息

在這兩種真實(shí)數(shù)據(jù)集上對(duì)算法進(jìn)行分析與驗(yàn)證，并且根據(jù)模塊度來衡量算法劃分的社區(qū)結(jié)構(gòu)的優(yōu)劣。同時(shí)，將文中算法CRJ-LPA與傳統(tǒng)LPA算法(如LPA、NSLPA、KBLPA算法)進(jìn)行比較。不同算法分別在數(shù)據(jù)集上進(jìn)行運(yùn)算后的模塊度如表2所示。

表2 算法模塊度的比較

通過對(duì)表2中的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析可以看出，與傳統(tǒng)的LPA、NSLPA、KBLPA算法相比，文中算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)的平均模塊度最大。從上述精準(zhǔn)的數(shù)字描述可以看出，文中算法在這兩種有向有權(quán)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上比傳統(tǒng)LPA等算法在性能上有明顯提升，且模塊度的值均在良好社區(qū)結(jié)構(gòu)的模塊度區(qū)間[0.3,0.7]范圍內(nèi)。因此，文中算法劃分的社區(qū)結(jié)構(gòu)良好，且算法準(zhǔn)確性和穩(wěn)定性較高。文中算法與LPA算法對(duì)Lesmis數(shù)據(jù)集劃分的結(jié)果如圖2與圖3所示。

圖2和圖3將位于不同社區(qū)的節(jié)點(diǎn)用直線分隔開，并且通過兩幅圖的對(duì)比可以得出，文中算法發(fā)現(xiàn)的社區(qū)較傳統(tǒng)LPA算法所得社區(qū)數(shù)量多，且較為穩(wěn)定，沒有超大社區(qū)。

4 結(jié)束語

針對(duì)有向加權(quán)網(wǎng)絡(luò)，提出了一種基于節(jié)點(diǎn)重要性和節(jié)點(diǎn)相似性的改進(jìn)標(biāo)簽傳播算法(CRJ-LPA)。該算法綜合考慮了復(fù)雜網(wǎng)絡(luò)中邊的權(quán)值和方向性，并且采用標(biāo)簽傳播的思想進(jìn)行社區(qū)發(fā)現(xiàn)。首先，通過有向加權(quán)的ClusterRank算法獲得節(jié)點(diǎn)的重要性排序列表，然后根據(jù)此順序更新節(jié)點(diǎn)標(biāo)簽，提高社區(qū)結(jié)構(gòu)的劃分質(zhì)量；其次，在節(jié)點(diǎn)更新過程通過節(jié)點(diǎn)重要性和相似性計(jì)算出一個(gè)新的度量CRJ，以此來避免原始LPA中的隨機(jī)選擇，有效克服了傳統(tǒng)標(biāo)簽傳播算法的隨機(jī)性。通過真實(shí)數(shù)據(jù)集對(duì)算法進(jìn)行測試，發(fā)現(xiàn)該算法具有較好的可行性和準(zhǔn)確性，能夠準(zhǔn)確地衡量節(jié)點(diǎn)的重要性，而且與LPA算法具有相似的時(shí)間復(fù)雜度。

圖2 文中算法效果

圖3 LPA算法效果