復雜網(wǎng)絡交疊團模糊分析與信息挖掘

1、<p>　　復雜網(wǎng)絡交疊團模糊分析與信息挖掘</p><p>　　摘 要:針對復雜網(wǎng)絡交疊團的聚類與模糊分析方法設計問題,給出一種新的模糊度量及相應的模糊聚類方法,并以新度量為基礎,設計出兩種挖掘網(wǎng)絡模糊拓撲特征的新指標:團間連接緊密程度和模糊點對交疊團的連接貢獻度,并將其用于網(wǎng)絡交疊模塊拓撲結構宏觀分析和團間關鍵點提取。實驗結果表明,使用該聚類與分析方法不僅可以獲得模糊團結構,而且能夠揭示出新的網(wǎng)絡特

2、征。該方法為復雜網(wǎng)絡聚類后分析提供了新的視角。 </p><p>　　針對復雜網(wǎng)絡交疊團的聚類與模糊剖析辦法設計Issue(問題),給出一種新的模糊度量及對應的模糊聚類辦法,并以新度量為根底,設計出兩種發(fā)掘網(wǎng)絡模糊拓撲特征的新目標:團間銜接嚴密水平和模糊點對交疊團的銜接奉獻度,并將其用于網(wǎng)絡交疊模塊拓撲構造微觀剖析和團間關鍵點提取。實驗后果標明,運用該聚類與剖析辦法不只能夠取得模糊勾結構,并且可以提醒出新的網(wǎng)絡特

3、征。該辦法為復雜網(wǎng)絡聚類后剖析提供了新的視角。</p><p>　　關鍵詞:網(wǎng)絡模糊聚類;團—點相似度;團間連接緊密度;團間連接貢獻度;對稱非負矩陣分解;網(wǎng)絡宏觀拓撲 </p><p>　　Fuzzy clustering and information mining in complex networks </p><p>　　ZHAO Kun,ZHANG Sha

4、o-wu,PAN Quan </p><p>　　(School of Automation, Northwestern Polytechnical University, Xi’an 710072, China) </p><p>　　Abstract:There is seldom a method which is capable of both clustering the net

5、work and analyzing the resulted overlapping communities. To solve this problem, this paper presented a novel fuzzy metric and a soft clustering algorithm. Based on the novel metric, two topological fuzzy metric, which in

6、clude clique-clique closeness degree and inter-clique connecting contribution degree, were devised and applied in the topological macro analysis and the extraction of key nodes in the overlapping communi</p><p

7、>　　Key words:network fuzzy clustering; clique-node similarity; clique-clique closeness degree; inter-clique connection contribution degree; symmetrical nonnegative matrix factorization(s-NMF); network topology macrost

8、ructure </p><p>　　團結構是復雜網(wǎng)絡普遍而又重要的拓撲屬性之一,具有團內連接緊密、團間連接稀疏的特點。網(wǎng)絡團結構提取是復雜網(wǎng)絡分析中的一個基本步驟。揭示網(wǎng)絡團結構的復雜網(wǎng)絡聚類方法[1~5]對分析復雜網(wǎng)絡拓撲結構、理解其功能、發(fā)現(xiàn)其隱含模式以及預測網(wǎng)絡行為都具有十分重要的理論意義和廣泛的應用前景。目前,大多數(shù)提取方法不考慮重疊網(wǎng)絡團結構,但在多數(shù)網(wǎng)絡應用中,重疊團結構更為普遍,也更具有實際意義。

9、 </p><p>　　現(xiàn)有的網(wǎng)絡重疊團結構提取方法[6~10]多數(shù)只對團間模糊點進行初步分析,如Nepusz等人[9,10]的模糊點提取。針對網(wǎng)絡交疊團結構的深入拓撲分析,本文介紹一種新的團—點相似度模糊度量。由于含有確定的物理含意和更為豐富的拓撲信息,用這種模糊度量可進一步導出團與團的連接緊密程度,以及模糊節(jié)點對兩團聯(lián)系的貢獻程度,并設計出新指標和定量關系來深度分析網(wǎng)絡宏觀拓撲連接模式和提取關鍵連接節(jié)點。本文

