拓撲結構與節點屬性綜合分析的社區發現算法

張振宇，朱培棟，王 可，胡慧俐

(國防科學技術大學 計算機學院，湖南 長沙 410073)

0 引 言

20世紀90年代以來，國際互聯網、社交網絡、新陳代謝網絡、電力網絡、交通網絡、腦細胞網絡等使得人們生活的世界處于各種不同類型的復雜網絡之中，對各類復雜網絡性質的研究隨之成為必要。社交網絡中社區結構的發現，不僅有助于網絡功能的發掘、網絡內部連接層次的識別、社交網絡上復雜用戶行為及群體行為的理解[1]，同時其分析理論也廣泛應用于其他學科。

現有的一些經典社區發現算法，如GN算法、FastNewman算法、遺傳算法、系派過濾法、紐帶社區等，均只是基于網絡拓撲結構[2]進行社區發現。但是，社交網絡節點往往蘊含豐富的屬性信息，這些信息對社區結構的形成具有重要影響，目前帶有節點屬性的社區發現，如基于隨機游走的邊權值節點屬性相似度NAS算法[3]，衡量拓撲結構和節點屬性的距離概念[4]，邊穩定稀疏模型[5]，聯合拓撲和屬性的分析[6]，這些均將節點屬性作為影響因素進行了考慮，但都沒有很好地解決兩者之間的相關關系，使其聯合分析無可避免地產生相關性誤差。目前聯合拓撲結構和節點屬性的社區發現技術有待進一步深入分析。

文中綜合考慮社交網絡中的拓撲結構和節點屬性，通過對兩因素進行去相關性操作和賦權處理，從而建立社交網絡的社區距離關系矩陣，最后針對得到的關系矩陣，設計一種依據模糊關系相關原理的社區發現算法。該算法具有較高的社區發現準確率，并通過不同閾值的選定能得到多層次社區結構[7]，解決社區層次性問題。

1 問題描述

對社交網絡進行精準的描述是社區發現的基礎?？捎脠D結構對社交網絡進行描述，用WG=(V,E,W,S)表示社交網絡[8]，其中V為圖節點集合，表示人；E為圖邊集合，表示人與人之間的社交關系；W為圖邊權值，表示關系的強弱；S為圖節點信息，表示人對應的屬性信息。

社區結構是一種網絡拓撲特性，刻畫了連邊關系的局部聚類特性。為了發現或識別社區結構，如果能夠判定任意兩個節點是否處于同一社區，那么該社區結構也就唯一確定。用矩陣描述為P=[pij]n×n，其中pij∈{0,1}，0表示對應兩人處于不同社區，1表示對應兩人處于相同社區。需要指出的是：每個人和自己必定處于相同社區；如果A與B處于相同社區，那么B與A也處于相同社區，反之亦然；如果A與C處于相同社區，B與C也處于相同社區，那么B與C亦處于相同社區。

將上述三個條件符號化：矩陣P中，若pii=1，即滿足自反性；若pij=pji，即滿足對稱性；若pij=1，pjk=1，則有pik=1，即滿足傳遞性。故反映社區結構的矩陣P是普通等價矩陣。

由此，可將問題進行如下描述：

f(W,S)=P

(1)

其中，W表示網絡拓撲結構；S表示網絡節點屬性；P表示社區結構，為普通等價矩陣；函數f表示網絡拓撲結構和節點屬性到社區結構的映射關系，即為所求。

2 網絡社區距離

從社交網絡的拓撲結構和節點屬性出發得到社交網絡的社區結構。為避免社區發現結果受影響因子間相關性的影響，本節對影響因子進行去相關性分析；同時，基于設計的穩定性賦權方法綜合拓撲結構和節點屬性。

2.1 拓撲結構與節點屬性的相關性分析

對于節點屬性，同社區的屬性相似度相對較高，不同社區的屬性相似度相對較低，因此，相較于屬性值，屬性相似性更能體現網絡的社區情況。文中用歐氏距離描述屬性相似性。

綜合拓撲結構和節點屬性進行社區結構發現時，兩者之間的相關性容易為后面的綜合討論帶來疊加效應[3]。目前社交網絡中關系的量化并沒有形成統一的標準，量化誤差會使得關系數據偏離理論上的正態分布；節點屬性的量化賦值方法具有極大的主觀性，使得屬性總體分布類型未知。因此，采用Spearman相關系數對兩者之間的相關性進行度量。Spearman相關系數用于對不服從正態分布的數據、總體分布類型未知的數據的關聯性進行描述。

