關于計算機復雜網絡交疊團分析與信息挖掘研究論文

導語：關于計算機復雜網絡交疊團分析與信息挖掘研究論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

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

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

關鍵詞:網絡模糊聚類;團—點相似度;團間連接緊密度;團間連接貢獻度;對稱非負矩陣分解;網絡宏觀拓撲

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

現有的網絡重疊團結構提取方法[6~10]多數只對團間模糊點進行初步分析,如Nepusz等人[9,10]的模糊點提取。針對網絡交疊團結構的深入拓撲分析,本文介紹一種新的團—點相似度模糊度量。由于含有確定的物理含意和更為豐富的拓撲信息,用這種模糊度量可進一步導出團與團的連接緊密程度,以及模糊節點對兩團聯系的貢獻程度,并設計出新指標和定量關系來深度分析網絡宏觀拓撲連接模式和提取關鍵連接節點。本文在三個實際網絡上作了實驗分析,其結果表明,本方法所挖掘出的網絡拓撲特征信息為網絡的模糊聚類后分析提供了新的視角。

1新模糊度量和最優化逼近方法

設A=[Aij]n×n(Aij≥0)為n點權重無向網絡G(V,E)的鄰接矩陣,Y是由A產生的特征矩陣,表征點—點距離,Yij>0。假設圖G的n個節點劃分到r個交疊團中,用非負r×n維矩陣W=[Wki]r×n來表示團—點關系,Wki為節點i與第k個團的關系緊密程度或相似度。W稱為團—點相似度矩陣。令Mij=rk=1WkiWkj(1)

若Wki能精確反映點i與團k的緊密度,則Mij可視為對點i、j間相似度Yij的一個近似。所以可用矩陣W來重構Y,視為用團—點相似度W對點—點相似度Y的估計:

WTW→Y(2)

用歐式距離構造如下目標函數:minW≥0FG(Y,W)=‖Y-WTW‖F=12ij[(Y-WTW)。(Y-WTW)]ij(3)

其中:‖•‖F為歐氏距離;A。B表示矩陣A、B的Hadamard矩陣乘法。由此,模糊度量W的實現問題轉換為一個最優化問題,即尋找合適的W使式(3)定義的目標函數達到最小值。

式(3)本質上是一種矩陣分解,被稱為對稱非負矩陣分解,或s-NMF(symmetricalnon-negativematrixfactorization)。s-NMF的求解與非負矩陣分解NMF[11,12]的求解方法非常類似。非負矩陣分解將數據分解為兩個非負矩陣的乘積,得到對原數據的簡化描述,被廣泛應用于各種數據分析領域。類似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)的迭代結果必落入NMF的穩定點集合中符合附加條件(H=W)的部分,由此決定s-NMF的收斂性。

在求解W之前還需要確定特征矩陣。本文選擴散核[13]為被逼近的特征矩陣。擴散核有明確的物理含義,它通過計算節點間的路徑數給出任意兩節點間的相似度,能描述網絡節點間的大尺度范圍關系,當兩點間路徑數增加時,其相似度也增大。擴散核矩陣被定義為K=exp(-βL)(5)

其中:參數β用于控制相似度的擴散程度,本文取β=0.1;L是網絡G的拉普拉斯矩陣:

Lij=-Aiji≠j

kAiki=j(6)

作為相似度的特征矩陣應該是擴散核矩陣K的歸一化形式:

Yij=Kij/(KiiKjj)1/2(7)

基于擴散核的物理含義,團—點相似度W也具有了物理含義:團到點的路徑數。實際上,W就是聚類結果,對其列歸一化即可得模糊隸屬度,需要硬聚類結果時,則選取某點所對應列中相似度值最大的團為最終所屬團。

2團—團關系度量

團—點相似度W使得定量刻畫網絡中的其他拓撲關系成為可能。正如WTW可被用來作為點與點的相似度的一個估計,同樣可用W來估計團—團關系:

Z=WWT(8)

其物理含義是團與團間的路徑條數。很明顯,Z的非對角元ZJK刻畫團J與團K之間的緊密程度,或團間重疊度,對角元ZJJ則刻畫團J的團內密度。

以圖1中的對稱網絡為例,二分團時算得

Z=WWT=1.33760.0353

0.03531.3376

由于圖1中的網絡是對稱網絡,兩團具有同樣的拓撲連接模式,它們有相同的團內密度1.3376,而團間重疊度為0.0353。

3團間連接貢獻度

ZJK度量了團J與團K間的重疊程度:

ZJK=na=1WJaWKa(9)