10、在三個實際網(wǎng)絡上作了實驗分析,其結果表明,本方法所挖掘出的網(wǎng)絡拓撲特征信息為網(wǎng)絡的模糊聚類后分析提供了新的視角。 </p><p>　　1 新模糊度量和最優(yōu)化逼近方法 </p><p>　　設A=[Aij]n×n(Aij≥0)為n點權重無向網(wǎng)絡G(V,E)的鄰接矩陣,Y是由A產(chǎn)生的特征矩陣,表征點—點距離,Yij&gt;0。假設圖G的n個節(jié)點劃分到r個交疊團中,用非負r&

11、#215;n維矩陣W=[Wki]r×n來表示團—點關系,Wki為節(jié)點i與第k個團的關系緊密程度或相似度。W稱為團—點相似度矩陣。令 </p><p>　　Mij=?rk=1WkiWkj(1) </p><p>　　若Wki能精確反映點i與團k的緊密度,則Mij可視為對點i、j間相似度Yij的一個近似。所以可用矩陣W來重構Y,視為用團—點相似度W對點—點相似度Y的估計: </

12、p><p>　　W ?TW→Y(2) </p><p>　　用歐式距離構造如下目標函數(shù): </p><p>　　minW≥0 F?G(Y,W)=‖Y-W ?TW‖?F=?12?ij[(Y-W ?TW)。(Y-W ?TW)]ij(3) </p><p>　　其中:‖&#8226;‖?F為歐氏距離;A。B表示矩陣A、B的Hadamard 矩陣

13、乘法。由此,模糊度量W的實現(xiàn)問題轉換為一個最優(yōu)化問題,即尋找合適的W使式(3)定義的目標函數(shù)達到最小值。 </p><p>　　式(3)本質上是一種矩陣分解,被稱為對稱非負矩陣分解,或s-NMF (symmetrical non-negative matrix factorization)。?s-NMF的求解與非負矩陣分解NMF[11,12]的求解方法非常類似。非負矩陣分解將數(shù)據(jù)分解為兩個非負矩陣的乘積,得到對原

14、數(shù)據(jù)的簡化描述,被廣泛應用于各種數(shù)據(jù)分析領域。類似NMF的求解,s-NMF可視為加入限制條件(H=W)下的NMF。給出s-NMF的迭代式如下: </p><p>　　Wk+1=W?k。[W?kY]/[W?kW ?T?kW?k](4) </p><p>　　其中:[A]/[B]為矩陣A和B的Hadamard矩陣除法。 </p><p>　　由于在NMF中引入了限制條件

15、,s-NMF的解集是NMF的子集,即式(4)的迭代結果必落入NMF的穩(wěn)定點集合中符合附加條件(H=W)的部分,由此決定s-NMF的收斂性。 </p><p>　　在求解W之前還需要確定特征矩陣。本文選擴散核[13]為被逼近的特征矩陣。擴散核有明確的物理含義,它通過計算節(jié)點間的路徑數(shù)給出任意兩節(jié)點間的相似度,能描述網(wǎng)絡節(jié)點間的大尺度范圍關系,當兩點間路徑數(shù)增加時,其相似度也增大。擴散核矩陣被定義為 </p&g

16、t;<p>　　K=exp(-βL)(5) </p><p>　　其中:參數(shù)β用于控制相似度的擴散程度,本文取β=0.1;L是網(wǎng)絡G的拉普拉斯矩陣: </p><p>　　Lij=-Aiji≠j </p><p>　　?kAiki=j(6) </p><p>　　作為相似度的特征矩陣應該是擴散核矩陣K的歸一化?形式: </