取X和Y兩個集合對應表示矩陣W和N中的數值，Xi、Yi為對應集合中的第i(0

(2)

基于上述分析，通過如下操作進行相似性和去相關性處理：

(3)

(4)

此時，對于問題的求解，得到如下過程：

f1(W,S)=(W,N)

(5)

其中，W為關系強度矩陣；S為網絡節點屬性矩陣；N為強度無關屬性矩陣；函數f1為相關性剔除函數，是函數f的分函數。

2.2 網絡社區距離指數

所研究問題的難點在于如何確定兩影響因素對社區結構的影響程度。針對不相關變量的綜合處理，目前有多種解決方法，但是，大部分方法中的權重需要主觀賦予，而社交網絡很難從機理的角度得到二者對社區結構之間的影響權重，故該類方法對于本問題具有較大主觀性。

(6)

前文只分析了兩節點間的直接關系對社區結構形成的影響，而社區結構其內部節點的聚類系數很高，社區聚類系數由節點間的間接關系反映。因此，把節點間的間接關系作為社區結構形成的另一影響因素，同時，由于社交網絡的小世界性，認為三度(及以上)鄰居關系的影響較小。用該對節點與其他節點的距離的差方和來衡量兩度鄰居的影響因子：

(7)

(8)

文中提出“社區距離”的概念[9]。根據以上分析，綜合穩定性賦權和聚類系數操作，根據式(6)～(8)提出反映兩節點的社區情況的社區距離，定義如下：

(9)

其中，σN為矩陣N元素的方差；σW為矩陣W元素的方差；lij為節點i與節點j之間的社區距離。得到社區距離矩陣L=[lij]n×n。

此時，對于問題的求解，得到如下過程：

f3(W,N)=L

(10)

其中，W為關系強度矩陣；N為強度無關屬性矩陣；L為網絡社區距離矩陣；函數f3為社區距離函數，是函數f的分函數。

3 基于模糊關系的社區發現

文中最終要得到的社區結構是一種普通等價關系，而社區距離矩陣L也是一種關系的表現，因此，文中社區發現的過程實質是關系變換的過程，即從普通關系變換為等價關系。本節基于模糊關系相關理論對網絡數據進行分析，從而進行社區發現。

3.1 社區距離的模糊等價化

將社區距離矩陣Ln×n表示為節點集V×V中的模糊關系。在該模糊關系中[10]，lij∈[0,1]，lii=0，lij=lji，此模糊關系只滿足對稱性。

欲使關系滿足自反性，令lii=1，此時，lij∈[0,1]，lij=lji，lii=1，該矩陣同時滿足對稱性、自反性，為模糊相似矩陣。

此時，對于問題的求解，得到如下過程：

f4(L)=Ln-1

(11)

其中，L為網絡社區距離矩陣；Ln-1為L的n-1次max-min乘積[13]；函數f4為模糊傳遞閉包函數，是函數f的分函數。

3.2 模糊關系確定化

文中需要得到能反映社區結構的普通等價矩陣,模糊數學中的截關系運算可以完成。令L是V×V中的模糊關系，對任意α∈[0,1]，其α截關系Lα的特征函數為：

(12)

由此，在沒有改變關系的等價性的前提下，模糊關系轉化為確定關系，最終得到明確的節點劃分關系—社區結構。有必要指出：基于不同的截取值，會有不同的社區結構，即該社區發現具有多層次性。

此時，對于問題的求解，得到如下過程：

f5(Ln-1)=P

(13)

其中，P為社區結構矩陣；函數f5為截運算函數，是函數f的分函數。

4 算法描述

從拓撲結構和節點屬性出發，對該影響因素進行相關性分析、權值賦予討論，通過模糊關系相關理論進行社區發現，給出一種新的社區結構發現方法，算法模型如下：

f(W,S)=f4(f3(f2(f1(W,S))))=P

(14)

其中，W表示網絡拓撲結構；S表示網絡節點屬性；P表示社區結構；f1為相關性剔除函數；f2為社區距離函數；f3為模糊傳遞閉包函數；f4為截運算函數。

文中社區發現模糊算法的具體描述如下：

輸入：連接矩陣W，屬性矩陣S

輸出：社區結構P

2.defineD=排序差分(W,N')

3.defineρ=Spearman相關系數(D)

5.for(i,j雙循環)

6.for(n次循環)defineλij=λij+[1-(wik-wjk)]2/n

7.defineγij=γij+[1-(nik-njk)]2/n； //三度鄰居關系

8.defineσW=(W的方差)；σN=(N的方差)；

9.σW=σN/(σW+σN)；σN=σW/(σW+σN) //基于穩定性賦權

10.for(i,j雙循環)

11.definelij=σWλijwij+σNγijnij//綜合權值擬合

12.for(n-1次循環)

13.for(i,j雙循環)

15.define(α=input)

17.elsepij=0 //模糊截關系處理

18.if(P==預期) over //社區層次性選擇

19.else 返回(15)

20.returnP

算法流程如圖1所示。從社交網絡出發，得到社交網絡中反映拓撲結構的關系矩陣和反映節點屬性的屬性矩陣；對屬性矩陣進行相似性變換得到屬性相似性矩陣；對關系矩陣和屬性相似性矩陣進行相關性分析得到修正關系矩陣和修正相似性矩陣；對兩修正矩陣進行賦權處理得到社區距離矩陣；對社區距離矩陣進行模糊傳遞閉包處理得到模糊等價矩陣；進而基于截關系得到能夠反映社區結構的普通等價矩陣。

圖1 算法流程

5 算法實現與分析

文中算法與各經典算法基于不同的數據集進行比較分析?；贖OT模型[14]得到網絡模擬數據，社區評價指標為模塊度與NMI[15]。模塊度是社區內部的總邊數和網絡中總邊數的比例減去一個期望值，用于在不知道網絡真實劃分的情況下量化或評判的社區劃分水平。NMI是歸一化互信息，用于衡量算法劃分結果和真實結果的重合程度；通過模擬數據集進行實驗；基于不同社區參數和網絡規模下[16]的社交網絡進行實驗結果以及時間復雜度比較如圖2～4及表1所示。

圖2 不同社區度網絡下各算法的模塊度

圖3 不同社區度網絡下各算法模塊度NMI

圖4 不同規模網絡下社區模塊度

表1 各算法時間復雜度

由圖2可以看到，不同社區參數下，文中算法得到的社區結構的模塊度較高，且對社區參數不敏感；由圖3可以看到，不同社區參數下，文中算法得到的社區結構的NMI較高，且對社區參數較敏感，社區參數較大時下降較快；由圖4可以看到，不同網絡規模下，文中算法得到的社區結構的模塊度低于遺傳算法但均好于其他算法，且對網絡規模相對不敏感；由表1可以看到，文中算法時間復雜度相對較高，不太適用于大規模網絡分析，這也是后續工作中應該關注和改進的方向。

由此，相比各算法，文中算法時間復雜度相對較高，算法準確率高且穩定，對網絡規模和網絡聚類性不敏感，具有較高的準確性，適用于小型網絡、中型網絡以及對時間要求不高的大型網絡的社區發現。

6 結束語

從包含拓撲結構和節點屬性的完備信息集出發，通過相似性運算、去相關性運算、賦權運算等操作進行數據前期處理；基于模糊傳遞閉包思想進行社區結構的發現，通過截運算得到社區結構；最終實現了社交網絡的社區發現，同時一定程度上解決了社區層次性的問題，緩解了網絡動態性帶來的影響。

該算法基于網絡拓撲結構和節點屬性信息，增強了信息完備度；設計的穩定賦權法和Spearman相關系數的引入解決了信息干擾問題；社區距離概念的提出和模糊關系理論的導入提升了社區發現的精度和穩定性。

參考文獻:

[1] AHN Y Y,BAGROW J P,LEHMANN S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.

[2] 劉大有,金 弟,何東曉,等.復雜網絡社區挖掘綜述[J].計算機研究與發展,2013,50(10):2140-2154.

[3] STEINHAEUSER K,CHAWLA N V.Identifying and evaluating community structure in complex networks[J].Pattern Recognition Letters,2010,31(5):413-421.

[4] ZHOU Y,CHENG H,YU J X. Graph clustering based on structural/attribute similarities[J].Proceedings of the VLDB Endowment,2009,2(1):718-729.

[5] 林友芳,王天宇,唐 銳,等.一種有效的社會網絡社區發現模型和算法[J].計算機研究與發展,2012,49(2):337-345.

[6] 郭進時,湯紅波,葛國棟.一種聯合拓撲與屬性的社區模糊劃分算法[J].計算機工程,2013,39(11):35-40.

[7] 王 莉,程學旗.在線社會網絡的動態社區發現及演化[J].計算機學報，2015，38(2)：219-237.

[8] 于 海,趙玉麗,崔 坤,等.一種基于交叉熵的社區發現算法[J].計算機學報，2015，38(8):1574-1581.

[9] HU R J,LI Q,ZHANG G Y,et al.Centrality measures in directed fuzzy social networks[J].Fuzzy Information and Engineering,2015,7(1):115-128.

[10] 范艷煥,耿生玲,李永明.Pebble模糊有窮自動機和傳遞閉包邏輯[J].模糊系統與數學,2015,29(4):38-44.

[11] 李秀格,朱紅寧.求模糊相似矩陣的傳遞閉包的簡捷算法[J].電腦知識與技術，2014,10(26):6161-6164.

[12] PARAND F A,RAHIMI H,GORZIN M.Combining fuzzy logic and eigenvector centrality measure in social network analysis[J].Physica A:Statistical Mechanics and Its Applications,2015,459:24-31.

[13] RAJ E D,BABU L D D.A fuzzy adaptive resonance theory inspired over lapping community detection method for online social networks[J].Knowledge-Based Systems,2016,113:75-87.

[14] 吳增海.社交網絡模型的研究[D].合肥:中國科學技術大學,2012.

[15] 王 林,戴冠中,趙煥成.一種新的評價社區結構的模塊度研究[J].計算機工程,2010,36(14):227-229.

[16] 岳 訓,遲忠先,莫宏偉,等.基于網絡社區模塊結構的特征選擇性能評價[J].計算機工程,2007,33(12):16-18.