[發明專利]基于拓撲特性的復雜網絡社團發現方法

有效

• 申請號: 201410037855.1
• 申請日: 2014-01-27
• 公開（公告）號: CN103810260B
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 周紅芳;段文聰;王心怡;何馨依;郭杰;張國榮
• 申請（專利權）人: 西安理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 西安弘理專利事務所61214
• 代理人: 李娜

1.基于拓撲特性的復雜網絡社團發現方法，其特征在于，包括：

步驟1，初始化；將網絡中的每個節點作為一個獨立的社團，如果網絡中有n個節點，那么就有n個初始化社團，各個節點的關鍵性為0，歸屬度取決于邊連接強度；

所述歸屬度，是節點劃分的判斷標準，即節點與各個社團之間的關系；歸屬度計算公式如下：

$A(i,g)=\underset{j\∈g}{\mathrm{\Σ}}\left(\right(1+s_{ij})\·(1+\frac{c_j}{r}\left)\right)---\left(1\right)$

其中A(i,g)就代表節點i與社團g的歸屬度，s_ij代表節點i與社團g中節點j的邊連接強度，c_j代表節點j在社團g中的關鍵性，r為系數；

步驟2，計算邊連接強度；計算所有相連節點之間的邊連接強度，也就是計算有邊相連的兩個節點所構成的三角形的個數；

步驟3，迭代；依順序對各節點進行以下操作：首先，將一個節點從其所在社團刪除，計算該節點與各個社團的歸屬度，將節點劃分到歸屬度最大的社團；

步驟3中，節點被劃分到新的社團之后，與其相連的節點的中心程度可能會發生改變，需要重新計算它們的關鍵性，即能構成的三角形的個數；之后，對下一個節點進行同樣的操作；當遍歷完所有的節點，一次迭代結束；經過多次迭代，各節點的歸屬將不再發生變化，算法終止。

2.如權利要求1所述的基于拓撲特性的復雜網絡社團發現方法，其特征在于，所述邊連接強度，是用來衡量兩個相連節點之間的相似度，用s_ij來表示節點i與節點j之間的邊連接強度，s_ij等于在網路中包含節點i與節點j所組成的三角形的個數。

3.如權利要求1所述的基于拓撲特性的復雜網絡社團發現方法，其特征在于，所述關鍵性，是衡量節點在其所屬社團中的重要程度，用c_j來表示節點j在其所屬社團中的關鍵性，c_j等于在節點j所屬社團中包含節點j的三角形的個數。