[發明專利]動態社交網絡中基于聯盟形成博弈的社區檢測方法

有效

• 申請號: 201710878090.8
• 申請日: 2017-09-26
• 公開（公告）號: CN107659467B
• 公開（公告）日: 2020-03-17
• 發明（設計）人: 周麗華;楊培忠;王麗珍;陳紅梅;肖清
• 申請（專利權）人: 云南大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;G06Q50/00
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

1.一種動態社交網絡中基于聯盟形成博弈的社區檢測方法，其特征在于，具體按照以下步驟進行：

步驟1，采用基于模塊度的社區檢測方法對初始社區結構進行檢測，得到初始社區結構Γ；

步驟2，將相鄰網絡快照上網絡社區結構的演變分解為增加節點、增加連邊、刪除節點或刪除連邊；

步驟3，計算t時刻的社區結構增加節點、增加連邊、刪除節點或刪除連邊后，t+1時刻所有可能形成的社區結構的收益，確定收益最大的社區結構為實際演變后t+1時刻的社區結構，如此對初始社區結構Γ進行動態局部調整，得到實際演變后的社區結構Γ'；

社區結構Γ的收益v(Γ)的計算方法：社交網絡表示為一個無向圖G＝(N，E),其中：N＝{v₁,v₂,...,v_n}為節點的集合，表示社交網絡中的用戶，n為整個社交網絡中用戶的數量；E＝{e₁,e₂,...,e_m}為連邊的集合，表示社交網絡中用戶之間的聯系，m為邊的數量；A＝(a_ij)_n×n，i,j∈N是社交網絡的鄰接矩陣，如果用戶i和用戶j之間存在聯系，則a_ij＝1，否則，a_ij＝0；x∈N，d(x)表示節點x的度數；Γ＝{S₁,S₂,...,S_k}表示社交網絡中的社區結構，k表示社區個數，其中，S_i表示一個社區，e(S)表示社區S內部的所有用戶之間的邊的數量，d(S)表示社區S中的所有用戶的度數之和；社區S的收益v(S)的計算公式見式(1)，社區結構Γ的收益v(Γ)的計算公式見式(2)，

其中，α∈[0,1]，β∈(0,1]；

所述步驟2中，當相鄰網絡快照上網絡社區結構的演變為增加節點時，假設增加的節點為節點p：

(i)如果節點p與其他節點沒有連邊連接，此時節點p自己形成一個社區，實際演變后的社區結構Γ′＝Γ+{{p}}；

(ii)如果節點p與一個或多個社區中的節點有連邊，比如社區S_j中的節點與節點p有連邊連接，如果將節點p加入社區S_j能增加社區S_j的收益v(S_j)，則將節點p加入到社區S_j，實際演變后的社區結構Γ′＝Γ-{S_j}+{S_j+{p}}；如果節點p分別加入多個社區均能使被加入社區的收益增加，則節點p被加入到多個社區中，同時成為多個社區的成員；

(iii)如果節點p與社區S_i、社區S_j內的節點聯系均很緊密，即節點p的加入使得兩個社區有合并為一個社區的趨勢，并且合并后的社區的收益分別大于原來兩個社區的單獨收益，則將社區S_i和社區S_j合并為一個社區，實際演變后的社區結構Γ′＝Γ-{S_i}-{S_j}+{S_i+S_j}；

所述步驟2中，當相鄰網絡快照上網絡社區結構的演變為增加連邊時，假設增加的連邊為l＝(x,y)：

(i)如果l＝(x,y)是社區S_i內部的連邊，其中x,y∈S_i，若加入l＝(x,y)后，社區S_i邊界的節點z離開社區S_i后，使得社區S_i的收益v(S_i)增大，則節點z從社區S_i離開；若節點z加入到與節點z有連邊連接的社區S_k中，k≠i，能夠增大社區S_k的收益，則節點z加入到社區S_k中，實際演變后的社區結構Γ′＝Γ-{S_i}-{S_k}+{S_k+{z}}+{S_i-{z}}；

(ii)如果l＝(x,y)是社區間的連邊，其中x∈S_i,y∈S_j,S_i≠S_j，加入l＝(x,y)之后，如果社區S_i和社區S_j合并得到的新社區的收益大于社區S_i、S_j的單獨收益，則將社區S_i和社區S_j合并，實際演變后的社區結構Γ′＝Γ-{S_i}-{S_j}+{S_i+S_j}；如果社區S_i和社區S_j不能合并，分別對兩個社區的邊界節點重新確定社區歸屬：假設節點x為社區S_i的邊界節點，若則節點x離開社區S_i，其中e(x,S_i)表示節點x與社區S_i內部節點之間的連邊數量；若節點x加入到與節點x有連邊連接的社區S_k中，k≠i，能夠增大社區S_k的收益，則將節點x加入到社區S_k中，實際演變后的社區結構Γ′＝Γ-{S_i}-{S_k}+{S_k+{x}}+{S_i-{x}}；確定社區S_i和社區S_j的其余邊界節點社區歸屬的方法與確定節點x社區歸屬的方法相同。