拓撲結構與節(jié)點屬性綜合分析的社區(qū)發(fā)現(xiàn)算法

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

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

0 引 言

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

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

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

1 問題描述

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

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

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

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

f(W,S)=P

(1)

其中，W表示網(wǎng)絡拓撲結構；S表示網(wǎng)絡節(jié)點屬性；P表示社區(qū)結構，為普通等價矩陣；函數(shù)f表示網(wǎng)絡拓撲結構和節(jié)點屬性到社區(qū)結構的映射關系，即為所求。

2 網(wǎng)絡社區(qū)距離

從社交網(wǎng)絡的拓撲結構和節(jié)點屬性出發(fā)得到社交網(wǎng)絡的社區(qū)結構。為避免社區(qū)發(fā)現(xiàn)結果受影響因子間相關性的影響，本節(jié)對影響因子進行去相關性分析；同時，基于設計的穩(wěn)定性賦權方法綜合拓撲結構和節(jié)點屬性。

2.1 拓撲結構與節(jié)點屬性的相關性分析

對于節(jié)點屬性，同社區(qū)的屬性相似度相對較高，不同社區(qū)的屬性相似度相對較低，因此，相較于屬性值，屬性相似性更能體現(xiàn)網(wǎng)絡的社區(qū)情況。文中用歐氏距離描述屬性相似性。

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

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

(2)

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

(3)

(4)

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

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

(5)

其中，W為關系強度矩陣；S為網(wǎng)絡節(jié)點屬性矩陣；N為強度無關屬性矩陣；函數(shù)f1為相關性剔除函數(shù)，是函數(shù)f的分函數(shù)。

2.2 網(wǎng)絡社區(qū)距離指數(shù)

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

(6)

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

(7)

(8)

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

(9)

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

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

f3(W,N)=L

(10)

其中，W為關系強度矩陣；N為強度無關屬性矩陣；L為網(wǎng)絡社區(qū)距離矩陣；函數(shù)f3為社區(qū)距離函數(shù)，是函數(shù)f的分函數(shù)。

3 基于模糊關系的社區(qū)發(fā)現(xiàn)

文中最終要得到的社區(qū)結構是一種普通等價關系，而社區(qū)距離矩陣L也是一種關系的表現(xiàn)，因此，文中社區(qū)發(fā)現(xiàn)的過程實質是關系變換的過程，即從普通關系變換為等價關系。本節(jié)基于模糊關系相關理論對網(wǎng)絡數(shù)據(jù)進行分析，從而進行社區(qū)發(fā)現(xiàn)。

3.1 社區(qū)距離的模糊等價化

將社區(qū)距離矩陣Ln×n表示為節(jié)點集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為網(wǎng)絡社區(qū)距離矩陣；Ln-1為L的n-1次max-min乘積[13]；函數(shù)f4為模糊傳遞閉包函數(shù)，是函數(shù)f的分函數(shù)。

3.2 模糊關系確定化

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

(12)

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

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

f5(Ln-1)=P

(13)

其中，P為社區(qū)結構矩陣；函數(shù)f5為截運算函數(shù)，是函數(shù)f的分函數(shù)。

4 算法描述

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

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

(14)

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

文中社區(qū)發(fā)現(xiàn)模糊算法的具體描述如下：

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

輸出：社區(qū)結構P

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

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

5.for(i,j雙循環(huán))

6.for(n次循環(huá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) //基于穩(wěn)定性賦權

10.for(i,j雙循環(huán))

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

12.for(n-1次循環(huán))

13.for(i,j雙循環(huán))

15.define(α=input)

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

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

19.else 返回(15)

20.returnP

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

圖1 算法流程

5 算法實現(xiàn)與分析

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

圖2 不同社區(qū)度網(wǎng)絡下各算法的模塊度

圖3 不同社區(qū)度網(wǎng)絡下各算法模塊度NMI

圖4 不同規(guī)模網(wǎng)絡下社區(qū)模塊度

表1 各算法時間復雜度

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

由此，相比各算法，文中算法時間復雜度相對較高，算法準確率高且穩(wěn)定，對網(wǎng)絡規(guī)模和網(wǎng)絡聚類性不敏感，具有較高的準確性，適用于小型網(wǎng)絡、中型網(wǎng)絡以及對時間要求不高的大型網(wǎng)絡的社區(qū)發(fā)現(xiàn)。

6 結束語

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

該算法基于網(wǎng)絡拓撲結構和節(jié)點屬性信息，增強了信息完備度；設計的穩(wěn)定賦權法和Spearman相關系數(shù)的引入解決了信息干擾問題；社區(qū)距離概念的提出和模糊關系理論的導入提升了社區(qū)發(fā)現(xiàn)的精度和穩(wěn)定性。

參考文獻:

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

[2] 劉大有,金 弟,何東曉,等.復雜網(wǎng)絡社區(qū)挖掘綜述[J].計算機研究與發(fā)展,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] 林友芳,王天宇,唐 銳,等.一種有效的社會網(wǎng)絡社區(qū)發(fā)現(xiàn)模型和算法[J].計算機研究與發(fā)展,2012,49(2):337-345.

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

[7] 王 莉,程學旗.在線社會網(wǎng)絡的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J].計算機學報，2015，38(2)：219-237.

[8] 于 海,趙玉麗,崔 坤,等.一種基于交叉熵的社區(qū)發(fā)現(xiàn)算法[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].模糊系統(tǒng)與數(shù)學,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] 吳增海.社交網(wǎng)絡模型的研究[D].合肥:中國科學技術大學,2012.

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

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