[發明專利]基于標簽傳播的可調節重疊社團發現方法

在審

• 申請號: 201710653535.2
• 申請日: 2017-08-02
• 公開（公告）號: CN107392784A
• 公開（公告）日: 2017-11-24
• 發明（設計）人: 方建平;王海威
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 西安利澤明知識產權代理有限公司61222
• 代理人: 賈曉玲

1.基于標簽傳播的可調節重疊社團發現方法，其特征在于包括以下步驟：

步驟1：用戶根據需要，輸入一個可調參數，根據參數的輸入值來選擇重疊社團檢測模式或非重疊社團檢測模式；

步驟2：初始化所有節點標簽；

步驟3：進行標簽傳播；

步驟4：判斷是否達到終止條件，若達到條件則輸出結果，若未達到條件則返回步驟3繼續迭代傳播。

2.如權利要求1所述的基于標簽傳播的可調節重疊社團發現方法，其特征在于：在步驟1中，用戶根據需要，輸入一個可調參數K∈R，根據參數K的輸入值來選擇重疊社團檢測模式或非重疊社團檢測模式；若參數K滿足條件K∈{x|x∈[0,1],x∈R}時，程序采用重疊社團檢測模式，并將模式標志位flag_mode置為0；此時，該參數用于判定重疊社團結構的程度，該參數越大，社團重疊程度越小；反之，該參數越小，社團重疊程度越大，這將影響最終的輸出結果；若參數K的輸入值不滿足條件K∈{x|x∈[0,1],x∈R}時，即時，程序采用非重疊社團檢測模式，將按照傳統的基于標簽傳播社團發現方法對輸入圖進行非重疊社團檢測，并將模式標志位flag_mode置為1。

3.如權利要求1所述的基于標簽傳播的可調節重疊社團發現方法，其特征在于：在步驟2中，首先讀取輸入的圖數據：

G＝(V,E)

其中，V表示網絡中的節點集合；一般情況下，節點V_i代表網絡中的單個節點，總的節點數n＝|V|；E表示網絡中的邊集合，集合中的元素e代表網絡中節點間的邊關系，網絡中的總邊數m＝|E|；節點i的鄰居節點集合用N_i來表示；節點V_i的鄰居節點有k個，用N_i1,N_i2,N_i3,…,N_ik表示，其中k＝|N_i|；

在圖數據輸入后，為所有節點初始化標簽；當flag_mode＝0時，節點V_i的標簽由標簽組表示L_i(t,x)，其中t表示當前迭代周期(迭代次數)，x表示節點V_i的第x個標簽,x的最大值x_max＝k；當flag_mode＝1時，節點V_i的標簽表示為L_i(t)，使所有節點標簽初始化為其節點標號L_i(0)＝i，此時只攜帶一個標簽。

4.如權利要求1所述的基于標簽傳播的可調節重疊社團發現方法，其特征在于：在步驟3中，進行標簽傳播首先令t＝t+1，并將網絡內的所有節點進行隨機排序，得到特定序列O_t，對特定序列O_t中的每一個節點V_i進行標簽傳播，通過V_i節點的所有鄰居節點的標簽進行統計來決定V_i節點的新標簽；

隨后檢測模式標志位flag_mode，當flag_mode＝0時，采用重疊社團檢測模式，刪除節點V_i的標簽組中的標簽，統計節點V_i的鄰居節點中每種標簽的數量總和l_x；將數量總和最大的標簽記為L_M，數量記為l_M，并向V_i的標簽組中添加標簽L_M；對比L_M和l_x，當時，將l_x對應的標簽L_x加入節點V_i的標簽組；

當flag_mode＝1時，采用非重疊社團檢測模式，統計節點V_i的鄰居節點中每種標簽的數量總和l_x，將數量總和最大的標簽L_M更新為節點V_i的新標簽L_i(t)＝L_M。

5.如權利要求1所述的基于標簽傳播的可調節重疊社團發現方法，其特征在于：在步驟4中，判斷所有節點是否擁有其鄰居節點中標簽數量最大的標簽，若所有節點均符合該條件則停止迭代，網絡中擁有相同標簽的節點為同一社團，將所有社團結果輸出；若有節點不滿足上述條件則繼續迭代執行步驟3。