[發明專利]一種基于局部結構的密度最大化重疊社團發現方法及系統

在審

• 申請號: 202010678380.X
• 申請日: 2020-07-15
• 公開（公告）號: CN111861772A
• 公開（公告）日: 2020-10-30
• 發明（設計）人: 陳潔;王惠君;趙姝;張燕平
• 申請（專利權）人: 安徽大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62;G06F16/953
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙) 34124
• 代理人: 張祥

本發明提供了一種基于局部結構的密度最大化重疊社團發現方法，包括：步驟A：將待劃分社團抽象成由節點連接成的抽象網絡；步驟B：獲得每個節點的度，以度最大的節點及其鄰居節點構建初始化社團中；步驟C：對剩余節點重復步驟B，直到抽象網絡中不存在未劃分的節點；步驟D：依次判斷小社團中的節點能否添加到大社團中，對初始化社團進行擴張；步驟E：對擴張后的社團判斷是否滿足合并條件，將滿足合并條件的社團進行合并，輸出社團劃分結果。本發明還提供了基于上述方法的系統。本發明的優點在于：通過種子節點的選取確定初始化社團，根據社團擴張的結果判斷能否合并，提高社團劃分結果的準確性和擴張效率。

技術領域

本發明涉及社團劃分技術領域，尤其涉及一種基于局部結構的密度最大化重疊社團發現方法及系統。

背景技術

網絡廣泛存在于我們的現實生活中，如社會系統中的社交網，生物系統中的蛋白質交互網絡，計算機網絡中的萬維網和因特網等，這些網絡中的每一個個體通過信息交換通道與其它的個體連接。隨著對網絡的深入研究，人們發現許多實際網絡中都存在著社團結構，即整個網絡由若干個社團構成。例如，可以將現實中存在的網絡，如計算機網絡中的每一臺設備抽象成一個節點，而各個節點之間的網絡通道可以抽象成節點之間的邊，可以發現，每個社團內部的節點與節點之間連接相對緊密，而社團之間的連接相對比較稀疏。為了實現對網絡的分析，需要根據節點之間的關聯關系，尋找聯系緊密的小型社團結構，該過程可以被稱為社團劃分或社團發現。近年來，隨著研究的深入，人們發現許多現實世界網絡包含重疊的社區，一個節點屬于多個社區是很常見的。例如，在生物學中，很大一部分蛋白質同時屬于幾種蛋白質復合物。在社交網絡中，用戶可以屬于眾多社區(家庭，運動，音樂等)。那么發現重疊的社團結構對于理解社團內部以及社團之間的信息交互和動態演化都具有重要意義。因此，對于重疊社團劃分的研究是十分必要的。

目前，人們已經提出許多重疊社團發現算法，主要分為以下幾種：基于團滲透理論的重疊社團發現算法(CPM)、使用統計學意義的方法(OSLOM)、使用種子節點擴張或優化目標的算法、基于矩陣分解的算法(NMF)、基于標簽傳播的算法(LPA)和分層的重疊社團發現算法(LFM)。這些現有的重疊社團發現算法從局部到全局再從靜態到動態充分考慮了不同角度不同層面的重疊社團結構，并取得了豐碩的研究成果。

但是，其中大多數局部社團發現方法在社團擴張時采取粗暴的擴張方式，以不屬于社團的所有節點為擴張集合，這對于真實的網絡是不必要的，并且降低了算法的效率。

公開號為CN110086670A的發明專利申請公開了一種基于局部鄰居信息的大規模復雜網絡社團發現方法及應用；通過度最大的節點及其鄰居節點對原始節點進行劃分，并基于隸屬度關系對節點進行擴充，最終實現所有節點的劃分。然而該申請在擴張過程中考慮的隸屬度關系僅僅考慮了節點在局部社團中的度和整個抽象網絡中度的關系，未考慮局部社團結構節點之間的聯通關系和節點對于整個社團結構的影響，無法解決大規模網絡稀疏的問題。

發明內容

本發明所要解決的技術問題在于提供一種能夠高效率的合理劃分重疊社團的方法，提高重疊社團劃分結果的精度。

本發明是通過以下技術方案解決上述技術問題的：一種基于局部結構的密度最大化重疊社團發現方法，包括以下步驟：

步驟A：將待劃分社團的網絡抽象成由節點連接成的抽象網絡；

步驟B：根據節點的連接屬性，獲得每個節點的度，以度最大的節點作為種子節點，將種子節點的鄰居節點添加到初始化社團中；

步驟C：對剩余節點重復步驟B，直到抽象網絡中不存在未劃分的節點；

步驟D：將所有社團從大到小排序，依次判斷小社團中的節點能否添加到大社團中，對初始化社團進行擴張；

步驟E：對擴張后的社團判斷是否滿足合并條件，將滿足合并條件的社團進行合并，輸出社團劃分結果。