復(fù)雜網(wǎng)絡(luò)交疊團(tuán)模糊分析與信息挖掘
若水221147由 分享
時(shí)間：
摘 要:針對(duì)復(fù)雜網(wǎng)絡(luò)交疊團(tuán)的聚類與模糊分析方法設(shè)計(jì)問題,給出一種新的模糊度量及相應(yīng)的模糊聚類方法,并以新度量為基礎(chǔ),設(shè)計(jì)出兩種挖掘網(wǎng)絡(luò)模糊拓?fù)涮卣鞯男轮笜?biāo):團(tuán)間連接緊密程度和模糊點(diǎn)對(duì)交疊團(tuán)的連接貢獻(xiàn)度,并將其用于網(wǎng)絡(luò)交疊模塊拓?fù)浣Y(jié)構(gòu)宏觀分析和團(tuán)間關(guān)鍵點(diǎn)提取。實(shí)驗(yàn)結(jié)果表明,使用該聚類與分析方法不僅可以獲得模糊團(tuán)結(jié)構(gòu),而且能夠揭示出新的網(wǎng)絡(luò)特征。該方法為復(fù)雜網(wǎng)絡(luò)聚類后分析提供了新的視角。
針對(duì)復(fù)雜網(wǎng)絡(luò)交疊團(tuán)的聚類與模糊剖析辦法設(shè)計(jì)Issue(問題),給出一種新的模糊度量及對(duì)應(yīng)的模糊聚類辦法,并以新度量為根底,設(shè)計(jì)出兩種發(fā)掘網(wǎng)絡(luò)模糊拓?fù)涮卣鞯男履繕?biāo):團(tuán)間銜接嚴(yán)密水平和模糊點(diǎn)對(duì)交疊團(tuán)的銜接奉獻(xiàn)度,并將其用于網(wǎng)絡(luò)交疊模塊拓?fù)錁?gòu)造微觀剖析和團(tuán)間關(guān)鍵點(diǎn)提取。實(shí)驗(yàn)后果標(biāo)明,運(yùn)用該聚類與剖析辦法不只能夠取得模糊勾結(jié)構(gòu),并且可以提醒出新的網(wǎng)絡(luò)特征。該辦法為復(fù)雜網(wǎng)絡(luò)聚類后剖析提供了新的視角。
關(guān)鍵詞:網(wǎng)絡(luò)模糊聚類;團(tuán)—點(diǎn)相似度;團(tuán)間連接緊密度;團(tuán)間連接貢獻(xiàn)度;對(duì)稱非負(fù)矩陣分解;網(wǎng)絡(luò)宏觀拓?fù)?br />
Fuzzy clustering and information mining in complex networks
ZHAO Kun,ZHANG Shao-wu,PAN Quan
(School of Automation, Northwestern Polytechnical University, Xi’an 710072, China)
Abstract:There is seldom a method which is capable of both clustering the network 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 include 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 communities. Experimental results indicate that, as an attempt of analysis after clustering, the new indicators and mechanics can uncover new topology features hidden in the network.
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 macrostructure
團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)普遍而又重要的拓?fù)鋵傩灾?具有團(tuán)內(nèi)連接緊密、團(tuán)間連接稀疏的特點(diǎn)。網(wǎng)絡(luò)團(tuán)結(jié)構(gòu)提取是復(fù)雜網(wǎng)絡(luò)分析中的一個(gè)基本步驟。揭示網(wǎng)絡(luò)團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)聚類方法[1~5]對(duì)分析復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、理解其功能、發(fā)現(xiàn)其隱含模式以及預(yù)測網(wǎng)絡(luò)行為都具有十分重要的理論意義和廣泛的應(yīng)用前景。目前,大多數(shù)提取方法不考慮重疊網(wǎng)絡(luò)團(tuán)結(jié)構(gòu),但在多數(shù)網(wǎng)絡(luò)應(yīng)用中,重疊團(tuán)結(jié)構(gòu)更為普遍,也更具有實(shí)際意義。
現(xiàn)有的網(wǎng)絡(luò)重疊團(tuán)結(jié)構(gòu)提取方法[6~10]多數(shù)只對(duì)團(tuán)間模糊點(diǎn)進(jìn)行初步分析,如Nepusz等人[9,10]的模糊點(diǎn)提取。針對(duì)網(wǎng)絡(luò)交疊團(tuán)結(jié)構(gòu)的深入拓?fù)浞治?本文介紹一種新的團(tuán)—點(diǎn)相似度模糊度量。由于含有確定的物理含意和更為豐富的拓?fù)湫畔?用這種模糊度量可進(jìn)一步導(dǎo)出團(tuán)與團(tuán)的連接緊密程度,以及模糊節(jié)點(diǎn)對(duì)兩團(tuán)聯(lián)系的貢獻(xiàn)程度,并設(shè)計(jì)出新指標(biāo)和定量關(guān)系來深度分析網(wǎng)絡(luò)宏觀拓?fù)溥B接模式和提取關(guān)鍵連接節(jié)點(diǎn)。本文在三個(gè)實(shí)際網(wǎng)絡(luò)上作了實(shí)驗(yàn)分析,其結(jié)果表明,本方法所挖掘出的網(wǎng)絡(luò)拓?fù)涮卣餍畔榫W(wǎng)絡(luò)的模糊聚類后分析提供了新的視角。
1 新模糊度量和最優(yōu)化逼近方法
設(shè)A=[Aij]n×n(Aij≥0)為n點(diǎn)權(quán)重?zé)o向網(wǎng)絡(luò)G(V,E)的鄰接矩陣,Y是由A產(chǎn)生的特征矩陣,表征點(diǎn)—點(diǎn)距離,Yij>0。假設(shè)圖G的n個(gè)節(jié)點(diǎn)劃分到r個(gè)交疊團(tuán)中,用非負(fù)r×n維矩陣W=[Wki]r×n來表示團(tuán)—點(diǎn)關(guān)系,Wki為節(jié)點(diǎn)i與第k個(gè)團(tuán)的關(guān)系緊密程度或相似度。W稱為團(tuán)—點(diǎn)相似度矩陣。令
Mij=?rk=1WkiWkj(1)
若Wki能精確反映點(diǎn)i與團(tuán)k的緊密度,則Mij可視為對(duì)點(diǎn)i、j間相似度Yij的一個(gè)近似。所以可用矩陣W來重構(gòu)Y,視為用團(tuán)—點(diǎn)相似度W對(duì)點(diǎn)—點(diǎn)相似度Y的估計(jì):
W ?TW→Y(2)
用歐式距離構(gòu)造如下目標(biāo)函數(shù):
minW≥0 F?G(Y,W)=‖Y-W ?TW‖?F=?12?ij[(Y-W ?TW)。(Y-W ?TW)]ij(3)
其中:‖•‖?F為歐氏距離;A。B表示矩陣A、B的Hadamard 矩陣乘法。由此,模糊度量W的實(shí)現(xiàn)問題轉(zhuǎn)換為一個(gè)最優(yōu)化問題,即尋找合適的W使式(3)定義的目標(biāo)函數(shù)達(dá)到最小值。
式(3)本質(zhì)上是一種矩陣分解,被稱為對(duì)稱非負(fù)矩陣分解,或s-NMF (symmetrical non-negative matrix factorization)。?s-NMF的求解與非負(fù)矩陣分解NMF[11,12]的求解方法非常類似。非負(fù)矩陣分解將數(shù)據(jù)分解為兩個(gè)非負(fù)矩陣的乘積,得到對(duì)原數(shù)據(jù)的簡化描述,被廣泛應(yīng)用于各種數(shù)據(jù)分析領(lǐng)域。類似NMF的求解,s-NMF可視為加入限制條件(H=W)下的NMF。給出s-NMF的迭代式如下:
Wk+1=W?k。[W?kY]/[W?kW ?T?kW?k](4)
其中:[A]/[B]為矩陣A和B的Hadamard矩陣除法。
由于在NMF中引入了限制條件,s-NMF的解集是NMF的子集,即式(4)的迭代結(jié)果必落入NMF的穩(wěn)定點(diǎn)集合中符合附加條件(H=W)的部分,由此決定s-NMF的收斂性。
在求解W之前還需要確定特征矩陣。本文選擴(kuò)散核[13]為被逼近的特征矩陣。擴(kuò)散核有明確的物理含義,它通過計(jì)算節(jié)點(diǎn)間的路徑數(shù)給出任意兩節(jié)點(diǎn)間的相似度,能描述網(wǎng)絡(luò)節(jié)點(diǎn)間的大尺度范圍關(guān)系,當(dāng)兩點(diǎn)間路徑數(shù)增加時(shí),其相似度也增大。擴(kuò)散核矩陣被定義為
K=exp(-βL)(5)
其中:參數(shù)β用于控制相似度的擴(kuò)散程度,本文取β=0.1;L是網(wǎng)絡(luò)G的拉普拉斯矩陣:
Lij=-Aiji≠j
?kAiki=j(6)
作為相似度的特征矩陣應(yīng)該是擴(kuò)散核矩陣K的歸一化?形式:
Yij=Kij/(KiiKjj)??1/2(7)
基于擴(kuò)散核的物理含義,團(tuán)—點(diǎn)相似度W也具有了物理含義:團(tuán)到點(diǎn)的路徑數(shù)。實(shí)際上,W就是聚類結(jié)果,對(duì)其列歸一化即可得模糊隸屬度,需要硬聚類結(jié)果時(shí),則選取某點(diǎn)所對(duì)應(yīng)列中相似度值最大的團(tuán)為最終所屬團(tuán)。
2 團(tuán)—團(tuán)關(guān)系度量
團(tuán)—點(diǎn)相似度W使得定量刻畫網(wǎng)絡(luò)中的其他拓?fù)潢P(guān)系成為可能。正如W ?TW可被用來作為點(diǎn)與點(diǎn)的相似度的一個(gè)估計(jì),同樣可用W來估計(jì)團(tuán)—團(tuán)關(guān)系:
Z=WW ?T(8)
其物理含義是團(tuán)與團(tuán)間的路徑條數(shù)。很明顯,Z的非對(duì)角元ZJK刻畫團(tuán)J與團(tuán)K之間的緊密程度,或團(tuán)間重疊度,對(duì)角元ZJJ則刻畫團(tuán)J的團(tuán)內(nèi)密度。?
以圖1中的對(duì)稱網(wǎng)絡(luò)為例,二分團(tuán)時(shí)算得
Z=WW ?T=1.337 60.035 3
0.035 31.337 6
由于圖1中的網(wǎng)絡(luò)是對(duì)稱網(wǎng)絡(luò),兩團(tuán)具有同樣的拓?fù)溥B接模式,它們有相同的團(tuán)內(nèi)密度1.337 6,而團(tuán)間重疊度為?0.035 3。
3 團(tuán)間連接貢獻(xiàn)度
ZJK度量了團(tuán)J與團(tuán)K間的重疊程度:
ZJK=?na=1WJaWKa(9)
其中:WJaWKa是這個(gè)總量來自于點(diǎn)a的分量。下面定義一個(gè)新指標(biāo)來量化給定點(diǎn)對(duì)團(tuán)間連接的貢獻(xiàn)。假設(shè)點(diǎn)i是同時(shí)連接J、K兩團(tuán)的團(tuán)間某點(diǎn),定義點(diǎn)i對(duì)團(tuán)J和團(tuán)K的團(tuán)間連接貢獻(xiàn)度為
B?i=[(WJiWKi)/(?na=1WJaWKa)]×100%(10)
顯然,那些團(tuán)間連接貢獻(xiàn)大的點(diǎn)應(yīng)處于網(wǎng)絡(luò)中連接各團(tuán)的關(guān)鍵位置,它們對(duì)團(tuán)間連接的穩(wěn)定性負(fù)主要責(zé)任。將這種在團(tuán)與團(tuán)間起關(guān)鍵連接作用的點(diǎn)稱為關(guān)鍵連接點(diǎn)。為了設(shè)定合適的閾值來提取團(tuán)間關(guān)鍵連接點(diǎn),本文一律取B>10%的點(diǎn)為關(guān)鍵連接點(diǎn)。
4 實(shí)驗(yàn)與結(jié)果分析
下面將在三個(gè)實(shí)際網(wǎng)絡(luò)上展開實(shí)驗(yàn),首先根據(jù)指定分團(tuán)個(gè)數(shù)計(jì)算出團(tuán)—點(diǎn)相似度W,然后用W計(jì)算團(tuán)—團(tuán)關(guān)系和B值,并提取關(guān)鍵連接點(diǎn)。
4.1 海豚社會(huì)網(wǎng)
由Lusseau等人[14]給出的瓶鼻海豚社會(huì)網(wǎng)來自對(duì)一個(gè)62個(gè)成員的瓶鼻海豚社會(huì)網(wǎng)絡(luò)長達(dá)七年的觀測,節(jié)點(diǎn)表示海豚,連線為對(duì)某兩只海豚非偶然同時(shí)出現(xiàn)的記錄。圖2(a)中名為SN100 (點(diǎn)36)的海豚在一段時(shí)間內(nèi)消失,導(dǎo)致這個(gè)海豚網(wǎng)絡(luò)分裂為兩部分。
使用s-NMF算法聚類,海豚網(wǎng)絡(luò)分為兩團(tuán)時(shí),除30和39兩點(diǎn)外,其他點(diǎn)的分團(tuán)結(jié)果與實(shí)際觀測相同,如圖2(a)所示。計(jì)算B值并根據(jù)閾值提取出的五個(gè)關(guān)鍵連接點(diǎn):1、7、28、36、40(虛線圈內(nèi)),它們對(duì)兩團(tuán)連接起到至關(guān)重要的作用。圖2(b)為這五點(diǎn)的B值柱狀圖。該圖顯示,節(jié)點(diǎn)36(SN100)是五個(gè)關(guān)鍵連接點(diǎn)中B值最大者,對(duì)連接兩團(tuán)貢獻(xiàn)最大。某種程度上,這個(gè)結(jié)果可以解釋為什么海豚SN100的消失導(dǎo)致了整個(gè)網(wǎng)絡(luò)最終分裂的影響。本例說明,s-NMF算法及團(tuán)間連接貢獻(xiàn)程度指標(biāo)在分析、預(yù)測社會(huì)網(wǎng)絡(luò)演化方面有著獨(dú)具特色的作用。
4.2 Santa Fe 科學(xué)合作網(wǎng)
用本算法對(duì)Newman等人提供的Santa Fe科學(xué)合作網(wǎng)絡(luò)[15]加以測試。271個(gè)節(jié)點(diǎn)表示涵蓋四個(gè)學(xué)術(shù)領(lǐng)域的學(xué)者,學(xué)者合作發(fā)表文章產(chǎn)生網(wǎng)絡(luò)連接,構(gòu)成了一個(gè)加權(quán)合作網(wǎng)絡(luò)。將本算法用于網(wǎng)絡(luò)中一個(gè)包含118個(gè)節(jié)點(diǎn)的最大孤立團(tuán),如圖3(a)所示。
圖3(a)中,四個(gè)學(xué)科所對(duì)應(yīng)的主要組成部分都被正確地分離出來,mathematical ecology(灰菱形)和agent-based models(白方塊)與文獻(xiàn)[15]的結(jié)果一致,中間的大模塊statistical physics又被細(xì)分為四個(gè)小塊,以不同灰度區(qū)分。計(jì)算了24個(gè)點(diǎn)的團(tuán)間連接度貢獻(xiàn)值B,從中分離出11個(gè)B值大于10%的點(diǎn)作為關(guān)鍵連接點(diǎn):1、2、4、6、11、12、20、47、50、56、57,其標(biāo)號(hào)在橫軸下方標(biāo)出,見圖3(b),并在圖3(a)中用黑色圓圈標(biāo)記,這些連接點(diǎn)對(duì)應(yīng)那些具有多種學(xué)科興趣、積極參與交叉研究的學(xué)者。除去這11個(gè)點(diǎn)時(shí),整個(gè)網(wǎng)絡(luò)的連接布局被完全破壞,見圖3(a)下方灰色背景縮小圖,可見關(guān)鍵連接點(diǎn)的確起到重要的溝通各模塊的作用。
4.3 雜志索引網(wǎng)絡(luò)
在Rosvall等人[16]建立的2004年雜志索引網(wǎng)絡(luò)上進(jìn)行測試。網(wǎng)絡(luò)節(jié)點(diǎn)代表雜志,分為物理學(xué)(方形)、化學(xué)(方形)、生物學(xué)(菱形)、生態(tài)學(xué)(三角形)四個(gè)學(xué)科領(lǐng)域,每個(gè)學(xué)科中各選10份影響因子最高的刊物,共40個(gè)節(jié)點(diǎn),若某刊物文章引用了另一刊物文章,則兩刊間有一條連線,形成189條連接。使用s-NMF對(duì)該網(wǎng)4分團(tuán)時(shí),聚類結(jié)果與實(shí)際分團(tuán)情況完全一致,如圖4(a)所示。
由本算法得出的團(tuán)—點(diǎn)相似度W在網(wǎng)絡(luò)宏觀拓?fù)浣Y(jié)構(gòu)的挖掘方面有非常有趣的應(yīng)用,如第2章所述,用W計(jì)算團(tuán)—團(tuán)相似度矩陣Z=WW?T,其對(duì)角元是團(tuán)內(nèi)連接密度,非對(duì)角元表征團(tuán)與團(tuán)的連接緊密程度,故Z可被視為對(duì)原網(wǎng)絡(luò)的一種“壓縮表示”。如果將團(tuán)換成“點(diǎn)”,將團(tuán)與團(tuán)之間的連接換成“邊”,利用Z的非對(duì)角元,就能構(gòu)造出原網(wǎng)絡(luò)的一個(gè)壓縮投影網(wǎng)絡(luò),如圖4(b)所示。這是原網(wǎng)絡(luò)的一個(gè)降維示意圖,也是團(tuán)與團(tuán)之間關(guān)系定量刻畫的形象表述,定量地反映了原網(wǎng)絡(luò)在特定分團(tuán)數(shù)下的“宏觀(全局)拓?fù)漭喞?圖上團(tuán)間連線色深和粗細(xì)表示連接緊密程度。由圖4(b)可以看到,physics和chemistry連接最緊密,而chemistry與biology和biology與?ecology次之。由此推測,如果減少分團(tuán)數(shù),將相鄰兩團(tuán)合并,連接最緊密的兩團(tuán)必首先合并為一個(gè)團(tuán)。實(shí)際情況正是如此:分團(tuán)數(shù)為3時(shí),biology和ecology各自獨(dú)立成團(tuán),physics 和?chemistry合并為一個(gè)大團(tuán),這與文獻(xiàn)[11]結(jié)果一致。
5 討論
網(wǎng)絡(luò)模糊聚類能幫助研究者進(jìn)一步對(duì)團(tuán)間的一些特殊點(diǎn)進(jìn)行定量分析,如Nepusz等人[9]用一種橋值公式來刻畫節(jié)點(diǎn)在多個(gè)團(tuán)間的共享程度,即節(jié)點(diǎn)從屬度的模糊程度。而本文的團(tuán)間連接貢獻(xiàn)度B反映出節(jié)點(diǎn)在團(tuán)間連接中所起的作用大小。本質(zhì)上它們是完全不同的兩種概念,同時(shí)它們也都是網(wǎng)絡(luò)模糊分析中所特有的。團(tuán)間連接貢獻(xiàn)度指標(biāo)的提出,將研究引向?qū)?jié)點(diǎn)在網(wǎng)絡(luò)宏觀拓?fù)淠Ｊ街械挠绊懥Φ年P(guān)注,是本方法的一個(gè)獨(dú)特貢獻(xiàn)。無疑,關(guān)鍵連接點(diǎn)對(duì)團(tuán)間連接的穩(wěn)定性起到很大作用,如果要迅速切斷團(tuán)間聯(lián)系,改變網(wǎng)絡(luò)的宏觀拓?fù)涓窬?首先攻擊關(guān)鍵連接點(diǎn)(如海豚網(wǎng)中的SD100)是最有效的方法。團(tuán)間連接貢獻(xiàn)度這一定義的基礎(chǔ)來自于對(duì)團(tuán)與團(tuán)連接關(guān)系(Z)的定量刻畫,這個(gè)定量關(guān)系用以往的模糊隸屬度概念無法得到。由于W有明確的物理含義,使得由W導(dǎo)出的團(tuán)—團(tuán)關(guān)系Z也具有了物理含義,這對(duì)網(wǎng)絡(luò)的宏觀拓?fù)浞治龇浅?有利。
6 結(jié)束語
針對(duì)復(fù)雜網(wǎng)絡(luò)交疊團(tuán)現(xiàn)象,本文給出了一個(gè)新的聚類后模糊分析框架。它不僅能對(duì)網(wǎng)絡(luò)進(jìn)行模糊聚類,而且支持對(duì)交疊結(jié)構(gòu)的模糊分析,如關(guān)鍵點(diǎn)的識(shí)別和網(wǎng)絡(luò)宏觀拓?fù)鋱D的提取。使用這些新方法、新指標(biāo)能夠深入挖掘潛藏于網(wǎng)絡(luò)的拓?fù)湫畔?。從本文的聚類后分析不難看出,網(wǎng)絡(luò)模糊聚類的作用不僅在于聚類本身,還在于模糊聚類結(jié)果能夠?yàn)榫W(wǎng)絡(luò)拓?fù)渖钊敕治龊托畔⑼诰蛱峁┲С?而硬聚類則不能。今后將致力于對(duì)團(tuán)間連接貢獻(xiàn)度指標(biāo)進(jìn)行更為深入的統(tǒng)計(jì)研究。
參考文獻(xiàn):
[1]
趙鳳霞,謝福鼎.基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(6):2041-2043,2049.
[2]汪小帆,劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J].電子科技大學(xué)學(xué)報(bào),2009,38(5):537-543.
[3]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[4]WHITE S,SMYTH P.A spectral clustering approach to finding communities in graphs[C]//Proc of SIAM International Conference on Data Mining.2005.
[5]ENRIGHT A J,DONGEN S V,OUZOUNIS C A.An efficient algorithm for large-scale detection of protein families[J].Nucleic Acids Research,2002,30(7):1575-1584.
[6]BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press,1981.
[7]PALLA G,DERENYI I,FARKAS I,et al.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
?[8]REICHARDT J,BORNHOLDT S.Detecting fuzzy community structures in complex networks with a potts model[J].Physical Review Letters,2004,93(21):218701.
?[9]NEPUSZ T,PETROCZI A,N?GYESSY L,et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Physical Review E,2008,77(1):016107.
[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 Review A:Statistical Mechanics and Its Applications,2007,374(1):483-490.
[11]PAATERO P,TAPPER U.Positive matrix factorization:a non-negative factor model with optimal utilization of error estimates of data values[J].Environmetrics,1994,5(2):111-126.
[12]ANTTILA P,PAATERO P,TAPPER U,et al.Source identification of bulk wet deposition in Finland by positive matrix factorization[J].Atmospheric Environment,1995,29(14):1705-1718.
[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:Morgan Kaufmann,2002.
[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 isolation explain this unique trait?[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[15]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[16]ROSVALL M,BERGSTROM C T.An information-theoretic framework for resolving community structure in complex networks [J].Proceedings of the National Academy of Sciences of the United States of ?America,2007,104(18):7327-7331.
針對(duì)復(fù)雜網(wǎng)絡(luò)交疊團(tuán)的聚類與模糊剖析辦法設(shè)計(jì)Issue(問題),給出一種新的模糊度量及對(duì)應(yīng)的模糊聚類辦法,并以新度量為根底,設(shè)計(jì)出兩種發(fā)掘網(wǎng)絡(luò)模糊拓?fù)涮卣鞯男履繕?biāo):團(tuán)間銜接嚴(yán)密水平和模糊點(diǎn)對(duì)交疊團(tuán)的銜接奉獻(xiàn)度,并將其用于網(wǎng)絡(luò)交疊模塊拓?fù)錁?gòu)造微觀剖析和團(tuán)間關(guān)鍵點(diǎn)提取。實(shí)驗(yàn)后果標(biāo)明,運(yùn)用該聚類與剖析辦法不只能夠取得模糊勾結(jié)構(gòu),并且可以提醒出新的網(wǎng)絡(luò)特征。該辦法為復(fù)雜網(wǎng)絡(luò)聚類后剖析提供了新的視角。
關(guān)鍵詞:網(wǎng)絡(luò)模糊聚類;團(tuán)—點(diǎn)相似度;團(tuán)間連接緊密度;團(tuán)間連接貢獻(xiàn)度;對(duì)稱非負(fù)矩陣分解;網(wǎng)絡(luò)宏觀拓?fù)?br />
Fuzzy clustering and information mining in complex networks
ZHAO Kun,ZHANG Shao-wu,PAN Quan
(School of Automation, Northwestern Polytechnical University, Xi’an 710072, China)
Abstract:There is seldom a method which is capable of both clustering the network 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 include 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 communities. Experimental results indicate that, as an attempt of analysis after clustering, the new indicators and mechanics can uncover new topology features hidden in the network.
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 macrostructure
團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)普遍而又重要的拓?fù)鋵傩灾?具有團(tuán)內(nèi)連接緊密、團(tuán)間連接稀疏的特點(diǎn)。網(wǎng)絡(luò)團(tuán)結(jié)構(gòu)提取是復(fù)雜網(wǎng)絡(luò)分析中的一個(gè)基本步驟。揭示網(wǎng)絡(luò)團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)聚類方法[1~5]對(duì)分析復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、理解其功能、發(fā)現(xiàn)其隱含模式以及預(yù)測網(wǎng)絡(luò)行為都具有十分重要的理論意義和廣泛的應(yīng)用前景。目前,大多數(shù)提取方法不考慮重疊網(wǎng)絡(luò)團(tuán)結(jié)構(gòu),但在多數(shù)網(wǎng)絡(luò)應(yīng)用中,重疊團(tuán)結(jié)構(gòu)更為普遍,也更具有實(shí)際意義。
現(xiàn)有的網(wǎng)絡(luò)重疊團(tuán)結(jié)構(gòu)提取方法[6~10]多數(shù)只對(duì)團(tuán)間模糊點(diǎn)進(jìn)行初步分析,如Nepusz等人[9,10]的模糊點(diǎn)提取。針對(duì)網(wǎng)絡(luò)交疊團(tuán)結(jié)構(gòu)的深入拓?fù)浞治?本文介紹一種新的團(tuán)—點(diǎn)相似度模糊度量。由于含有確定的物理含意和更為豐富的拓?fù)湫畔?用這種模糊度量可進(jìn)一步導(dǎo)出團(tuán)與團(tuán)的連接緊密程度,以及模糊節(jié)點(diǎn)對(duì)兩團(tuán)聯(lián)系的貢獻(xiàn)程度,并設(shè)計(jì)出新指標(biāo)和定量關(guān)系來深度分析網(wǎng)絡(luò)宏觀拓?fù)溥B接模式和提取關(guān)鍵連接節(jié)點(diǎn)。本文在三個(gè)實(shí)際網(wǎng)絡(luò)上作了實(shí)驗(yàn)分析,其結(jié)果表明,本方法所挖掘出的網(wǎng)絡(luò)拓?fù)涮卣餍畔榫W(wǎng)絡(luò)的模糊聚類后分析提供了新的視角。
1 新模糊度量和最優(yōu)化逼近方法
設(shè)A=[Aij]n×n(Aij≥0)為n點(diǎn)權(quán)重?zé)o向網(wǎng)絡(luò)G(V,E)的鄰接矩陣,Y是由A產(chǎn)生的特征矩陣,表征點(diǎn)—點(diǎn)距離,Yij>0。假設(shè)圖G的n個(gè)節(jié)點(diǎn)劃分到r個(gè)交疊團(tuán)中,用非負(fù)r×n維矩陣W=[Wki]r×n來表示團(tuán)—點(diǎn)關(guān)系,Wki為節(jié)點(diǎn)i與第k個(gè)團(tuán)的關(guān)系緊密程度或相似度。W稱為團(tuán)—點(diǎn)相似度矩陣。令
Mij=?rk=1WkiWkj(1)
若Wki能精確反映點(diǎn)i與團(tuán)k的緊密度,則Mij可視為對(duì)點(diǎn)i、j間相似度Yij的一個(gè)近似。所以可用矩陣W來重構(gòu)Y,視為用團(tuán)—點(diǎn)相似度W對(duì)點(diǎn)—點(diǎn)相似度Y的估計(jì):
W ?TW→Y(2)
用歐式距離構(gòu)造如下目標(biāo)函數(shù):
minW≥0 F?G(Y,W)=‖Y-W ?TW‖?F=?12?ij[(Y-W ?TW)。(Y-W ?TW)]ij(3)
其中:‖•‖?F為歐氏距離;A。B表示矩陣A、B的Hadamard 矩陣乘法。由此,模糊度量W的實(shí)現(xiàn)問題轉(zhuǎn)換為一個(gè)最優(yōu)化問題,即尋找合適的W使式(3)定義的目標(biāo)函數(shù)達(dá)到最小值。
式(3)本質(zhì)上是一種矩陣分解,被稱為對(duì)稱非負(fù)矩陣分解,或s-NMF (symmetrical non-negative matrix factorization)。?s-NMF的求解與非負(fù)矩陣分解NMF[11,12]的求解方法非常類似。非負(fù)矩陣分解將數(shù)據(jù)分解為兩個(gè)非負(fù)矩陣的乘積,得到對(duì)原數(shù)據(jù)的簡化描述,被廣泛應(yīng)用于各種數(shù)據(jù)分析領(lǐng)域。類似NMF的求解,s-NMF可視為加入限制條件(H=W)下的NMF。給出s-NMF的迭代式如下:
Wk+1=W?k。[W?kY]/[W?kW ?T?kW?k](4)
其中:[A]/[B]為矩陣A和B的Hadamard矩陣除法。
由于在NMF中引入了限制條件,s-NMF的解集是NMF的子集,即式(4)的迭代結(jié)果必落入NMF的穩(wěn)定點(diǎn)集合中符合附加條件(H=W)的部分,由此決定s-NMF的收斂性。
在求解W之前還需要確定特征矩陣。本文選擴(kuò)散核[13]為被逼近的特征矩陣。擴(kuò)散核有明確的物理含義,它通過計(jì)算節(jié)點(diǎn)間的路徑數(shù)給出任意兩節(jié)點(diǎn)間的相似度,能描述網(wǎng)絡(luò)節(jié)點(diǎn)間的大尺度范圍關(guān)系,當(dāng)兩點(diǎn)間路徑數(shù)增加時(shí),其相似度也增大。擴(kuò)散核矩陣被定義為
K=exp(-βL)(5)
其中:參數(shù)β用于控制相似度的擴(kuò)散程度,本文取β=0.1;L是網(wǎng)絡(luò)G的拉普拉斯矩陣:
Lij=-Aiji≠j
?kAiki=j(6)
作為相似度的特征矩陣應(yīng)該是擴(kuò)散核矩陣K的歸一化?形式:
Yij=Kij/(KiiKjj)??1/2(7)
基于擴(kuò)散核的物理含義,團(tuán)—點(diǎn)相似度W也具有了物理含義:團(tuán)到點(diǎn)的路徑數(shù)。實(shí)際上,W就是聚類結(jié)果,對(duì)其列歸一化即可得模糊隸屬度,需要硬聚類結(jié)果時(shí),則選取某點(diǎn)所對(duì)應(yīng)列中相似度值最大的團(tuán)為最終所屬團(tuán)。
2 團(tuán)—團(tuán)關(guān)系度量
團(tuán)—點(diǎn)相似度W使得定量刻畫網(wǎng)絡(luò)中的其他拓?fù)潢P(guān)系成為可能。正如W ?TW可被用來作為點(diǎn)與點(diǎn)的相似度的一個(gè)估計(jì),同樣可用W來估計(jì)團(tuán)—團(tuán)關(guān)系:
Z=WW ?T(8)
其物理含義是團(tuán)與團(tuán)間的路徑條數(shù)。很明顯,Z的非對(duì)角元ZJK刻畫團(tuán)J與團(tuán)K之間的緊密程度,或團(tuán)間重疊度,對(duì)角元ZJJ則刻畫團(tuán)J的團(tuán)內(nèi)密度。?
以圖1中的對(duì)稱網(wǎng)絡(luò)為例,二分團(tuán)時(shí)算得
Z=WW ?T=1.337 60.035 3
0.035 31.337 6
由于圖1中的網(wǎng)絡(luò)是對(duì)稱網(wǎng)絡(luò),兩團(tuán)具有同樣的拓?fù)溥B接模式,它們有相同的團(tuán)內(nèi)密度1.337 6,而團(tuán)間重疊度為?0.035 3。
3 團(tuán)間連接貢獻(xiàn)度
ZJK度量了團(tuán)J與團(tuán)K間的重疊程度:
ZJK=?na=1WJaWKa(9)
其中:WJaWKa是這個(gè)總量來自于點(diǎn)a的分量。下面定義一個(gè)新指標(biāo)來量化給定點(diǎn)對(duì)團(tuán)間連接的貢獻(xiàn)。假設(shè)點(diǎn)i是同時(shí)連接J、K兩團(tuán)的團(tuán)間某點(diǎn),定義點(diǎn)i對(duì)團(tuán)J和團(tuán)K的團(tuán)間連接貢獻(xiàn)度為
B?i=[(WJiWKi)/(?na=1WJaWKa)]×100%(10)
顯然,那些團(tuán)間連接貢獻(xiàn)大的點(diǎn)應(yīng)處于網(wǎng)絡(luò)中連接各團(tuán)的關(guān)鍵位置,它們對(duì)團(tuán)間連接的穩(wěn)定性負(fù)主要責(zé)任。將這種在團(tuán)與團(tuán)間起關(guān)鍵連接作用的點(diǎn)稱為關(guān)鍵連接點(diǎn)。為了設(shè)定合適的閾值來提取團(tuán)間關(guān)鍵連接點(diǎn),本文一律取B>10%的點(diǎn)為關(guān)鍵連接點(diǎn)。
4 實(shí)驗(yàn)與結(jié)果分析
下面將在三個(gè)實(shí)際網(wǎng)絡(luò)上展開實(shí)驗(yàn),首先根據(jù)指定分團(tuán)個(gè)數(shù)計(jì)算出團(tuán)—點(diǎn)相似度W,然后用W計(jì)算團(tuán)—團(tuán)關(guān)系和B值,并提取關(guān)鍵連接點(diǎn)。
4.1 海豚社會(huì)網(wǎng)
由Lusseau等人[14]給出的瓶鼻海豚社會(huì)網(wǎng)來自對(duì)一個(gè)62個(gè)成員的瓶鼻海豚社會(huì)網(wǎng)絡(luò)長達(dá)七年的觀測,節(jié)點(diǎn)表示海豚,連線為對(duì)某兩只海豚非偶然同時(shí)出現(xiàn)的記錄。圖2(a)中名為SN100 (點(diǎn)36)的海豚在一段時(shí)間內(nèi)消失,導(dǎo)致這個(gè)海豚網(wǎng)絡(luò)分裂為兩部分。
使用s-NMF算法聚類,海豚網(wǎng)絡(luò)分為兩團(tuán)時(shí),除30和39兩點(diǎn)外,其他點(diǎn)的分團(tuán)結(jié)果與實(shí)際觀測相同,如圖2(a)所示。計(jì)算B值并根據(jù)閾值提取出的五個(gè)關(guān)鍵連接點(diǎn):1、7、28、36、40(虛線圈內(nèi)),它們對(duì)兩團(tuán)連接起到至關(guān)重要的作用。圖2(b)為這五點(diǎn)的B值柱狀圖。該圖顯示,節(jié)點(diǎn)36(SN100)是五個(gè)關(guān)鍵連接點(diǎn)中B值最大者,對(duì)連接兩團(tuán)貢獻(xiàn)最大。某種程度上,這個(gè)結(jié)果可以解釋為什么海豚SN100的消失導(dǎo)致了整個(gè)網(wǎng)絡(luò)最終分裂的影響。本例說明,s-NMF算法及團(tuán)間連接貢獻(xiàn)程度指標(biāo)在分析、預(yù)測社會(huì)網(wǎng)絡(luò)演化方面有著獨(dú)具特色的作用。
4.2 Santa Fe 科學(xué)合作網(wǎng)
用本算法對(duì)Newman等人提供的Santa Fe科學(xué)合作網(wǎng)絡(luò)[15]加以測試。271個(gè)節(jié)點(diǎn)表示涵蓋四個(gè)學(xué)術(shù)領(lǐng)域的學(xué)者,學(xué)者合作發(fā)表文章產(chǎn)生網(wǎng)絡(luò)連接,構(gòu)成了一個(gè)加權(quán)合作網(wǎng)絡(luò)。將本算法用于網(wǎng)絡(luò)中一個(gè)包含118個(gè)節(jié)點(diǎn)的最大孤立團(tuán),如圖3(a)所示。
圖3(a)中,四個(gè)學(xué)科所對(duì)應(yīng)的主要組成部分都被正確地分離出來,mathematical ecology(灰菱形)和agent-based models(白方塊)與文獻(xiàn)[15]的結(jié)果一致,中間的大模塊statistical physics又被細(xì)分為四個(gè)小塊,以不同灰度區(qū)分。計(jì)算了24個(gè)點(diǎn)的團(tuán)間連接度貢獻(xiàn)值B,從中分離出11個(gè)B值大于10%的點(diǎn)作為關(guān)鍵連接點(diǎn):1、2、4、6、11、12、20、47、50、56、57,其標(biāo)號(hào)在橫軸下方標(biāo)出,見圖3(b),并在圖3(a)中用黑色圓圈標(biāo)記,這些連接點(diǎn)對(duì)應(yīng)那些具有多種學(xué)科興趣、積極參與交叉研究的學(xué)者。除去這11個(gè)點(diǎn)時(shí),整個(gè)網(wǎng)絡(luò)的連接布局被完全破壞,見圖3(a)下方灰色背景縮小圖,可見關(guān)鍵連接點(diǎn)的確起到重要的溝通各模塊的作用。
4.3 雜志索引網(wǎng)絡(luò)
在Rosvall等人[16]建立的2004年雜志索引網(wǎng)絡(luò)上進(jìn)行測試。網(wǎng)絡(luò)節(jié)點(diǎn)代表雜志,分為物理學(xué)(方形)、化學(xué)(方形)、生物學(xué)(菱形)、生態(tài)學(xué)(三角形)四個(gè)學(xué)科領(lǐng)域,每個(gè)學(xué)科中各選10份影響因子最高的刊物,共40個(gè)節(jié)點(diǎn),若某刊物文章引用了另一刊物文章,則兩刊間有一條連線,形成189條連接。使用s-NMF對(duì)該網(wǎng)4分團(tuán)時(shí),聚類結(jié)果與實(shí)際分團(tuán)情況完全一致,如圖4(a)所示。
由本算法得出的團(tuán)—點(diǎn)相似度W在網(wǎng)絡(luò)宏觀拓?fù)浣Y(jié)構(gòu)的挖掘方面有非常有趣的應(yīng)用,如第2章所述,用W計(jì)算團(tuán)—團(tuán)相似度矩陣Z=WW?T,其對(duì)角元是團(tuán)內(nèi)連接密度,非對(duì)角元表征團(tuán)與團(tuán)的連接緊密程度,故Z可被視為對(duì)原網(wǎng)絡(luò)的一種“壓縮表示”。如果將團(tuán)換成“點(diǎn)”,將團(tuán)與團(tuán)之間的連接換成“邊”,利用Z的非對(duì)角元,就能構(gòu)造出原網(wǎng)絡(luò)的一個(gè)壓縮投影網(wǎng)絡(luò),如圖4(b)所示。這是原網(wǎng)絡(luò)的一個(gè)降維示意圖,也是團(tuán)與團(tuán)之間關(guān)系定量刻畫的形象表述,定量地反映了原網(wǎng)絡(luò)在特定分團(tuán)數(shù)下的“宏觀(全局)拓?fù)漭喞?圖上團(tuán)間連線色深和粗細(xì)表示連接緊密程度。由圖4(b)可以看到,physics和chemistry連接最緊密,而chemistry與biology和biology與?ecology次之。由此推測,如果減少分團(tuán)數(shù),將相鄰兩團(tuán)合并,連接最緊密的兩團(tuán)必首先合并為一個(gè)團(tuán)。實(shí)際情況正是如此:分團(tuán)數(shù)為3時(shí),biology和ecology各自獨(dú)立成團(tuán),physics 和?chemistry合并為一個(gè)大團(tuán),這與文獻(xiàn)[11]結(jié)果一致。
5 討論
網(wǎng)絡(luò)模糊聚類能幫助研究者進(jìn)一步對(duì)團(tuán)間的一些特殊點(diǎn)進(jìn)行定量分析,如Nepusz等人[9]用一種橋值公式來刻畫節(jié)點(diǎn)在多個(gè)團(tuán)間的共享程度,即節(jié)點(diǎn)從屬度的模糊程度。而本文的團(tuán)間連接貢獻(xiàn)度B反映出節(jié)點(diǎn)在團(tuán)間連接中所起的作用大小。本質(zhì)上它們是完全不同的兩種概念,同時(shí)它們也都是網(wǎng)絡(luò)模糊分析中所特有的。團(tuán)間連接貢獻(xiàn)度指標(biāo)的提出,將研究引向?qū)?jié)點(diǎn)在網(wǎng)絡(luò)宏觀拓?fù)淠Ｊ街械挠绊懥Φ年P(guān)注,是本方法的一個(gè)獨(dú)特貢獻(xiàn)。無疑,關(guān)鍵連接點(diǎn)對(duì)團(tuán)間連接的穩(wěn)定性起到很大作用,如果要迅速切斷團(tuán)間聯(lián)系,改變網(wǎng)絡(luò)的宏觀拓?fù)涓窬?首先攻擊關(guān)鍵連接點(diǎn)(如海豚網(wǎng)中的SD100)是最有效的方法。團(tuán)間連接貢獻(xiàn)度這一定義的基礎(chǔ)來自于對(duì)團(tuán)與團(tuán)連接關(guān)系(Z)的定量刻畫,這個(gè)定量關(guān)系用以往的模糊隸屬度概念無法得到。由于W有明確的物理含義,使得由W導(dǎo)出的團(tuán)—團(tuán)關(guān)系Z也具有了物理含義,這對(duì)網(wǎng)絡(luò)的宏觀拓?fù)浞治龇浅?有利。
6 結(jié)束語
針對(duì)復(fù)雜網(wǎng)絡(luò)交疊團(tuán)現(xiàn)象,本文給出了一個(gè)新的聚類后模糊分析框架。它不僅能對(duì)網(wǎng)絡(luò)進(jìn)行模糊聚類,而且支持對(duì)交疊結(jié)構(gòu)的模糊分析,如關(guān)鍵點(diǎn)的識(shí)別和網(wǎng)絡(luò)宏觀拓?fù)鋱D的提取。使用這些新方法、新指標(biāo)能夠深入挖掘潛藏于網(wǎng)絡(luò)的拓?fù)湫畔?。從本文的聚類后分析不難看出,網(wǎng)絡(luò)模糊聚類的作用不僅在于聚類本身,還在于模糊聚類結(jié)果能夠?yàn)榫W(wǎng)絡(luò)拓?fù)渖钊敕治龊托畔⑼诰蛱峁┲С?而硬聚類則不能。今后將致力于對(duì)團(tuán)間連接貢獻(xiàn)度指標(biāo)進(jìn)行更為深入的統(tǒng)計(jì)研究。
參考文獻(xiàn):
[1]
趙鳳霞,謝福鼎.基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(6):2041-2043,2049.
[2]汪小帆,劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J].電子科技大學(xué)學(xué)報(bào),2009,38(5):537-543.
[3]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[4]WHITE S,SMYTH P.A spectral clustering approach to finding communities in graphs[C]//Proc of SIAM International Conference on Data Mining.2005.
[5]ENRIGHT A J,DONGEN S V,OUZOUNIS C A.An efficient algorithm for large-scale detection of protein families[J].Nucleic Acids Research,2002,30(7):1575-1584.
[6]BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press,1981.
[7]PALLA G,DERENYI I,FARKAS I,et al.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
?[8]REICHARDT J,BORNHOLDT S.Detecting fuzzy community structures in complex networks with a potts model[J].Physical Review Letters,2004,93(21):218701.
?[9]NEPUSZ T,PETROCZI A,N?GYESSY L,et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Physical Review E,2008,77(1):016107.
[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 Review A:Statistical Mechanics and Its Applications,2007,374(1):483-490.
[11]PAATERO P,TAPPER U.Positive matrix factorization:a non-negative factor model with optimal utilization of error estimates of data values[J].Environmetrics,1994,5(2):111-126.
[12]ANTTILA P,PAATERO P,TAPPER U,et al.Source identification of bulk wet deposition in Finland by positive matrix factorization[J].Atmospheric Environment,1995,29(14):1705-1718.
[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:Morgan Kaufmann,2002.
[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 isolation explain this unique trait?[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[15]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[16]ROSVALL M,BERGSTROM C T.An information-theoretic framework for resolving community structure in complex networks [J].Proceedings of the National Academy of Sciences of the United States of ?America,2007,104(18):7327-7331.