17、p><p>　　Yij=Kij/(KiiKjj)??1/2(7) </p><p>　　基于擴散核的物理含義,團—點相似度W也具有了物理含義:團到點的路徑數(shù)。實際上,W就是聚類結果,對其列歸一化即可得模糊隸屬度,需要硬聚類結果時,則選取某點所對應列中相似度值最大的團為最終所屬團。</p><p>　　2 團—團關系度量 </p><p>　　團—

18、點相似度W使得定量刻畫網(wǎng)絡中的其他拓撲關系成為可能。正如W ?TW可被用來作為點與點的相似度的一個估計,同樣可用W來估計團—團關系: </p><p>　　Z=WW ?T(8) </p><p>　　其物理含義是團與團間的路徑條數(shù)。很明顯,Z的非對角元ZJK刻畫團J與團K之間的緊密程度,或團間重疊度,對角元ZJJ則刻畫團J的團內密度。? </p><p>　　以圖1

19、中的對稱網(wǎng)絡為例,二分團時算得 </p><p>　　Z=WW ?T=1.337 60.035 3 </p><p>　　0.035 31.337 6 </p><p>　　由于圖1中的網(wǎng)絡是對稱網(wǎng)絡,兩團具有同樣的拓撲連接模式,它們有相同的團內密度1.337 6,而團間重疊度為?0.035 3。</p><p>　　3 團間連接貢獻度 &l

20、t;/p><p>　　ZJK度量了團J與團K間的重疊程度: </p><p>　　ZJK=?na=1WJaWKa(9) </p><p>　　其中:WJaWKa是這個總量來自于點a的分量。下面定義一個新指標來量化給定點對團間連接的貢獻。假設點i是同時連接J、K兩團的團間某點,定義點i對團J和團K的團間連接貢獻度為</p><p>　　B?i=[(

21、WJiWKi)/(?na=1WJaWKa)]×100%(10) </p><p>　　顯然,那些團間連接貢獻大的點應處于網(wǎng)絡中連接各團的關鍵位置,它們對團間連接的穩(wěn)定性負主要責任。將這種在團與團間起關鍵連接作用的點稱為關鍵連接點。為了設定合適的閾值來提取團間關鍵連接點,本文一律取B&gt;10%的點為關鍵連接點。 </p><p>　　4 實驗與結果分析 </p&g

22、t;<p>　　下面將在三個實際網(wǎng)絡上展開實驗,首先根據(jù)指定分團個數(shù)計算出團—點相似度W,然后用W計算團—團關系和B值,并提取關鍵連接點。 </p><p>　　4.1 海豚社會網(wǎng) </p><p>　　由Lusseau等人[14]給出的瓶鼻海豚社會網(wǎng)來自對一個62個成員的瓶鼻海豚社會網(wǎng)絡長達七年的觀測,節(jié)點表示海豚,連線為對某兩只海豚非偶然同時出現(xiàn)的記錄。圖2(a)中名為S

23、N100 (點36)的海豚在一段時間內消失,導致這個海豚網(wǎng)絡分裂為兩部分。 </p><p>　　使用s-NMF算法聚類,海豚網(wǎng)絡分為兩團時,除30和39兩點外,其他點的分團結果與實際觀測相同,如圖2(a)所示。計算B值并根據(jù)閾值提取出的五個關鍵連接點:1、7、28、36、40(虛線圈內),它們對兩團連接起到至關重要的作用。圖2(b)為這五點的B值柱狀圖。該圖顯示,節(jié)點36(SN100)是五個關鍵連接點中B值最大

24、者,對連接兩團貢獻最大。某種程度上,這個結果可以解釋為什么海豚SN100的消失導致了整個網(wǎng)絡最終分裂的影響。本例說明,s-NMF算法及團間連接貢獻程度指標在分析、預測社會網(wǎng)絡演化方面有著獨具特色的作用。 </p><p>　　4.2 Santa Fe 科學合作網(wǎng) </p><p>　　用本算法對Newman等人提供的Santa Fe科學合作網(wǎng)絡[15]加以測試。271個節(jié)點表示涵蓋四個學術

