[發明專利]動態網絡社區結構的更新方法及裝置

有效

• 申請號: 201210185451.8
• 申請日: 2012-06-06
• 公開（公告）號: CN102722750A
• 公開（公告）日: 2012-10-10
• 發明（設計）人: 尚家興;劉連臣;謝峰;陳安燕;徐磊
• 申請（專利權）人: 清華大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

技術領域

本發明涉及動態網絡社區技術領域，特別涉及一種基于增量更新策略的動態網絡社區結構的更新方法及裝置。

背景技術

現實世界中的很多系統都可以以網絡圖的形式來表示，圖中的節點代表個體，邊代表個體之間的相互關系，典型的例子有社會關系網絡、引文網絡、生物網絡、移動電話網絡、以及犯罪組織網絡等。對于這種復雜網絡的分析，一個重要的問題就是網絡中的社區結構的檢測與識別，所謂社區結構是指將網絡中的節點劃分到不同的分組（社區）中，這種劃分具有如下特點：社區內部的節點之間聯系緊密，而不同社區之間的節點聯系稀疏。以物種的地理分布為例，同一個種群中的個體組成一個社區，可以發現大多數情況下，種群內的個體只與同一個種群內的其他個體發生聯系，而很少與其他種群（外部社區）的個體發生聯系。網絡社區的檢測和識別可以幫助我們發現復雜網絡中的一些深層次信息，如網絡犯罪組織、人群中潛在的共同興趣愛好、具有核心影響力的網絡節點等，因而可以應用到犯罪偵查、協同過濾、輿情監控等各個方面。在近幾年的研究中，人們提出了大量用于識別網絡社區的方法，其中具有代表性的是Newman等人于2004年提出的基于Modularity的算法，該算法中，Newman以Modularity作為評價社區結構好壞的度量標準，它的物理意義是：如果一個社區結構越滿足社區內部的節點聯系緊密，社區之間的節點聯系稀疏的特點，那么這個社區結構對應的Modularity值就越大。這樣，社區識別問題就轉化為一個求解最優社區結構，使其對應的Modularity值最大的優化問題。然而，Newman同時在文章中指出，求解Modularity的全局最優解是NP難的，因而限制了其在大規模網絡上的應用。

在Newman提出了基于Modularity的算法之后，很多人做了相應的改進，提出了大量求解次優解的啟發式算法，在算法效率上做出了很大的提高,目前已知的基于Modularity的最快算法是由Blondel等人于2008年提出的LOUVAIN算法，它能夠在有限時間內處理規模為1億個節點，10億條邊的網絡，此外，該算法得到的社區結構對應的Modularity值也相當高。雖然基于Modularity的算法已經得到了很大的改進并且被成功運用到了許多真實的網絡中，但是這些算法都有一個共同的缺點：都是靜態算法，只能處理靜態的網絡，當網絡發生變化時（例如增加一個節點或一條邊），需要對整個網絡重新運行算法來得到最新的社區結構，對于規模較大且動態性較高的網絡來說，頻繁運行靜態算法來跟蹤社區結構顯然是不現實的。

發明內容

本發明的目的旨在至少解決上述技術缺陷之一。

為此，本發明的一個目的在于提出一種更新速度快，計算的時間復雜度低的動態網絡社區結構的更新方法。

本發明的另一目的在于提出一種動態網絡社區結構的更新裝置。

為了實現上述目的，本發明的實施例提出了一種動態網絡社區結構的更新方法，包括如下步驟：對由多個節點組成的初始網絡進行計算，以生成網絡初始社區結構；根據節點之間的交互判斷新加入的邊的類型，其中，所述新加入的邊的類型包括社區內部邊、跨社區的邊、半新邊和全新邊；以及根據所述新加入的邊的類型選擇對應的增量更新策略對所述網絡初始社區結構進行更新以得到網絡更新社區結構。

另外，根據本發明上述實施例的動態網絡社區結構的更新方法還可以具有如下附加的技術特征：

在一些示例中，所述增量更新策略的選擇依據為：選擇使得網絡初始社區結構的Modularity值的增量最大的增量更新策略。

在一些示例中，所述增量更新策略的選擇依據進一步包括：如果不存在對所述網絡初始社區結構的Modularity值帶來增量的增量更新策略，則選擇使得網絡初始社區結構的Modularity值的減少量最小的增量更新策略。

在一些示例中，所述網絡初始社區結構是通過LOUVAIN算法得到的。

在一些示例中，所述增量更新策略包括保持社區結構不變的更新策略、將兩個社區合并為一個社區的更新策略、將新加入的節點加入到已存在的社區的更新策略以及創建新社區的更新策略。