[發明專利]一種非重疊網絡和重疊網絡中社團結構檢測方法

在審

• 申請號: 201910334636.2
• 申請日: 2019-04-24
• 公開（公告）號: CN110070177A
• 公開（公告）日: 2019-07-30
• 發明（設計）人: 許小可;肖婧;胡越
• 申請（專利權）人: 大連民族大學
• 主分類號: G06N3/04
• 分類號: G06N3/04;G06N3/00
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 蓋小靜

本發明公開了一種非重疊網絡和重疊網絡中社團結構檢測方法，在模糊模塊度函數的引導下，在約束條件對應的可行隸屬度分布組合空間內進行方向性搜索，收斂至使模糊模塊度函數達到最優的隸屬度分布，由最優的隸屬度分布，得到真正的社團劃分，從而確定社團結構。本方法可獲得真正的模糊社團劃分，并根據隸屬度分布確定社團結構，所獲得的最終隸屬度分布能夠體現重疊節點的多樣化拓撲特性差異，克服了隸屬度計算過程中由于計算指標單一帶來的不精確性。

技術領域

本發明涉及一種社團結構檢測方法，具體說是一種非重疊網絡和重疊網絡中社團結構檢測方法。

背景技術

社團結構是復雜網絡是重要特性之一，發掘復雜網絡中的社團結構對揭示網絡功能具有重要的意義。網絡社團檢測能夠挖掘出復雜網絡中有現實意義的社團結構，但在實際中，網絡的形式多種多樣，內在聯系形式也大都不同，這就導致了內部社團結構也呈現出多樣性。因此，針對這些形式多樣的網絡，為了能夠準確有效的分析其中的社團結構，誕生了許多社團檢測算法。

相比較于社團檢測，非重疊的社團檢測算法最先被提出，并且目前在python的標準庫中已有多種社團檢測算法可以被直接調用。例如基于多分辨率版本的模塊度的MultiLevel算法、基于貪婪算法的FastGreedy算法、基于隨機游走的WalkTrap算法、基于邊介數的GN算法、基于節點和子圖關系的Kclique算法、基于動力學隨機游走的InfoMap算法、基于標簽節點傳播的標簽傳播算法(LP)和基于模塊矩陣主導特征向量的Eigenvector算法。然而，隨著復雜網絡規模的增加，社團劃分方式變得更加復雜，這些經典的社團檢測算法已經不能滿足需求。

在社團檢測中，存在兩種類型的重疊：離散重疊和模糊重疊。離散重疊中每個節點對于其所屬的社團有相同的隸屬度，而模糊重疊對劃分有更加精確的要求，即節點對所屬社團的隸屬度不盡相同。典型的離散社團檢測算法包括：派系過濾、鏈接聚類、局部擴展、模塊度優化、多目標優化和標簽傳播等。

2011年，Gregory針對社交網絡的社團檢測首次提出了“模糊重疊劃分”的概念。目前，國內外已經有多種模糊社團檢測算法被提出，包括擴展標簽傳播、非負矩陣分解及模糊模塊度優化等。擴展的標簽傳播算法典型代表算法包括COPRA算法、SLPA算法及LPPB算法等，其中，COPRA是Gregory于2010年提出的首個基于標簽傳播的模糊社團檢測算法。基于非負矩陣分解是機器學習中的常用算法，近年來被用于社團檢測求解中，典型代表算法包括Zhao等2010年提出的對稱NMF算法s-NMF，Psorakis等2011年提出的貝葉斯NMF算法等。模糊聚類的典型代表性算法包括2013年Wang等提出基于FCM的模糊聚類算法。

在社團檢測中，離散重疊只關心節點是否屬于某個社團，對社團劃分沒有更精確的要求。然而目前，絕大多數的社團檢測算法僅限于離散社團檢測，這類算法將節點對各個社團的隸屬度看作是相同的，然而很多真實社團結構中節點隸屬度是非一致的。

現如今國內外已有的多種模糊社團檢測算法中，包括擴展標簽傳播、非負矩陣分解及模糊模塊度優化等，基于擴展標簽傳播的模糊社團檢測算法缺乏有效的設置隸屬度閾值的方法。基于非負矩陣分解算法計算復雜度高，不適用于大規模網絡。以FCM為代表的模糊聚類算法檢測所得社團結構的模塊度較低。模糊模塊度優化算法在全局尋優方面能力不足并且易陷入局部最優。

發明內容

針對現有技術存在上述問題，本申請提供了一種非重疊網絡和重疊網絡中社團結構檢測方法，在模糊模塊度函數的引導下，在約束條件對應的可行隸屬度分布組合空間內進行方向性搜索，收斂至使模糊模塊度函數達到最優的隸屬度分布，由最優的隸屬度分布，得到真正的社團劃分，從而確定社團結構。

為實現上述目的，本申請的技術方案為：一種非重疊網絡和重疊網絡中社團結構檢測方法，具體步驟如下：

一、非重疊網絡中社團結構檢測方式為：

Step1對種群個體進行編碼并構建初始種群；