25、領域的學者,學者合作發(fā)表文章產(chǎn)生網(wǎng)絡連接,構成了一個加權合作網(wǎng)絡。將本算法用于網(wǎng)絡中一個包含118個節(jié)點的最大孤立團,如圖3(a)所示。 </p><p>　　圖3(a)中,四個學科所對應的主要組成部分都被正確地分離出來,mathematical ecology(灰菱形)和agent-based models(白方塊)與文獻[15]的結果一致,中間的大模塊statistical physics又被細分為四個小塊,

26、以不同灰度區(qū)分。計算了24個點的團間連接度貢獻值B,從中分離出11個B值大于10%的點作為關鍵連接點:1、2、4、6、11、12、20、47、50、56、57,其標號在橫軸下方標出,見圖3(b),并在圖3(a)中用黑色圓圈標記,這些連接點對應那些具有多種學科興趣、積極參與交叉研究的學者。除去這11個點時,整個網(wǎng)絡的連接布局被完全破壞,見圖3(a)下方灰色背景縮小圖,可見關鍵連接點的確起到重要的溝通各模塊的作用。 </p>

27、<p>　　4.3 雜志索引網(wǎng)絡 </p><p>　　在Rosvall等人[16]建立的2004年雜志索引網(wǎng)絡上進行測試。網(wǎng)絡節(jié)點代表雜志,分為物理學(方形)、化學(方形)、生物學(菱形)、生態(tài)學(三角形)四個學科領域,每個學科中各選10份影響因子最高的刊物,共40個節(jié)點,若某刊物文章引用了另一刊物文章,則兩刊間有一條連線,形成189條連接。使用s-NMF對該網(wǎng)4分團時,聚類結果與實際分團情況完全一致

28、,如圖4(a)所示。 </p><p>　　由本算法得出的團—點相似度W在網(wǎng)絡宏觀拓撲結構的挖掘方面有非常有趣的應用,如第2章所述,用W計算團—團相似度矩陣Z=WW?T,其對角元是團內連接密度,非對角元表征團與團的連接緊密程度,故Z可被視為對原網(wǎng)絡的一種“壓縮表示”。如果將團換成“點”,將團與團之間的連接換成“邊”,利用Z的非對角元,就能構造出原網(wǎng)絡的一個壓縮投影網(wǎng)絡,如圖4(b)所示。這是原網(wǎng)絡的一個降維示意圖

29、,也是團與團之間關系定量刻畫的形象表述,定量地反映了原網(wǎng)絡在特定分團數(shù)下的“宏觀(全局)拓撲輪廓”,圖上團間連線色深和粗細表示連接緊密程度。由圖4(b)可以看到,physics和chemistry連接最緊密,而chemistry與biology和biology與?ecology次之。由此推測,如果減少分團數(shù),將相鄰兩團合并,連接最緊密的兩團必首先合并為一個團。實際情況正是如此:分團數(shù)為3時,biology和ecology各自獨立成團,p

30、hysics 和?chemistry合并為一個大團,這與文獻[11]結果一致。 </p><p><b>　　5 討論 </b></p><p>　　網(wǎng)絡模糊聚類能幫助研究者進一步對團間的一些特殊點進行定量分析,如Nepusz等人[9]用一種橋值公式來刻畫節(jié)點在多個團間的共享程度,即節(jié)點從屬度的模糊程度。而本文的團間連接貢獻度B反映出節(jié)點在團間連接中所起的作用大小。本

31、質上它們是完全不同的兩種概念,同時它們也都是網(wǎng)絡模糊分析中所特有的。團間連接貢獻度指標的提出,將研究引向對節(jié)點在網(wǎng)絡宏觀拓撲模式中的影響力的關注,是本方法的一個獨特貢獻。無疑,關鍵連接點對團間連接的穩(wěn)定性起到很大作用,如果要迅速切斷團間聯(lián)系,改變網(wǎng)絡的宏觀拓撲格局,首先攻擊關鍵連接點(如海豚網(wǎng)中的SD100)是最有效的方法。團間連接貢獻度這一定義的基礎來自于對團與團連接關系(Z)的定量刻畫,這個定量關系用以往的模糊隸屬度概念無法得到。由

