[發明專利]一種網絡局部社團挖掘方法

在審

• 申請號: 201810141629.6
• 申請日: 2018-02-11
• 公開（公告）號: CN108427724A
• 公開（公告）日: 2018-08-21
• 發明（設計）人: 徐小龍;胡楠
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 姜慧勤

1.一種網絡局部社團挖掘方法，其特征在于，包括如下步驟：

步驟1，對網絡中的所有節點進行編號，且每個節點的編號唯一，并將節點的編號作為自身的id；

步驟2，設定網絡中的部分節點為種子節點，并獲取各種子節點對應的編號；

步驟3，針對網絡中每個節點，根據節點的度數和包含該節點的三角環數，計算每個節點的關系密度值；

步驟4，基于高斯模糊算法的思想，對于網絡中的每個節點，計算其自身的關系密度值和鄰居節點的關系密度值的加權平均值，將加權平均的結果作為該節點的社團中心性值；

步驟5，在網絡中，通過有指導的隨機游走，從各種子節點出發尋找附近S步數內社團中心性值最大的節點，即各種子節點所在的局部社團的中心節點，S為可調參數；

步驟6，從各局部社團的中心節點出發，挖掘出與種子節點在同一局部社團的其他節點，并輸出各種子節點所在的局部社團中的所有節點。

2.根據權利要求1所述網絡局部社團挖掘方法，其特征在于，步驟3所述關系密度值的計算公式為：

其中，R表示節點的關系密度值，t表示包含該節點的三角環數，d表示節點的度數。

3.根據權利要求1所述網絡局部社團挖掘方法，其特征在于，步驟4所述社團中心性值的計算公式為：

其中，H表示節點的社團中心性值，R表示節點的關系密度值，R_m表示鄰居節點的關系密度值，M表示鄰居節點的數量，x表示積分變量，σ表示參數。

4.根據權利要求1所述網絡局部社團挖掘方法，其特征在于，所述步驟5的具體過程為：

5-1，初始化種子節點，為每個種子節點添加激活標記，設置當前游走步數S′＝0；

5-2，若S′≤S轉5-3，否則轉5-5，S為可調參數；

5-3，從有激活標記的節點出發，尋找其對應的鄰居節點中社團中心性值大于自身且社團中心性值最大的節點，如果存在滿足條件的鄰居節點則轉5-4，否則轉5-5；

5-4，將激活標記轉移到滿足條件的鄰居節點，S′＝S′+1，轉5-2；

5-5，游走結束，輸出每個種子節點所在的局部社團的中心節點。

5.根據權利要求1所述網絡局部社團挖掘方法，其特征在于，所述步驟6的具體過程為：

6-1，將各局部社團的中心節點作為初始社團，并初始化；

6-2，將每個中心節點的鄰居節點中，與中心節點處于同一個三角環中的節點添加進中心節點所在的局部社團；

6-3，將每個局部社團中的所有節點壓縮成一個節點，并保留對外連邊；

6-4，若某節點與6-3得到的節點處于同一個三角環內且6-3得到的節點所對應的局部社團對某節點的吸引力大于θ時，將某節點添加到該局部社團，θ為設定的閾值參數，若沒有滿足條件的節點則轉6-6；

6-5，計算局部社團的內聚系數，若內聚系數增大，則轉6-3，否則轉6-6；

6-6，挖掘結束，并輸出納入局部社團的所有節點。

6.根據權利要求5所述網絡局部社團挖掘方法，其特征在于，所述吸引力的計算公式為：

其中，α表示局部社團對節點k的吸引力，n表示已添加到局部社團的節點數量，N表示網絡中所有節點的數量，當節點k與節點j之間有連邊，則σ(k,j)＝1，否則σ(k,j)＝0；當節點k與節點i之間有連邊，則σ(k,i)＝1，否則σ(k,i)＝0。

7.根據權利要求5所述網絡局部社團挖掘方法，其特征在于，所述內聚系數的計算公式為：

其中，w表示局部社團的內聚系數，w_in表示已添加到局部社團的節點之間的連邊數量，w_out表示已添加到局部社團的節點與網絡中其他節點之間的連邊數量。