[發明專利]一種基于標簽擴散的時序平滑社團劃分方法及裝置

在審

• 申請號: 201811277145.0
• 申請日: 2018-10-30
• 公開（公告）號: CN109389179A
• 公開（公告）日: 2019-02-26
• 發明（設計）人: 胡學鋼;何偉;楊恒宇
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙) 34124
• 代理人: 丁瑞瑞

1.一種基于標簽擴散的時序平滑社團劃分方法，其特征在于，所述方法包括：

1)、獲取待劃分網絡中的各個節點在當前時刻的前一時刻的標簽值，其中，所述待劃分網絡是由所述節點連接而成的抽象網絡；

2)、獲取當前次更新中標簽值發生變化的節點數量，并根據所述節點數量更新標簽值發生變化的節點數量的振蕩次數，判斷所述振蕩次數是否大于預設閾值；

3)、若否，針對每一個節點，利用所述節點的歸一化邊密度以及所述節點的歸一化隸屬度，獲取所述節點的第一偏好權值；將所述第一偏好值作為所述節點的當前偏好值；

4)、若是，針對每一個節點，利用所述節點的歸一化隸屬度以及所述節點的度數中心度，獲取所述節點的第二偏好權值；將所述第二偏好值作為所述節點的當前偏好值；

5)、根據所述當前偏好權值、所述節點的鄰居節點屬于前一時刻的待劃分網絡或者所述節點不屬于前一時刻的待劃分網絡，更新當前時刻所述節點的標簽值；返回執行所述步驟2)，直至所述待劃分網絡中的各個節點都被劃分到由標簽值相同的節點組成的社團中。

2.根據權利要求1所述的一種基于標簽擴散的時序平滑社團劃分方法，其特征在于，所述步驟1)，包括：

獲取待劃分網絡中的各個節點在當前時刻的前一時刻的標簽值以及，獲取所述節點的標簽值的更新順序，且，所述獲取所述節點的標簽值的更新順序，包括：

利用公式，計算所述節點的Burt約束系數，其中，

Constraint(i)為節點i的Burt約束系數；i為所述節點的序號；∑為求和函數；j為節點i的鄰居節點的序號；V_i為所述節點以及所述節點的鄰居節點的集合；q為集合V_i中第q個節點；p_iq為節點i與節點q之間的相對關聯強度，且a_iq為待劃分網絡的鄰接矩陣中第i行第q列的元素；a_qi為待劃分網絡的鄰接矩陣中第q行第i列的元素；a_ik為待劃分網絡的鄰接矩陣中第i行第k列的元素；a_ki為待劃分網絡的鄰接矩陣中第k行第i列的元素；k為集合V_i中的第k個節點；p_qj為節點q與節點j之間的相對關聯強度；

將所述節點的Burt約束系數從大到小的順序作為所述節點的標簽值更新順序。

3.根據權利要求1所述的一種基于標簽擴散的時序平滑社團劃分方法，其特征在于，所述獲取所述節點的第一偏好權值，包括：

利用公式，計算歸一化社團密度，其中，

Density_norm(c)為社團c的歸一化邊密度；C為當前所有社團的集合；Density(c)為社團c對應的社團密度，且E(c)為社團c中的邊的集合；V(c)為社團c中的節點的集合；||為勢函數；min_x∈C()為最小值求值函數；max_x∈C()為最大值求值函數；x為社團集合C中除社團c以外的其他社團；

利用公式，獲取節點i的歸一化隸屬度，其中，

Loyalty_norm(i)為節點i的歸一化隸屬度；Loyalty(i)為節點i的隸屬度，且D_in(i)為節點i的社團內度數；D(i)為節點i的度數；V為待劃分網絡中所有節點的集合；

利用公式，w_ij＝1+Density_norm(c)-Loyalty_norm(i)，獲取所述節點的第一偏好權值，其中，

w_ij為節點i相對于節點j的第一偏好權值。