基于復雜網絡的社區發現算法研究

孟彩霞，李楠楠，張 琰

(西安郵電大學 計算機學院，陜西 西安 700121)

0 引 言

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

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

文中考慮邊的方向和權值，將標簽傳播思想應用于有向加權網絡，并且通過加權的ClusterRank獲得節點重要性列表，以避免LPA中的隨機選擇。其次，采用Jaccard系數度量節點的相似度，結合節點重要性列表計算出一個新的度量CRJ(重要度和相似度)，提高算法的穩定性和社區發現質量。

1 標簽傳播算法

標簽傳播算法是一種接近線性復雜度的社區發現算法，其基本思想是用已知節點標簽信息預測未知節點的標簽。

具體算法描述如下：

(1)將所有節點的標簽初始化為唯一值，例如初始化節點標簽為其ID號。

(2)隨機地對圖中的所有節點進行排序。

(3)根據步驟2按順序更新每個節點，將節點的標簽更新為鄰居中出現次數最多的標簽；若當個數最多的標簽不唯一時，隨機選一個標簽賦給當前節點。

(4)如果網絡中的所有節點的標簽均穩定不變，則算法終止。否則，返回步驟2繼續。

基于標簽傳播算法的社區檢測的具體過程如圖1所示。

圖1 基于LPA的標簽傳播過程

在圖1中有四個節點，每個節點ID為1,2,3,4，它們的標簽被初始化為A，B，C和D。

在標簽傳播過程中，節點1的標簽隨機選擇為節點4的標簽D后，與節點2相鄰的節點中，標簽D的數量最多，因此節點2的標簽也設置為D，這樣的過程不斷持續下去，直到所有可能聚集到一起的節點都具有了相同的社區標簽，此時圖1中所有節點的標簽都變成了D，所有節點都已達到算法的終止然后退出循環。

標簽的更新策略分為:同步更新和異步更新。同步更新是指對于節點x，在第t代時，根據其鄰居在t-1代時的社區標簽進行更新。異步更新是指節點x，在第t代時，根據其鄰居最新的社區標簽進行更新。同步更新標簽的方法對于二分或者近似二分的網絡來說，可能會導致標簽的振蕩，所以選擇異步更新節點標簽的方式。

LPA算法的隨機性有以下兩個方面的問題:

(1)節點更新順序的隨機性。每次迭代開始時，都需要重新隨機生成節點更新的順序。但是，這種隨機性的方法不僅可以產生最佳值，也可能會產生最差值，因此，增加了算法的不穩定性。

(2)當個數最多的標簽不唯一時，標簽選擇是隨機的。這種隨機性可能會使得算法的迭代次數增加，并且導致算法不穩定，劃分出來的結果也會相對較差。

針對第1個問題，提出基于加權的ClusterRank算法獲得節點重要性列表來依次更新節點，避免隨機選擇；針對第2個問題，采用Jaccard系數度量節點的相似度，結合節點重要性列表計算出一個新的度量CRJ(重要度和相似度)，選擇度量值最高的標簽進行更新，提高算法的穩定性和社區發現質量。

2 CRJ-LPA：改進的標簽傳播算法

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

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

2.1 加權的ClusterRank算法

Chen等[13]根據節點的度和聚類系數對有向復雜網絡的節點重要性進行了分析，并以此為基礎提出了ClusterRank算法。該算法在考慮節點的鄰居節點的數量的同時，還考慮到聚類系數對網絡中信息傳播的巨大影響。ClusterRank算法是對LeaderRank和PageRank算法做了進一步的優化和改進[14]，但是ClusterRank沒有考慮網絡中節點周圍的結構信息和邊的權值，因此，無法有效地衡量有向加權網絡中節點的重要性。考慮到這個問題，文中結合含權網絡中節點強度的定義提出了基于加權的ClusterRank算法。

2.1.1 含權網絡中的節點強度

(1)

(2)

上面定義的缺點很明顯，忽視了節點的度，在網絡中往往存在節點的鄰居多而節點強度卻很小的情況。Garas等[15]提出了另一種節點強度的定義方式，即用節點的鄰居數量和邊權重共同表示節點的度值，更加細致地刻畫了節點的屬性。在這里，節點vi的強度為：

(3)

其中，ki為節點vi的度；wij為節點vi與其鄰居vj之間連邊的權值；α和β為自由參數，用來調節度和權值之間的比重。

2.1.2 含權的局部聚類系數

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

(4)

現有研究提出了計算適用于有向網絡和加權網絡的局部聚類系數的方法，但這些并不適用于加權定向網絡。考慮到這一點，文中融合Garas等提出的節點強度概念和信息傳播的因素，定義了加權定向網絡上的局部聚類系數，如下所示：

(5)

2.1.3 含權的ClusterRank算法

