[發明專利]一種基于多標簽傳播的社交網絡重疊社區發現方法及裝置

有效

• 申請號: 202011350850.6
• 申請日: 2020-11-26
• 公開（公告）號: CN112464107B
• 公開（公告）日: 2023-03-31
• 發明（設計）人: 范時平;薛思豪
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 重慶輝騰律師事務所 50215
• 代理人: 王海軍

1.一種基于多標簽傳播的社交網絡重疊社區發現方法，其特征在于，所述方法包括以下步驟：

采集社交網絡數據，構造出以社交網絡用戶為節點，用戶關系為邊的社交網絡圖；

將用戶節點的相似度映射到邊的權重，并計算出各個節點的相似度；

基于各個節點的相似度，構建出所述社交網絡圖所對應的加權網絡；

遍歷加權網絡中的每個節點的標簽，當源節點傳播到目標節點時，如果目標節點具有與源節點相同的標簽，那么該標簽的權重采用第一更新公式更新，否則采用第二更新公式更新；

第一更新公式表示為：

labelDic(v_j).label←labelDic(v_j)+w_ij×labelWeight×(y_i+1)；

第二更新公式表示為：

labelDic(v_j).label←w_ij×labelWeight×(y_i+1)

其中，labelDic(v_j).label表示在標簽字典中存儲的節點v_j的標簽權重；w_ij表示節點v_i和節點v_j邊權值，通過節點的相似度公式計算而得；labelWeight表示標簽權重；y_i表示節點v_i的標準標簽數，即節點v_i的標簽數x減去節點標簽最小的數Min比上節點標簽最大數Max減去節點標簽最小的數Min，表示為y_i是一個(0，1)標準化后的數；

去除傳播更新后標簽權重小于預設閾值的標簽，如果節點標簽數小于或等于k，就將全部標簽作為該節點的新標簽，如果節點標簽數大于k，則取每個節點的前k個標簽作為該節點的新標簽；

對每個標簽的節點數進行計數，選擇節點數最多的k個標簽，按照節點數依次遞減的順序，分別將具有該標簽的用戶劃分到一個區域中，從而依次劃分出k個區域最終的重疊社區。

2.根據權利要求1所述的一種基于多標簽傳播的社交網絡重疊社區發現方法，其特征在于，各個節點的相似度的計算公式包括：

其中，Similarity(v_i,v_j)表示節點v_i和節點v_j的相似度；s為節點標簽的個數，I(T_ik+T_jk)表示指標函數，T_ik表示節點v_i的第k個標簽屬性值，T_jk表示節點v_j的第k個標簽屬性值；當T_ik+T_jk等于2時I(T_ik+T_jk)為1，其他為0。

3.根據權利要求1所述的一種基于多標簽傳播的社交網絡重疊社區發現方法，其特征在于，在遍歷加權網絡中的每個節點的標簽后，該標簽權重按照α線性遞減。

4.根據權利要求1所述的一種基于多標簽傳播的社交網絡重疊社區發現方法，其特征在于，在遍歷加權網絡中的每個節點的標簽后，該標簽權重按照半衰期函數遞減。

5.一種基于多標簽傳播的社交網絡重疊社區發現裝置，其用于實現如權利要求1～4任一所述的一種基于多標簽傳播的社交網絡重疊社區發現方法，其特征在于，所述裝置包括：

采集模塊，獲取社交網絡數據，包括社交用戶和社交用戶之間的關系；

社交網絡模塊，用于構造出以社交網絡用戶為節點，用戶關系為邊的社交網絡圖；

相似度計算模塊，用于計算出各個節點之間的相似度；

加權網絡模塊，用于根據各個節點之間的相似度，構建出所述社交網絡圖所對應的加權網絡；

傳播模塊，用于遍歷加權網絡中每個節點的標簽，并采用第一更新公式或者第二更新公式更新標簽權重；

確定模塊，用于根據更新后的標簽權重，選擇出節點的新標簽；

劃分模塊，對每個標簽的節點數進行計數，選擇節點數最多的k個標簽作為最終的重疊社區。