32、于W有明確的物理含義,使得由W導出的團—團關系Z也具有了物理含義,這對網(wǎng)絡的宏觀拓撲分析非常?有利。 </p><p><b>　　6 結束語 </b></p><p>　　針對復雜網(wǎng)絡交疊團現(xiàn)象,本文給出了一個新的聚類后模糊分析框架。它不僅能對網(wǎng)絡進行模糊聚類,而且支持對交疊結構的模糊分析,如關鍵點的識別和網(wǎng)絡宏觀拓撲圖的提取。使用這些新方法、新指標能夠深入挖掘潛藏

33、于網(wǎng)絡的拓撲信息。從本文的聚類后分析不難看出,網(wǎng)絡模糊聚類的作用不僅在于聚類本身,還在于模糊聚類結果能夠為網(wǎng)絡拓撲深入分析和信息挖掘提供支持,而硬聚類則不能。今后將致力于對團間連接貢獻度指標進行更為深入的統(tǒng)計研究。</p><p><b>　　參考文獻: </b></p><p><b>　　[1] </b></p><p&g

34、t;　　趙鳳霞,謝福鼎.基于K-means聚類算法的復雜網(wǎng)絡社團發(fā)現(xiàn)新方法[J].計算機應用研究,2009,26(6):2041-2043,2049. </p><p>　　[2]汪小帆,劉亞冰.復雜網(wǎng)絡中的社團結構算法綜述[J].電子科技大學學報,2009,38(5):537-543. </p><p>　　[3]NEWMAN M E J.Modularity and community

35、 structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.</p><p>　　[4]WHITE S,SMYTH P.A spectral clustering approach to finding communi

36、ties in graphs[C]//Proc of SIAM International Conference on Data Mining.2005. </p><p>　　[5]ENRIGHT A J,DONGEN S V,OUZOUNIS C A.An efficient algorithm for large-scale detection of protein families[J].Nucleic

37、Acids Research,2002,30(7):1575-1584. </p><p>　　[6]BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press,1981. </p><p>　　[7]PALLA G,DERENYI I,FARKAS I,e

38、t al.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature,2005,435(7043):814-818. </p><p>　　?[8]REICHARDT J,BORNHOLDT S.Detecting fuzzy community structures in

39、complex networks with a potts model[J].Physical Review Letters,2004,93(21):218701. </p><p>　　?[9]NEPUSZ T,PETROCZI A,N?GYESSY L,et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Ph

40、ysical Review E,2008,77(1):016107. </p><p>　　[10]ZHANG Shi-hua,WANG Rui-sheng,ZHANG Xiang-sun.Identification of overlapping community structure in complex networks using fuzzy C-means clustering[J].Physical

41、Review A:Statistical Mechanics and Its Applications,2007,374(1):483-490. </p><p>　　[11]PAATERO P,TAPPER U.Positive matrix factorization:a non-negative factor model with optimal utilization of error estimates

42、 of data values[J].Environmetrics,1994,5(2):111-126. </p><p>　　[12]ANTTILA P,PAATERO P,TAPPER U,et al.Source identification of bulk wet deposition in Finland by positive matrix factorization[J].Atmospheric E

43、nvironment,1995,29(14):1705-1718. </p><p>　　[13]KONDOR R I,LAFFERTY J.Diffusion kernels on graphs and other discrete structures[C]//Proc of the 19th International Conference on Machine Learning.San Francisco

44、:Morgan Kaufmann,2002. </p><p>　　[14]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations:can geographic isolat

45、ion explain this unique trait?[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405. </p><p>　　[15]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the Natio

46、nal Academy of Sciences of the United States of America,2002,99(12):7821-7826. </p><p>　　[16]ROSVALL M,BERGSTROM C T.An information-theoretic framework for resolving community structure in complex networks [