[發明專利]標簽傳播方法和裝置

有效

• 申請號: 201611263101.3
• 申請日: 2016-12-30
• 公開（公告）號: CN106789588B
• 公開（公告）日: 2019-10-22
• 發明（設計）人: 王陽
• 申請（專利權）人: 東軟集團股份有限公司
• 主分類號: H04L12/58
• 分類號: H04L12/58;G06Q50/00
• 代理公司: 北京英創嘉友知識產權代理事務所(普通合伙) 11447
• 代理人: 魏嘉熹;南毅寧

本公開實施例涉及數據分析和復雜網絡領域，提供一種標簽傳播方法和裝置，能夠提高標簽傳播迭代結果的穩定性和準確性，該方法包括：計算社交網絡中每個節點的權值；將每個節點的標簽和所述權值傳播給與該節點有邊相連的接收節點；迭代執行根據所述接收節點接收到的各個標簽的數量以及標簽來源節點的權值為所述接收節點賦予新的標簽的步驟，直至預設標簽傳播結束條件滿足為止。

技術領域

本公開實施例涉及數據分析和復雜網絡領域，具體地，涉及一種標簽傳播方法和裝置。

背景技術

標簽傳播算法是在社交網絡分析領域中被廣泛采用的算法，經常被用來自動挖掘社交關系中的“團結構”(即圈子)。

現有的標簽傳播算法主要包括以下步驟：(1)在初始階段，為社交網絡中的每個節點賦予一個獨一無二的標簽L，該標簽L即為節點的初始標簽值，其通常為例如字符串類型的值；(2)然后，通過多輪迭代計算，通過社交關系(即社交網絡中的邊)將標簽向其他鄰居節點傳播。其中，在一輪迭代運算過程中，某個節點將根據與其有邊聯系的其他節點的標簽來決定自己此輪應該賦予哪個標簽，基本原則是：將其鄰居節點的標簽中出現次數最多的那個標簽賦予自己，如果鄰居節點的標簽數目一樣多，無法找出最多個數的標簽，則隨機賦予一個標簽。每個節點都根據這個原則重新確定本輪迭代中本節點應該獲得的新標簽，這樣就完成了一輪標簽賦值運算。(3)當進行了多輪迭代運算后，絕大多數節點的標簽不再發生變化時，這就是最終計算結果。

現有標簽傳播算法的主要缺點是，每次迭代結果不穩定，準確率不高。

發明內容

本公開的發明人發現，現有標簽傳播算法造成迭代結果不穩定的主要因素是更新標簽的原則太簡單，這樣會導致大部分節點都是隨機選取標簽來更新自身的標簽，導致迭代結果準確率不高。

本公開實施例的目的是提供一種標簽傳播方法和裝置，能夠使迭代結果穩定且準確。

為了實現上述目的，本公開實施例提供一種標簽傳播方法，該方法包括：

計算社交網絡中每個節點的權值；

將每個節點的標簽和所述權值傳播給與該節點有邊相連的接收節點；

迭代執行根據所述接收節點接收到的各個標簽的數量以及標簽來源節點的權值為所述接收節點賦予新的標簽的步驟，直至預設標簽傳播結束條件滿足為止。

可選地，所述根據所述接收節點接收到的各個標簽的數量以及標簽來源節點的權值為所述接收節點賦予新的標簽，包括：

在所述接收節點接收到的數量最多的標簽只有一個時，為該接收節點賦予該數量最多的標簽作為新的標簽。

可選地，所述根據所述接收節點接收到的各個標簽的數量以及標簽來源節點的權值為所述接收節點賦予新的標簽，包括：

在所述接收節點接收到的數量最多的標簽有至少兩個時，計算各個所述數量最多的標簽的來源節點的權值之和；

依據所述權值之和為所述接收節點賦予新的標簽。

可選地，所述依據所述權值之和為所述接收節點賦予新的標簽，包括：

在所述權值之和的最大值只有一個時，將該最大權值之和對應的標簽賦予所述接收節點作為新的標簽；

在所述權值之和的最大值有至少兩個時，將該最大權值之和對應的標簽中的其中一個標簽賦予所述接收節點作為新的標簽。

可選地，所述預設標簽傳播結束條件包括以下至少一者：

(1)迭代次數達到預設值；

(2)在單次迭代過程中，預設百分比的節點的標簽沒有發生變化。

本公開實施例還提供一種標簽傳播裝置，該裝置包括：