[發明專利]自適應的社區發現方法

在審

• 申請號: 201710380516.7
• 申請日: 2017-05-25
• 公開（公告）號: CN107301423A
• 公開（公告）日: 2017-10-27
• 發明（設計）人: 汪清;趙建軍
• 申請（專利權）人: 天津大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/00
• 代理公司: 天津市北洋有限責任專利代理事務所12201
• 代理人: 劉國威

1.一種自適應的社區發現方法，其特征是，步驟如下：

(1)首先遍歷網絡中的每一個節點，把每一個節點作為源節點，對其原始信息量進行擴散傳遞，當一個節點作為源節點時，其信息傳遞與其它節點信息無關；

(2)利用信息傳遞所獲得信息量代替峰值聚類中的密度；

(3)利用信息量矩陣獲得節點之間的距離矩陣；

(4)根據信息量與距離獲得核心節點，并且為每一個核心節點分配一個社區號；

(5)利用核心節點擴散完成社區劃分。

2.如權利要求1所述的自適應的社區發現方法，其特征是，社交網絡可表示為圖G＝(V,E)，其中V＝{v₁,v₂,…,v_n}表示網絡中節點集，E＝{e₁,e₂,…,e_m}表示網絡中邊集，n表示網絡中節點的個數，m表示網絡中邊的條數，定義網絡信息量矩陣S_n×n，其中S_ii表示節點i的初始信息量，S_ij表示源節點i傳遞到節點j的信息量；

節點間信息傳遞遵循如下規則：

信息傳遞過程中，節點對于信任度不同的鄰居節點所傳信息量不同，信任度越大，所傳遞的信息量越大；

基于此定義源節點i與鄰居節點j的信任度，由公式(3)至公式(6)獲得信任度函數：

C(i,j)＝|N_i∩N_j| (3)

α(i,j)=|C(i,j)|+1|Ni|---(4)]]>

β(i,j)=2×|E(C(i,j))|(|C(i,j)|)(|C(i,j)|-1),|C(i,j)|≥20,|C(i,j)|<2---(5)]]>

T(i,j)＝α(i,j)×(β(i,j)+1)(6)

其中,|C(i,j)|表示節點i與節點j的公共鄰居個數，N_i表示與節點i相鄰的鄰居節點，N_j表示與節點j相鄰的鄰居節點，|E(C(i,j))|表示節點i與節點j公共鄰居間的連邊總數，公式(4)中，分母為源節點的鄰居個數，使得T(i,j)≠T(j,i)，信息量的傳遞不對稱，度數大的節點獲得的信息量大，公式(5)表示兩節點公共鄰居間連邊總數與其最大可能的連邊總數的比值，由于β(i,j)是建立在α(i,j)的基礎上，因此總的信任度定義為公式(6)；

信息傳遞步驟如下：

1)初始化所有節點的信息量為1，即信息量矩陣S_n×n為單位矩陣；

2)遍歷網絡中的節點，將每個節點依次作為源節點，對其初始信息量1進行擴散傳遞，此時并不考慮其余節點的信息量；

3)源節點在擴散傳遞信息量時，采用廣度優先算法BFS，以i為源節點，其傳遞到鄰居節點j的信息量S_ij＝1×T(i,j)，鄰居節點j要把源節點i傳遞的信息量S_ij繼續擴散到j的鄰居節點k，k節點獲得信息量S_ik＝S_ij×T(j,k)＝1×T(i,j)×T(j,k)，直到網絡中所有節點都含有節點i的信息量時，節點i的信息傳遞完成；

信息傳遞結束后，S_ii＝1表示節點i的原始信息量，S_ij,j＝1,2,…,n；j≠i表示源節點i傳遞到網絡上其它節點的信息量，表示節點j的信息總量。