[發明專利]一種融合節點分析與邊分析的復雜網絡社區識別方法

有效

• 申請號: 202010516378.2
• 申請日: 2020-06-09
• 公開（公告）號: CN111698743B
• 公開（公告）日: 2022-09-13
• 發明（設計）人: 鄧琨;蔣慶豐;劉星妍
• 申請（專利權）人: 嘉興學院
• 主分類號: H04W36/00
• 分類號: H04W36/00;H04W48/16;G06Q50/00
• 代理公司: 北京勁創知識產權代理事務所(普通合伙) 11589
• 代理人: 徐家升

本發明公開了一種融合節點分析與邊分析的復雜網絡社區識別方法，包括初始化邊社區階段、擴展邊社區階段及擴展節點社區階段3個階段，具體如下：S1、所述初始化邊社區階段具體為：由于局部中心節點往往被認為是在局部范圍內擁有節點度較高的節點，對周圍的鄰居節點有較強的吸引力形成社區，因此，初始化邊社區階段首先搜索網絡中度較高的若干節點作為初始化邊社區階段的中心節點。本發明整合了邊與節點在社區識別過程中的優勢，分別在社區識別的不同階段從不同角度分析社區識別問題；其有效規避了單從邊與節點在社區識別過程中所存在弱點的同時，又提高了社區識別的穩定性與識別準確率。

技術領域

本發明涉及復雜網絡結構分析技術領域，具體涉及一種融合節點分析與邊分析的復雜網絡社區識別方法。

背景技術

近年來，復雜網絡結構分析在生物學、社會學、文獻計量學等領域已得到廣泛應用。復雜網絡具有分析這些特性的基本能力，大多數現實世界中的復雜網絡均可由社區組成。復雜網絡中的社區可定義為一組節點集合，這些節點在一個社區內彼此連接緊密，而社區間連接則較為松散。因此，人們可通過分析一個社區來獲得一組節點的功能、特征或屬性。鑒于復雜網絡中社區結構的實用性，社區識別已成為當今熱門的研究領域。

在現實世界的復雜網絡中，社區的重疊性是社區結構的一個重要特性，因此，復雜網絡中的重疊社區識別被廣泛關注，研究成果層出不窮。例如LFM算法(參見文獻：Lancichinetti A,Fortunato S,Kertesz J.Detecting the overlapping andhierarchical community structure in complex networks[J],New Journal ofPhysics,2009,11(3):033015)首先定義了適應度函數，然后算法沿著使適應度函數增加的方向擴展社區，直到每個社區的任意鄰居節點加入到該社區后，其相應的適應度函數值均為負時，則算法停止運行，因為每個社區在擴展過程中均較為獨立，且節點能夠被識別到不同社區中，因此，LFM算法可以識別出重疊社區。COPRA算法(參見文獻：Gregory S.Findingoverlapping communities in networks by label propagation[J].New Journal ofPhysics,2010,12(10):103018)首先為網絡中所有節點初始化標簽；然后，在標簽傳播過程中每個節點在每次迭代時，對其相鄰節點的隸屬系數進行平均，以更新其社區隸屬系數，每個節點的標簽也依據其隸屬系數選擇相應標簽。COPRA算法中設置了參數用于控制節點可以同時歸屬的最大社區數，并且刪除隸屬系數小于的節點標簽，當算法停止運行時標簽相同的節點被識別成一個社區，最終擁有多個標簽的節點被識別為重疊節點。以上算法均以節點為研究對象考慮社區識別問題，由于節點在社區識別過程中過于靈活，社區初始結構很難快速形成，傳統算法往往通過掌握先驗知識，預設參數閾值的方式，完成社區識別任務，但在紛繁復雜的網絡中，獲取先驗知識是一件難以實現的任務，在未知網絡中也是無法實現的。

鑒于以節點為研究對象展開重疊社區識別所存在的缺陷，Ahn等提出以邊為研究對象實現復雜網絡重疊社區識別的LC算法(參見文獻：Ahn Y Y,Bagrow J P,LehmannS.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764)，該算法的基本思想是邊在網絡中通常具有唯一角色而屬于單一社區，當網絡中的邊被識別到不同社區后，其相應的重疊節點也將自然顯現出來。該算法通過分析邊的相似度將邊進行聚類得到具有層次結構的邊社區，并通過對邊進行切割得到最終的社區結構。雖然邊社區識別方法具有穩定性高的優勢，但其依然存在識別社區“過度重疊”的現象。

綜上所述，以節點為研究對象和以邊為研究對象的社區識別均存在各自缺陷，使得社區識別的穩定性不高，因此，發揮邊與點的優勢，取長補短，完成社區識別任務，將是一個較為合理的方案。為此，我們提出一種融合節點分析與邊分析的復雜網絡社區識別方法。

發明內容