[發明專利]一種基于改進的密度峰值聚類的社交網絡社區發現方法

有效

• 申請號: 201810475496.6
• 申請日: 2018-05-17
• 公開（公告）號: CN108647739B
• 公開（公告）日: 2020-09-18
• 發明（設計）人: 李玉華;李瑞軒;袁清亮;辜希武;徐明麗;梁天安
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06K9/62;G06Q50/00
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智;曹葆青

1.一種基于改進的密度峰值聚類的社交網絡社區發現方法，其特征在于，包括以下步驟：

S1.收集社交網絡中所有用戶的簽到數據，并初始化社區集合C為空集；

S2.基于所有用戶的簽到數據，構建用戶距離矩陣D_m×m；

S3.基于用戶距離矩陣D_m×m計算截斷距離d_c；

S4.基于用戶距離矩陣D_m×m和截斷距離d_c，為每個用戶計算局部密度ρ和相對距離δ，標準化處理得到ρ′和δ＇，定義γ＝ρ′×δ′；

S5.基于γ值判斷每個用戶是否為社區中心，若是，則生成以該用戶為中心的社區，并將該社區插入到社區集合C；否則，將該用戶分配到局部密度比它大且離它最近的用戶所在社區；

S6.輸出社區集合C，社區集合C中所有社區即為發現的社區；

步驟S1包括：用U＝(u₁,u₂,...,u_m)來表示用戶集合，其中，m表示用戶數；用A_i＝(u_i1,u_i2,...,u_ia)表示用戶u_i的屬性集合，其中，a為用戶u_i的屬性數，u_ia表示用戶u_i的第a個屬性；用V＝(v₁,v₂,...,v_n)表示簽到地點集合，其中，n表示簽到地點數；用T＝(t₁,t₂....,t_l)表示時間窗口集合，其中，l表示時間窗口數；

步驟S2中矩陣D_m×m中矩陣元素d_ij表示用戶u_i與u_j之間的距離，其計算公式如下：

式中，d_atr(u_i,u_j)表示用戶u_i與u_j屬性之間的歐式距離，u_ik表示用戶u_i的第k個屬性；d_checkin(u_i,u_j)表示用戶u_i與u_j簽到數據之間的歐氏距離，表示用戶u_i在t_y時間窗口內，在地點v_x上的簽到次數；

在步驟S5和S6之間，還存在以下步驟：

(1)將步驟S5得到的社區集合記為C，C＝{c₁,c₂,...c_K}，K表示社區個數；

(2)C^*表示合并后的社區集合，初始化為空集，并選定一個合并閾值τ；

(3)生成一幅無向圖G(V,E)，其中，V是無向圖G中節點的集合，E是無向圖G中節點之間邊的集合，節點集合V中的每個節點對應社區集合C中的一個社區，即V＝{c₁,c₂,...c_K}，節點之間邊的集合E初始化為空集，即節點之間不存在邊；

(4)對社區集合C中任意兩個社區c_i和c_j，1≤i≤K，1≤j≤K，計算合并因子ω(c_i,c_j)和ω(c_j,c_i)，若合并因子ω(c_i,c_j)＞τ且ω(c_j,c_i)＞τ，則在無向圖G中的節點c_i和節點c_j之間標記一條邊(c_i,c_j)，表明社區c_i和c_j需要進行合并，并將這條邊插入到邊的集合E中；合并因子的計算公式如下：

其中，|c_i|和|c_j|分別表示社區c_i和c_j中的用戶的個數，x表示用戶，Ψ為二值函數，計算公式如下：

其中，y表示社區c_i的用戶，d_xy表示用戶x與用戶y之間的距離；

(5)在無向圖G(V,E)中找到所有的極大連通子圖，而每個極大連通子圖都對應一個合并后的社區，將該合并后的社區插入到合并后的社區集合C^*中；

(6)用合并后的社區集合C^*替換原社區集合C。