其中:WJaWKa是這個總量來自于點a的分量。下面定義一個新指標來量化給定點對團間連接的貢獻。假設點i是同時連接J、K兩團的團間某點,定義點i對團J和團K的團間連接貢獻度為

Bi=[(WJiWKi)/(na=1WJaWKa)]×100%(10)

顯然,那些團間連接貢獻大的點應處于網絡中連接各團的關鍵位置,它們對團間連接的穩定性負主要責任。將這種在團與團間起關鍵連接作用的點稱為關鍵連接點。為了設定合適的閾值來提取團間關鍵連接點,本文一律取B>10%的點為關鍵連接點。

4實驗與結果分析

下面將在三個實際網絡上展開實驗,首先根據指定分團個數計算出團—點相似度W,然后用W計算團—團關系和B值,并提取關鍵連接點。

4.1海豚社會網

由Lusseau等人[14]給出的瓶鼻海豚社會網來自對一個62個成員的瓶鼻海豚社會網絡長達七年的觀測,節點表示海豚,連線為對某兩只海豚非偶然同時出現的記錄。圖2(a)中名為SN100(點36)的海豚在一段時間內消失,導致這個海豚網絡分裂為兩部分。

使用s-NMF算法聚類,海豚網絡分為兩團時,除30和39兩點外,其他點的分團結果與實際觀測相同,如圖2(a)所示。計算B值并根據閾值提取出的五個關鍵連接點:1、7、28、36、40(虛線圈內),它們對兩團連接起到至關重要的作用。圖2(b)為這五點的B值柱狀圖。該圖顯示,節點36(SN100)是五個關鍵連接點中B值最大者,對連接兩團貢獻最大。某種程度上,這個結果可以解釋為什么海豚SN100的消失導致了整個網絡最終分裂的影響。本例說明,s-NMF算法及團間連接貢獻程度指標在分析、預測社會網絡演化方面有著獨具特色的作用。

4.2SantaFe科學合作網

用本算法對Newman等人提供的SantaFe科學合作網絡[15]加以測試。271個節點表示涵蓋四個學術領域的學者,學者合作發表文章產生網絡連接,構成了一個加權合作網絡。將本算法用于網絡中一個包含118個節點的最大孤立團,如圖3(a)所示。公務員之家

圖3(a)中,四個學科所對應的主要組成部分都被正確地分離出來,mathematicalecology(灰菱形)和agent-basedmodels(白方塊)與文獻[15]的結果一致,中間的大模塊statisticalphysics又被細分為四個小塊,以不同灰度區分。計算了24個點的團間連接度貢獻值B,從中分離出11個B值大于10%的點作為關鍵連接點:1、2、4、6、11、12、20、47、50、56、57,其標號在橫軸下方標出,見圖3(b),并在圖3(a)中用黑色圓圈標記,這些連接點對應那些具有多種學科興趣、積極參與交叉研究的學者。除去這11個點時,整個網絡的連接布局被完全破壞,見圖3(a)下方灰色背景縮小圖,可見關鍵連接點的確起到重要的溝通各模塊的作用。

4.3雜志索引網絡

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

由本算法得出的團—點相似度W在網絡宏觀拓撲結構的挖掘方面有非常有趣的應用,如第2章所述,用W計算團—團相似度矩陣Z=WWT,其對角元是團內連接密度,非對角元表征團與團的連接緊密程度,故Z可被視為對原網絡的一種“壓縮表示”。如果將團換成“點”,將團與團之間的連接換成“邊”,利用Z的非對角元,就能構造出原網絡的一個壓縮投影網絡,如圖4(b)所示。這是原網絡的一個降維示意圖,也是團與團之間關系定量刻畫的形象表述,定量地反映了原網絡在特定分團數下的“宏觀(全局)拓撲輪廓”,圖上團間連線色深和粗細表示連接緊密程度。由圖4(b)可以看到,physics和chemistry連接最緊密,而chemistry與biology和biology與ecology次之。由此推測,如果減少分團數,將相鄰兩團合并,連接最緊密的兩團必首先合并為一個團。實際情況正是如此:分團數為3時,biology和ecology各自獨立成團,physics和chemistry合并為一個大團,這與文獻[11]結果一致。

5討論

