[發明專利]基于兩階段策略的非重疊與重疊網絡社區檢測方法

有效

• 申請號: 201310404906.5
• 申請日: 2013-09-07
• 公開（公告）號: CN103455612A
• 公開（公告）日: 2013-12-18
• 發明（設計）人: 慕彩紅;焦李成;劉勇;吳建設;熊濤;馬文萍;劉若辰;霍利利;謝瑾
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

技術領域

本發明屬于計算機技術領域，更進一步涉及人工智能該領域的基于非重疊與重疊網絡的社區檢測方法。本發明可用于社交網絡、大規模集成電路、生物大分子結構分析和功能預測等實際應用中。

背景技術

現實世界的很多復雜系統都可以表示為網絡，如萬維網，電力網，生物網絡和社交網絡等。除了小世界效應，無標度等網絡屬性外，復雜網絡中的另一個重要屬性是社區結構。社區是指網絡中相似度較高或相互連接緊密的節點的集合。分析現實世界中網絡的社區結構對生產生活具有重要的指導意義。在這些網絡的社區結構中，社區之間很多并不是單純的相互隔離的，而是相互重疊，形成更加復雜的網絡結構。

目前，已存在多種復雜網絡社區檢測方法，按照網絡結構的特點可分為非重疊網絡社區檢測和重疊網絡社區檢測。

福建師范大學在其申請的專利“一種基于集成學習的社會網絡重疊社區發現方法”（專利申請號201210371876.8，公開號CN102959942A）中公開了一種基于集成學習的社會網絡重疊社區發現方法。該方法通過快速譜聚類方法對網絡進行社區劃分，能有效的發現網絡的重疊社區結構，但是該方法存在的不足是，不能以不同分辨率分析網絡結構。

西安電子科技大學在其申請的專利“基于自動相轉換聚類的重疊社區網絡檢測方法”（專利申請號201210085015.3，公開號CN102611588A）中公開了一種基于自動相轉換聚類的重疊社區網絡檢測方法。該方法通過迭代進行更新節點相位操作，提高了收斂速度，能有效發現重疊社區。但是該方法存在的不足是，不能檢測非重疊網絡社區結構，而且該方法收斂速度慢。

發明內容

本發明的目的在于克服上述已有技術的不足，提出基于兩階段策略的非重疊與重疊網絡社區檢測方法。本發明通過將擴展模塊密度函數作為適應度函數，引入隸屬度函數作重疊點檢測手段，加入模擬退火法作為局部檢測策略，能有效檢測網絡中非重疊與重疊網絡社區結構，同時解決了現有網絡社區結構檢測方法中的分辨率限制、易陷入局部最優等缺點，提高了網絡社區檢測的準確度。

本發明的具體實施步驟如下：

(1)載入網絡數據：

構造網絡的鄰接矩陣A(N*N)，N為網絡中節點的數目，若網絡社區節點i與網絡社區節點j有連接時，鄰接矩陣中的元素a_ij=1；若網絡社區節點i與網絡社區節點j無連接，則a_ij=0。

(2)初始化網絡社區種群：

采用直接編碼方式，隨機生成N個不超過網絡社區節點數目的整數數值，將這些整數數值分別標記給每條染色體上的S個基因位；重復以上操作，直至得到W條染色體，每條染色體代表一種網絡社區劃分，將W條染色體組成網絡社區種群θ。

(3)劃分網絡社區種群：

3a)通過適應度函數，計算網絡社區種群θ中每個網絡社區劃分的適應度值；

3b)將網絡社區種群θ中所有網絡社區劃分的適應度值由高到低進行排序，將排序中前40%的適應度值對應的網絡社區劃分劃分為精英網絡社區種群，剩余部分劃分為普通網絡社區種群。

(4)組建網絡社區團隊：

將精英網絡社區種群中的每個網絡社區劃分設定為基礎網絡社區劃分，分別將每個基礎網絡社區劃分與普通網絡社區種群中的網絡社區劃分組建成網絡社區團隊，每個網絡社區團隊中網絡社區劃分的數目如下：

其中，G表示每個網絡社區團隊中網絡社區劃分的數目，表示向上取整數個網絡社區劃分操作，W表示精英網絡社區種群與普通網絡社區種群的總規模，M表示網絡社區團隊的數目。

(5)檢測候選網絡社區劃分：

5a)對每個網絡社區團隊在(0,1)區間內隨機生成一個隨機概率p，當隨機概率p大于0.5時，在精英網絡社區種群中隨機選擇一個網絡社區劃分B，執行步驟5b)；當隨機概率p小于0.5時，在普通網絡社區種群中隨機選擇一個網絡社區劃分C，執行步驟5c)；

5b)通過對當前網絡社區團隊的基礎網絡社區劃分E和網絡社區劃分B進行協作操作，檢測得到候選的網絡社區劃分δ；

5c)通過對當前網絡社區團隊的基礎網絡社區劃分E和網絡社區劃分C進行引導操作，檢測得到候選的網絡社區劃分φ。

(6)更新網絡社區種群：

將檢測得到的網絡社區劃分δ或網絡社區劃分φ與原網絡社區種群θ進行融合，得到過渡網絡社區種群，將過渡網絡社區種群中所有網絡社區劃分按適應度值排序，排序中前450個適應度值所對應的網絡社區劃分組成網絡社區種群α。

(7)檢測局部網絡社區：