[發明專利]基于社交網絡節點雙標簽傳播算法的社區結構劃分方法

在審

• 申請號: 201911293324.8
• 申請日: 2019-12-16
• 公開（公告）號: CN110956553A
• 公開（公告）日: 2020-04-03
• 發明（設計）人: 鄭文鋒;楊波;尹超;劉珊;曾慶川
• 申請（專利權）人: 電子科技大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06F16/901
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平

本發明公開了一種基于社交網絡節點雙標簽傳播算法的社區結構劃分方法，先構造社交網絡圖，并為社交網絡圖中的節點分配標簽及初始隸屬度值，再利用K?shell算法計算各個節點的權值，最后通過迭代更新方式實現社交網絡節點的雙標簽傳播；這樣通過增加節點標簽數量并設置隸屬值的方式，充分考慮了社交網絡節點的社交復雜性，能夠提高迭代結果的穩定性和準確性，從而使社區結構劃分更加精確。

技術領域

本發明屬于社交網絡技術領域，更為具體地講，涉及一種基于社交網絡節點雙標簽傳播算法的社區結構劃分方法。

背景技術

標簽傳播算法是在社交網絡分析領域中被廣泛采用的算法，經常被用來自動挖掘社交關系中的社區結構。通過挖掘網絡中的社區結構，能夠發現網絡中隱含的組織結構信息、社會功能以及社區成員之間隱含的有趣屬性，如共同愛好等。通過研究社會網絡中社區之間、個體之間以及個體與社區之間的關系，可以挖掘出大量有價值的信息，可應用于許多領域。

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

現有技術中，已授權專利“201611263101.3”公開了一種標簽傳播方法，包括計算社交網絡中每個節點的權值；將每個節點的標簽和所述權值傳播給與該節點有邊相連的接收節點；迭代執行根據所述接收節點接收到的各個標簽的數量以及標簽來源節點的權值為所述接收節點賦予新的標簽的步驟，直至預設標簽傳播結束條件滿足為止。但該專利只考慮初始化節點為單一標簽，對于現在社會人作為社交節點的復雜性沒有充分考慮，導致結果不準確。

綜述，現有標簽傳播算法造成迭代結果不穩定的主要因素是第一：更新標簽的原則太過簡單；第二：初始化標簽單一；第三：未曾考慮標簽對于節點的隸屬度。這樣會導致大部分節點都是隨機選取標簽來更新自身的標簽，導致迭代結果不穩定以及準確率不高。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于社交網絡節點雙標簽傳播算法的社區結構劃分方法，通過考慮標簽對于節點的隸屬度，來實現雙標簽的傳播，從而劃分社交網絡的社區結構。

為實現上述發明目的，本發明一種基于社交網絡節點雙標簽傳播算法的社區結構劃分方法，其特征在于，包括以下步驟：

(1)、構造社交網絡圖；

讀取社交網絡數據，構造以社交網絡用戶為節點，用戶間關系為邊的社交網絡圖；

(2)、分配節點標簽及隸屬度初始化；

在社交網絡圖中，為每個節點分配兩個標簽并設置其隸屬度值為其中，i＝1,2,…，表示社交網絡圖中的節點數；

(3)、利用K-shell算法計算各個節點的權值；

(4)、通過迭代更新方式實現社交網絡節點的雙標簽傳播；

(4.1)、初始迭代次數k＝1，最大迭代次數K；設置所有節點對應標簽在傳播過程中未發生變化的百分占比閾值為P；

(4.2)、隨機遍歷社交網絡圖中的所有節點，并按照節點雙標簽傳播規則進行節點雙標簽更新，具體更新過程為：

(4.2.1)、隨機選取未更新節點V_i；