網絡模糊聚類能幫助研究者進一步對團間的一些特殊點進行定量分析,如Nepusz等人[9]用一種橋值公式來刻畫節點在多個團間的共享程度,即節點從屬度的模糊程度。而本文的團間連接貢獻度B反映出節點在團間連接中所起的作用大小。本質上它們是完全不同的兩種概念,同時它們也都是網絡模糊分析中所特有的。團間連接貢獻度指標的提出,將研究引向對節點在網絡宏觀拓撲模式中的影響力的關注,是本方法的一個獨特貢獻。無疑,關鍵連接點對團間連接的穩定性起到很大作用,如果要迅速切斷團間聯系,改變網絡的宏觀拓撲格局,首先攻擊關鍵連接點(如海豚網中的SD100)是最有效的方法。團間連接貢獻度這一定義的基礎來自于對團與團連接關系(Z)的定量刻畫,這個定量關系用以往的模糊隸屬度概念無法得到。由于W有明確的物理含義,使得由W導出的團—團關系Z也具有了物理含義,這對網絡的宏觀拓撲分析非常有利。

6結束語

針對復雜網絡交疊團現象,本文給出了一個新的聚類后模糊分析框架。它不僅能對網絡進行模糊聚類,而且支持對交疊結構的模糊分析,如關鍵點的識別和網絡宏觀拓撲圖的提取。使用這些新方法、新指標能夠深入挖掘潛藏于網絡的拓撲信息。從本文的聚類后分析不難看出,網絡模糊聚類的作用不僅在于聚類本身,還在于模糊聚類結果能夠為網絡拓撲深入分析和信息挖掘提供支持,而硬聚類則不能。今后將致力于對團間連接貢獻度指標進行更為深入的統計研究。

參考文獻:

[1]趙鳳霞,謝福鼎.基于K-means聚類算法的復雜網絡社團發現新方法[J].計算機應用研究,2009,26(6):2041-2043,2049.

[2]汪小帆,劉亞冰.復雜網絡中的社團結構算法綜述[J].電子科技大學學報,2009,38(5):537-543.

[3]NEWMANMEJ.Modularityandcommunitystructureinnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2006,103(23):8577-8582.

[4]WHITES,SMYTHP.Aspectralclusteringapproachtofindingcommunitiesingraphs[C]//ProcofSIAMInternationalConferenceonDataMining.2005.

[5]ENRIGHTAJ,DONGENSV,OUZOUNISCA.Anefficientalgorithmforlarge-scaledetectionofproteinfamilies[J].NucleicAcidsResearch,2002,30(7):1575-1584.

[6]BEZDEKJC.Patternrecognitionwithfuzzyobjectivefunctionalgorithms[M].NewYork:PlenumPress,1981.

[7]PALLAG,DERENYII,FARKASI,etal.Uncoveringtheoverlappingcommunitystructuresofcomplexnetworksinnatureandsociety[J].Nature,2005,435(7043):814-818.

[8]REICHARDTJ,BORNHOLDTS.Detectingfuzzycommunitystructuresincomplexnetworkswithapottsmodel[J].PhysicalReviewLetters,2004,93(21):218701.

[9]NEPUSZT,PETROCZIA,NGYESSYL,etal.Fuzzycommunitiesandtheconceptofbridgenessincomplexnetworks[J].PhysicalReviewE,2008,77(1):016107.

[10]ZHANGShi-hua,WANGRui-sheng,ZHANGXiang-sun.IdentificationofoverlappingcommunitystructureincomplexnetworksusingfuzzyC-meansclustering[J].PhysicalReviewA:StatisticalMechanicsandItsApplications,2007,374(1):483-490.

[11]PAATEROP,TAPPERU.Positivematrixfactorization:anon-negativefactormodelwithoptimalutilizationoferrorestimatesofdatavalues[J].Environmetrics,1994,5(2):111-126.

[12]ANTTILAP,PAATEROP,TAPPERU,etal.SourceidentificationofbulkwetdepositioninFinlandbypositivematrixfactorization[J].AtmosphericEnvironment,1995,29(14):1705-1718.

[13]KONDORRI,LAFFERTYJ.Diffusionkernelsongraphsandotherdiscretestructures[C]//Procofthe19thInternationalConferenceonMachineLearning.SanFrancisco:MorganKaufmann,2002.

[14]LUSSEAUD,SCHNEIDERK,BOISSEAUOJ,etal.Thebottlenosedolphincommunityofdoubtfulsoundfeaturesalargeproportionoflong-lastingassociations:cangeographicisolationexplainthisuniquetrait?[J].BehavioralEcologyandSociobiology,2003,54(4):396-405.

[15]GIRVANM,munitystructureinsocialandbiologicalnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99(12):7821-7826.

[16]ROSVALLM,BERGSTROMCT.Aninformation-theoreticframeworkforresolvingcommunitystructureincomplexnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2007,104(18):7327-7331.