對于ClusterRank只考慮節點的聚類系數，不適用于加權網絡的問題，提出了適用于加權定向網絡的ClusterRank算法。根據式5定義的加權定向網絡上的局部聚類系數，重新定義了節點vi的ClusterRank的評分si：

(6)

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

其中，Γι是節點vi的鄰居節點集合；wij是節點vi與節點vj直接相連的邊的權值；f(ci)是節點vi的聚類系數的函數。

在復雜網絡中，聚類系數越大，越會阻礙信息的傳播，因此隨著ci增大的f(ci)值將變小。

2.2 Jaccard相似度

在復雜網絡中，節點之間通常具有一定的相似性，Jaccard為描述相似度的重要指標。在包含節點集V和邊集E的圖G(V,E)中，節點vi和節點vj之間的Jaccard相似度定義如下：

(7)

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

在LPA算法中，即使通過文中提出的基于加權的ClusterRank算法進行節點重要性排序后進行標簽的更新，仍然有可能會出現一定的隨機選擇。因此，定義了一種新的度量CRJ，通過綜合考慮節點重要性和相似性來提高LPA算法的準確性，定義如下：

(8)

2.3 CRJ-LPA算法描述

針對有向加權網絡，基于原始的LPA算法，文中提出了一種基于節點重要性和相似性的改進CRJ-LPA算法。該算法具體步驟如下：

Step1:初始化，根據節點ID為每個節點分配一個唯一的標簽；

Step2:根據式6計算所有節點的重要性，并根據節點重要性由高到低對節點集合V進行排序；

Step3:根據式7計算節點的相似度；

Step4:從節點集合V中依次取出節點進行更新，并且優先更新鄰居節點間具有最大影響力的節點，如果出現影響力相同的情況，則根據式8計算鄰居節點的CRJ(v,v')，然后將節點v的標簽更新為具有最高CRJ(v,v')的鄰居節點v'的標簽；其次，在標簽更新過程中，如果節點的鄰居節點中個數最多的標簽出現兩個或多個時，同樣根據CRJ(v,v')來更新節點v的標簽；

Step5:如果網絡中的所有節點的標簽均穩定不變，則循環停止并退出算法。否則，跳轉到Step4繼續循環。

3 實驗結果與分析

選取Lesmis與Celegansneural兩種國際上公認的真實數據集，對CRJ-LPA算法進行測試。算法的實驗環境為Python3.5軟件，硬件配置為i5-3230M，RAM：4.00G；軟件配置:64 位WIN7操作系統。

3.1 有向加權網絡模塊度

文獻[13]中Newman和Girvan提出了模塊度的概念，后來作為衡量社區算法性能的公認評價標準。再后來，Newman等將其拓展到有向、加權網絡上[16]，定義如下：

3.2 實驗結果

數據集Lesmis與Celegansneural是兩種有向有權復雜網絡數據集，其基本信息如表1所示。

表1 真實復雜的網絡數據集信息

在這兩種真實數據集上對算法進行分析與驗證，并且根據模塊度來衡量算法劃分的社區結構的優劣。同時，將文中算法CRJ-LPA與傳統LPA算法(如LPA、NSLPA、KBLPA算法)進行比較。不同算法分別在數據集上進行運算后的模塊度如表2所示。

表2 算法模塊度的比較

通過對表2中的實驗數據進行分析可以看出，與傳統的LPA、NSLPA、KBLPA算法相比，文中算法發現的社區結構的平均模塊度最大。從上述精準的數字描述可以看出，文中算法在這兩種有向有權復雜網絡數據集上比傳統LPA等算法在性能上有明顯提升，且模塊度的值均在良好社區結構的模塊度區間[0.3,0.7]范圍內。因此，文中算法劃分的社區結構良好，且算法準確性和穩定性較高。文中算法與LPA算法對Lesmis數據集劃分的結果如圖2與圖3所示。

圖2和圖3將位于不同社區的節點用直線分隔開，并且通過兩幅圖的對比可以得出，文中算法發現的社區較傳統LPA算法所得社區數量多，且較為穩定，沒有超大社區。

4 結束語

針對有向加權網絡，提出了一種基于節點重要性和節點相似性的改進標簽傳播算法(CRJ-LPA)。該算法綜合考慮了復雜網絡中邊的權值和方向性，并且采用標簽傳播的思想進行社區發現。首先，通過有向加權的ClusterRank算法獲得節點的重要性排序列表，然后根據此順序更新節點標簽，提高社區結構的劃分質量；其次，在節點更新過程通過節點重要性和相似性計算出一個新的度量CRJ，以此來避免原始LPA中的隨機選擇，有效克服了傳統標簽傳播算法的隨機性。通過真實數據集對算法進行測試，發現該算法具有較好的可行性和準確性，能夠準確地衡量節點的重要性，而且與LPA算法具有相似的時間復雜度。

圖2 文中算法效果

圖3 LPA算法效果