復雜網(wǎng)絡圖中高密度子圖檢測方法與實現(xiàn).pdf

1、復雜網(wǎng)絡圖計算是當今數(shù)據(jù)挖掘領域最重要的研究課題之一。揭示復雜網(wǎng)絡圖中高密度子圖結(jié)構對分析復雜網(wǎng)絡的拓撲結(jié)構、發(fā)現(xiàn)其中隱含的模式、以及預測網(wǎng)絡進一步的行為和功能都具有十分重要的理論意義，在生物網(wǎng)、社交網(wǎng)和信息網(wǎng)等復雜網(wǎng)絡關系分析中有著廣泛應用。
　　本文提出兩種揭示復雜網(wǎng)絡圖中高密度子圖的方法，第一種為基于圖分割的k-邊連通子圖計算方法（MSK），該方法首先根據(jù)節(jié)點間緊密程度計算節(jié)點序列L。在計算序列過程中，應用節(jié)點合并策略，將滿

2、足 k-邊連通性的節(jié)點合并成為超級節(jié)點；應用提前分割策略，使得每發(fā)現(xiàn)值小于 k的割，刪除割中的邊，將子圖提前分割，提高算法時間效率。通過迭代執(zhí)行上述步驟，直到圖中只剩下孤立節(jié)點，任意節(jié)點之間都不存在連邊，此時每一個超級節(jié)點對應原圖中的一個 k-邊連通子圖，算法結(jié)束。進一步給出近似算法 PMSK，忽略因應用提前分割策略而導致的節(jié)點之間 k-邊連通性的變化，進一步提高計算的時間效率。第二種方法為基于同步動力學模型的聚類方法（SYN）。首先，

3、按照網(wǎng)絡中節(jié)點之間鄰居相似度關系對節(jié)點進行排序，此時，每一個節(jié)點對象使用唯一的一維坐標值表示，達到網(wǎng)絡矢量化。然后，在同步過程中，基于局部鄰域，實現(xiàn)局部同步子圖發(fā)現(xiàn)。在節(jié)點同步的鄰域半徑不斷擴大的過程中，得到很多子圖劃分，結(jié)合模塊度函數(shù)，選擇最佳聚類結(jié)果，因此子圖劃分更加符合高密度子圖內(nèi)部結(jié)構相對緊密、子圖之間結(jié)構相對稀疏的性質(zhì)。本文方法不依賴于任何數(shù)據(jù)分布假設，可以自動檢測任意形狀、任意大小和數(shù)量的子圖。
　　在大量人工數(shù)據(jù)集和