[發明專利]一種Fedora系統組件復雜網絡中的重疊社區檢測方法

有效

• 申請號: 201710303329.9
• 申請日: 2017-05-03
• 公開（公告）號: CN107240028B
• 公開（公告）日: 2020-09-15
• 發明（設計）人: 程久軍;吳瀟;黃震華;張長柱;秦鵬宇;陳向榮;楊陽;廖競學;邵劍雨;尚錚;米浩
• 申請（專利權）人: 同濟大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06F17/10
• 代理公司: 上海科律專利代理事務所(特殊普通合伙) 31290
• 代理人: 葉鳳

針對目前關于復雜網絡演化中重疊社區發現的研究并沒有考慮節點個體的動態演化、不均勻活躍度分布和多尺度性(Multi‐scaling)，使得重疊社區不能同時有較高的NMI(NMI，Normalized Mutual Information)和F‐score值等問題，本發明公開一種復雜網絡中基于節點活躍度的非對稱社團擴展的重疊社區發現及預測方法。首先，定義節點活躍度，將節點活躍度用于重疊社區擴展的目標函數；然后，社區擴展及使用最大社團作為擴展種子；最后，給出基于節點活躍度的非對稱社團擴展算法。本發明從根本上提升了復雜網絡中的重疊社區的檢測準確率，并且對未來重疊社區具有較好的預測能力。

技術領域

本發明涉及復雜網絡領域，具體涉及復雜網絡中基于節點活躍度的非對稱社團擴展的重疊社區發現及預測方法。

背景技術

2005年，Palla等人提出允許節點同時屬于多個社區的定義，即允許社區重疊。他們將傳統社區發現問題推廣為重疊社區發現。為了得到重疊社區，Palla等人基于社區內節點與社區內其他多數節點有連接而不必與所有節點連接的性質，提出了CPM算法(CPM，Clique Percolation Method)。在CPM算法中，首先搜索一種稱為k-clique的結構(至少包含k個節點的完全子圖且不是任何其他完全子圖的子集)，然后尋找相鄰的k-clique(共享k-1個節點)，通過將相鄰的k-clique合并得到重疊社區。CPM主要解決無向、無權的網絡中的重疊社區發現問題，而其擴展方法CPMd和CPMw則分別解決有向的和帶權網絡中的重疊社區發現問題。然而，CPM的時間復雜度較高且識別準確率較低，對重疊節點的檢測能力較差。另外，由于其時間復雜度高，在分析某些大型網絡時，CPM運行無法停止。

為了改進重疊社區發現方法，有人提出用邊代替節點作為考慮對象，對邊進行層級聚類從而得到重疊社區的方法。例如，在Ahn等人提出的linkcomm算法中，首先為節點k的邊e_ik和邊e_jk定義相似性函數：

其中N_i和N_j表示節點i和j的鄰居節點集合。然后將該相似度函數應用于傳統的AHC算法，即不斷地選擇一對相似度最高、以邊作為元素的集合進行合并，從而得到以邊作為葉節點的樹圖。在該樹圖中，通過切除某些分支從而得到重疊社區。linkcomm算法的時間復雜為O(n·k_max)，其中n代表節點數，k_max表示節點的最大度。然而，隨機性強的網絡存在大量介于社區之間的邊，此時相似性函數不能很好匹配社區定義，降低了linkcomm算法的準確率。

從某局部區域開始，采用一定的優化策略進行擴展得到重疊社區是一種有效的方法。Baumes等人提出一種分兩步的策略，即首先使用Rank Removal算法按照一定原則對節點排序，再逐步刪除排序靠前的節點，直到網絡成為多個較小的、不相交的簇核(ClusterCore)。然后以它們為起點，不斷添加或刪除節點來優化一個局部密度函數，直到函數取值不再增加，得到重疊社區(Iterative Scan算法)。該局部密度函數滿足重疊社區的定義，即

其中是社區內度(等于社區內的邊數乘以2)，而是社區外度(等于社區內的節點與社區外節點的連接總數)。f(c)取值越大，表示社區內的節點連接密度越高于社區內外連接的密度。該方法在擴展的過程中允許刪除節點，因而會將連通分量斷開。但是該問題在修改后的算法CIS中已被解決。此外，該函數還存在一個重要缺陷，即如果把網絡看作整體，該局部密度函數取得理論上的最大值1。該值表示發現了最準確的社區，但實際上沒有檢測到任何社區。

Lancichinetti等人也提出通過局部擴展和優化目標函數的方法來發現重疊社區，即LFM方法(LFM，Lancichinetti Fortunato Method)。與Baumes的方法不同，LFM隨機選擇一個未分配至任何社區的節點作為種子，即初始節點集合，且推廣原社區目標函數為：