[發明專利]一種基于網絡剪枝和局部社區擴展的邊社區發現算法

在審

• 申請號: 202011040915.7
• 申請日: 2020-09-28
• 公開（公告）號: CN112165401A
• 公開（公告）日: 2021-01-01
• 發明（設計）人: 王貴參;王紅梅;郭真俊;黨源源;張麗杰;劉致華
• 申請（專利權）人: 長春工業大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/26
• 代理公司: 暫無信息
• 代理人: 暫無信息

一種基于圖剪枝和局部社區擴展的邊社區發現算法是一種重疊社區發現算法。首先，計算圖中的邊吸引力，將圖中邊吸引力低于閾值的邊刪除，得到剪枝后的圖。之后，將剪枝圖轉化為線圖，使用PageRank算法，計算線圖上的節點的得分矩陣，選取一個種子節點，擴展社區，重復該過程，直至網絡中無候選種子節點為止。合并重復線圖上的節點社區，并將其轉換回原圖上節點的重疊社區結構。本發明為重疊社區發現提供了一種基于圖剪枝和局部社區擴展的邊社區發現算法，與現有方法比較，本發明具有如下主要優點：（1）提出邊吸引力概念，利用邊吸引力進行圖剪枝，降低線圖節點的規模。（2）使用局部社區發現算法對線圖上節點進行社區發現，能達到更優的評估度量值。

技術領域

本發明屬于復雜網絡領域，尤其涉及一種基于網絡剪枝和局部社區擴展的邊社區發現算法。

背景技術

重疊社區發現算法是復雜網絡領域的一類重要算法，對于理解復雜網絡有著重要幫助。在過去的十年中，學者們提出了多種重疊社區發現方法，如邊社區發現方法、局部社區發現方法等。

目前，典型的邊社區發現方法框架是通過計算邊之間的相似度來確定邊之間的相似程度，結合無監督學習方法來將相似的邊合并為一個社區。在確定邊的相似程度時，會計算邊的相似度，或者通過線圖模型，將圖中的邊轉換到線圖中的節點，計算線圖節點之間的關系。但是，由于圖中邊的規模通常要比節點規模大，因此，計算邊的相似度時開銷很大，同時，有些情形下，邊是冗余的，會對邊的相似度計算造成干擾。

典型的局部社區發現方法框架是尋找圖中的種子節點，之后，從種子節點出發，擴展局部社區，最后，將冗余社區進行合并。局部社區發現方法尋找社區結構的效率較高，但是，在邊社區發現中應用較少。

發明內容

針對上述兩個問題，本發明旨在邊社區發現算法基礎上，結合局部社區發現算法的優點，提供一種能夠降低圖中邊的規模的圖剪枝策略，并且能夠結合局部社區發現算法，降低在線圖上節點社區發現的時間復雜度。

本發明提供了一種基于網絡剪枝和局部社區擴展的邊社區發現算法，所述方法步驟如下：

步驟1：使用圖剪枝策略對圖進行剪枝，并將圖轉換為線圖

步驟2：在線圖上，使用PageRank算法對節點進行排序，并得到節點的得分矩陣

步驟3：在線圖上，尋找候選種子節點，并從種子節點出發，擴展局部社區，重復此過程，直至線圖中沒有候選種子節點為止

步驟4：合并冗余線圖節點社區，并將線圖節點社區轉換為圖的重疊節點社區。

附圖說明

圖1為本發明流程圖；

圖2為空手道俱樂部網絡不同閾值的NMI值圖；

圖3，圖4分別為空手道俱樂部網絡上的鄰接矩陣、距離矩陣圖；

圖5為空手道俱樂部網絡的三種算法的NMI值圖。

具體實施方式

以下實施例用于說明本發明，但不用來限制本發明的范圍。現通過附圖和實施例對本發明作進一步的詳細描述，本發明實施例的前提是已獲得了復雜網絡數據集，圖1為本發明實施例提供結合網絡剪枝和局部社區擴展的鏈路社區發現方法流程示意圖，如圖1所示，本實施例主要包含以下步驟：

步驟1：使用圖剪枝策略對圖進行剪枝，并將圖轉換為線圖

計算圖中的所有邊的吸引力值，吸引力公式定義如下：