[發明專利]一種基于邊不穩定度的社區發現系統及方法

有效

• 申請號: 201611150384.0
• 申請日: 2016-12-14
• 公開（公告）號: CN106599187B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 王雷;王新晨;李涵
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06Q50/00
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 楊學明;顧煒

本發明為一種基于邊不穩定度的社區發現系統及方法，屬于軟件工程和數據分析領域。本發明的社區發現方法基于邊不穩定度，在傳統社區發現算法的基礎上實現，首先將軟件函數調用圖作為一個網絡，定義了邊不穩定度的概念；然后在傳統社區發現算法的基礎上結合邊不穩定度進行改進，主要包括：改進的Fast Unfolding算法，改進的GN算法。本發明的社區發現算法在傳統算法的基礎上，增加了更好的劃分標準，在一定程度上可以提高社區發現算法的效率。

技術領域

本發明涉及一種基于邊不穩定度的社區發現系統及方法，屬于軟件工程和數據分析技術領域。

背景技術

復雜網絡社區發現早已成為計算機科學、生物學、社會信息學等多個領域的研究熱點之一，如何準確、高效的發現復雜網絡中存在的具有社區特性的系統結構分布，一直以來是值得深入研究的問題。

網絡是一種包含節點和邊(或連接)的集合，通常節點代表該系統的組成成員，而邊(或連接)用以描述系統成員間的相互作用關系。相對而言，復雜網絡具有以下特征：(1)網絡規模非常大，節點和邊的規模數以萬計，傳統方法對此等規模的系統只能借助系統的統計學特征進行初步的探測之后再分析。(2)網絡結構的復雜性和多樣性：現實世界中的網絡結構通常不是絕對隨機也不會是絕對規律，而是兩者的結合體，同時組成網絡的大量子單元和子系統結構復雜多變。(3)網絡節點類型不一，對于不同的研究對象其意義不同，同時節點間相互作用也錯綜復雜，其表現有二：一是權值的多樣性，而是結構的非均勻性。(4)網絡具有時空復雜性，一般研究模型為靜態，但實際上隨著時間空間變遷，網絡會動態演化，其節點數增加，同時節點間連接方式和權重也會不斷變化，網絡拓撲結構和動力學性質也會改變。

復雜網絡具有如下特性：(1)小世界效應，對于網絡G，若其平均節點維度不變，網絡的平均距離以不大于網絡規模對數的速度增長，小世界效應對于網絡結構研究有重要意義，例如考慮信息在網絡上的擴散路徑，小世界效應表明信息在網絡中僅僅需要少數幾個的步驟就可以非常快的擴散到整個網絡，在流行病傳播網絡中僅需要較少中間人即可大范圍傳播，在互聯網上去除少數關鍵性節點處的主機或路由即可造成大范圍網絡癱瘓。(2)傳遞性或群聚屬性，對于網絡中的節點A，B，C，如果節點A與B之間存在一條邊，B與C之間也有一條邊，則節點A有較大的概率與節點C之間也存在一條邊，此即傳遞性(生物網中又稱為群聚性)。一種顯而易見的現象就是，在人們的個人朋友圈內，朋友之間本身也存在朋友關系，送種關系的逐個傳遞形成一個群落，在社會網和生物網中尤為常見。(3)無標度性，Newmand等發現網絡中各不同節點度數在整個網絡總度數的占比呈冪律分布。(4)社區特性，2002年，Girvan和Newman發現復雜網絡分布中存在一種新的統計特征“社區結構”后很快就吸引了研究復雜網絡相關領域專家學者們的關注，并隨之迅速成為一個新的研究熱點。復雜網絡普遍存在一種“同一社區內節點連接緊密，不同化區間節點連接稀疏”的特征。圖1是一個簡單的社區結構網絡實例，圖中有3個黑色陰影背景的網絡簇，網絡簇之間僅有較少邊連接，此圖代表了一個具有3個結構明顯的社區的網絡。把軟件中的函數抽象為網絡圖中的一個結點，把函數之間的調用關系抽象為一條有向邊，那么就構成了軟件函數調用圖。函數調用圖也屬于復雜網絡的一種，具備小世界和無標度等特征。

現實情況網絡劃分成社區之前社區數目及每個社區的規模都是未知的，如何有效的評價網絡的一系列社區結構劃分質量，模塊化函數Q為此提供參考。自2004年由Newman和Girvan提出該理論后已被相關領域學者廣泛接受并在實際應用中獲得很大成功，以函數Q作為目標函數的進行優化的方法已成為一種共識。

2004年Newman在提出一種計算網絡社區結構劃分好壞的模塊性函數Q之后提出了W該函數Q作為目標化化函數，通過迭代的進行節點或社區聚合的社區挖掘算法FN，以模塊函數Q來看越明顯的網絡社區結構其Q值越大，FN算法迭代搜索規則是每次選擇兩個原始社區合并，合并的兩個原始社區必須獲得最大的Q增長。