[發明專利]面向網絡的重疊社區發現方法

在審

• 申請號: 201310277647.4
• 申請日: 2013-07-03
• 公開（公告）號: CN103425737A
• 公開（公告）日: 2013-12-04
• 發明（設計）人: 呂林濤;楊維維;孫飛龍;譚芳
• 申請（專利權）人: 西安理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 西安弘理專利事務所 61214
• 代理人: 李娜

技術領域

本發明屬于網絡社區發現方法，涉及一種面向網絡的重疊社區發現方法。

背景技術

現實世界中包含著各種類型的復雜網絡，如社會網絡、技術網絡、生物學網絡、網絡中頁面之間相互鏈接而形成的網絡、論文合著網絡、文獻引用網絡等等。這些現實世界中大量的復雜網絡是由許多不同類型的節點組合而成，其中相同的類型節點之間存在的連接比較多，而不同類型節點的連接卻相對較少，復雜網絡的這種特性稱為社區結構。

目前關于社區結構發現的研究己經取得了一定的進展，并且提出了許多社區結構發現方法，應用較多的有:Kernighan-lin方法、GN方法、譜平分法、極值優化方法等,然而，大多數的社區結構發現方法都是假定社區是彼此不重疊的，這就意味著一個節點只能屬于一個社區，但是在現實生活中，社區之間是有可能重疊的。例如，在科研合作網絡中，某一個學者有可能同時在多個不同的領域與人合作;在生物網絡中，某一種蛋白質有可能與多種其他的蛋白質相互作用，這樣就有可能有某些節點同時屬于多個社區;在社會網絡中，某一個興趣廣泛的人有可能參加多個不同的社區活動。發現復雜網絡中的重疊社區結構有助于我們更好地理解復雜網絡的拓撲結構，對社區中重疊部分的研究有助于我們開啟新的思路解決網絡擁塞、計算機病毒、輿論的傳播和流行病毒傳播等問題。現有的社區發現方法對重疊社區發現的準確率較低，尤其對于大規模網絡。

發明內容

本發明的目的在于提供一種面向網絡的重疊社區發現方法，解決現有技術對重疊社區發現的準確率低的問題。

本發明方法所采用的技術方案是，面向網絡的重疊社區發現方法，通過非重疊社區劃分的結果初始化網絡的節點，然后采用基于模糊合作博弈的方法求社區之間的重疊點，實現網絡的重疊社區劃分，具體步驟如下：

步驟1、選取非重疊社區發現方法進行社區劃分,不包含社區的重疊點；

步驟2、重新確定隸屬函數，計算節點屬于每個社區的隸屬度；

步驟3、重新確定收益函數，計算節點加入到社區后的社區的收益；

步驟4、根據計算的節點的隸屬度、節點加入社區后社區的收益求社區的重疊點，實現網絡的重疊社區劃分。

本發明的特點還在于：

步驟2中，對每個和節點i相連的社團C，這個節點加入到社團C的隸屬函數可以表示為：

membershipc(i)=Σm<nshort_distmn(i)/short_distmn---(1)]]>

式中，m、n分別表示社區C中兩個不相同的節點，short_dist_mn表示節點m和節點n之間的最短路徑數，表示節點m和節點n之間經過節點i的最短路徑數；在具有n個節點的社區中，對于給定的節點i來說，最為極端的情況是任意兩個其他節點之間的最短路徑均經過節點i，那么此時，該節點的membership_C(i)達到最大值(n-1)(n-2)/2.因此，歸一化的membership_C(i)可以定義為:

membership_C(i)＝membership_C(i)/[(n-1)(n-2)/2]????（2）

步驟3中，通過EQ函數來作為節點加入到社區后網絡的總體收益，EQ值越大，表明網絡的整體收益越大，那么，收益函數定義為:

revenge(C)＝EQ????????????（3）

節點i加入社區后社區C的收益變化為：

Δrevenge(C)＝ΔEQ??????????（4）