[發明專利]一種基于隸屬度傳播的復雜網絡模糊社團挖掘方法

在審

• 申請號: 201410801991.3
• 申請日: 2014-12-18
• 公開（公告）號: CN104657418A
• 公開（公告）日: 2015-05-27
• 發明（設計）人: 陳小武;張恒源;趙沁平;李甲;周彬
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

技術領域

本發明涉及復雜網絡、社團檢測和模糊聚類，特別是涉及復雜網絡中的模糊社團挖掘，具體地說是一種基于隸屬度傳播的復雜網絡模糊社團挖掘方法。

背景技術

節點的聚集現象是復雜網絡拓撲結構的重要特性，近十年以來，網絡中的社團結構分析成為了復雜網絡科學領域的前沿研究熱點之一。人們發現，真實世界中的復雜網絡常常可以被劃分為若干個社團。在同一社團內部，節點之間連接緊密，而屬于不同社團的節點之間則連接稀疏。發現網絡中的社團，可以揭示網絡的宏觀拓撲結構，從而能夠對不同領域的各種應用起到重要的支撐作用。當前對于網絡社團挖掘算法的研究，主要發源于美國密歇根大學的Girvan與Newman，他們提出了一個廣泛應用的社團劃分質量模塊度函數(modularity)。模塊度含義下的社團是一個子圖，且該子圖中的內部邊的數量，應該大于該子圖的隨機模型所產生的邊的數量。模塊度通常表示為Q，其定義如下：

Q=12m·Σi,j[(wij-deg(vi)·deg(vj)2m)·δ(Ci,Cj)]]]>

其中，w_ij為節點v_i和v_j之間的邊e_ij的權重，為網絡中所有邊的權重之和，deg(v_i)是節點v_i的度；Cⁱ表示v_i所屬的社團，δ(μ,υ)表示沖激函數，當μ＝υ時取值為1，否則取值為0。上式標明，若社團的內部邊的數量小于該其隨機模型所產生的邊的數量，則模塊度受到懲罰。模塊度的值介于0到1之間，越大則表明網絡具有越顯著的社團結構。

在目前眾多的網絡社團挖掘算法中，標簽傳播和模塊度優化是兩類最為流行的方法。標簽傳播利用信息擴散理論進行社團檢測，認為節點的社團屬性由其鄰居節點的社團屬性所決定。這一基本思想直觀、易與理解，且現實情況相符。然而，在標簽傳播算法中，節點的社團屬性僅考慮了其鄰居節點的因素，損失了大量的網絡拓撲信息，導致其性能的穩定性較差。當模塊度成為廣泛接受的網絡社團劃分質量度量指標后，網絡社團挖掘常常被轉化為對模塊度的優化問題。雖然模塊度函數存在分辨率限制的問題，但在實際應用中仍然取得了巨大成功。基于模塊度優化的社團挖掘方法，是目前最為流行、應用最為廣泛的網絡社團挖掘算法之一，具有較強的魯棒性和較高的檢測質量。然而，模塊度優化方法缺乏直觀的物理意義。