[發明專利]基于節點重要度的標簽傳播社區發現算法

在審

• 申請號: 201710238093.5
• 申請日: 2017-04-13
• 公開（公告）號: CN107194818A
• 公開（公告）日: 2017-09-22
• 發明（設計）人: 張賢坤;任靜;莢佳;宋琛;張倩
• 申請（專利權）人: 天津科技大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 天津盛理知識產權代理有限公司12209
• 代理人: 王利文

技術領域

本發明屬于智能信息處理技術領域，尤其是一種基于節點重要度的標簽傳播社區發現算法。

背景技術

社會網絡中的社區發現對于社會網絡分析具有重要意義。近10年來，已有很多社會網絡社區發現方法被提出，依據采用的求解策略不同，主要可以分為基于優化的社區發現方法和基于啟發式的社區發現方法，基于優化的方法通過設置目標函數并迭代逼近函數最優值實現社區發現，具有代表性的方法包括譜方法和模塊度最大化方法。基于啟發式策略的方法通過設置啟發規則來尋找最優社區劃分，代表性的算法如GN(Girvan-Newman)算法和WH(Wu-Huberman)算法。

標簽傳播算法是一種基于圖的半監督學習方法，其基本思路是用已標記節點的標簽信息去預測未標記節點的標簽信息。其利用樣本間的關系建立關系完全圖模型，在完全圖中，節點包括已標注和未標注數據，其邊表示兩個節點的相似度，節點的標簽按相似度傳遞給其他節點。標簽數據就像是一個源頭，可以對無標簽數據進行標注，節點的相似度越大，標簽越容易傳播。

2007年，Raghavan等人提出了一種基于標簽傳播思想的快速社區發現算法LPA(Label Propagation Algorithm)，LPA算法在迭代更新節點標簽的過程中存在不確定性和隨機性，導致其結果準確性和穩定性常常不能達到預期。之后又有學者分別從不同角度對LPA算法進行改進，但是這些算法僅根據標簽的個數評判標簽的影響力，沒有考慮標簽更新的順序和節點自身重要度對標簽選擇的影響。在大規模社交網絡中，比如微博社會網絡，如果考慮節點先驗屬性對節點重要度的影響。

綜上所述，現有的標簽傳播算法在準確性和穩定性上都存在很大的提升空間。

發明內容

本發明的目的在于克服現有技術的不足，提供基于節點重要度的標簽傳播社區發現算法，能夠在復雜度相似的情況下能夠顯著提高社區發現的質量，縮短迭代周期，從而提高社區發現的準確性和穩定性。

本發明解決其技術問題是采取以下技術方案實現的：

一種基于節點重要度的標簽傳播社區發現算法，包括以下步驟：

步驟1：初始化每個節點的唯一標簽；

步驟2：計算每個節點重要度，并按節點重要度從高到低對節點排序，生成有序序列；

步驟3：設置迭代次數t＝1；

步驟4：對有序序列中的任意節點，根據標簽選擇方法和標簽更新規則將該節點的標簽更新為其鄰接節點標簽集中影響力最大的標簽；

步驟5：設置最大迭代次數為max Iter，若迭代次數t＝＝max Iter或每個節點的標簽為影響力最大的標簽，則將具有同樣標簽的節點歸入相同社區，處理結束；否則，迭代次數t加1，返回步驟4；

進一步，所述步驟2節點重要度的計算公式為：

其中，NI(i)表示節點i的重要度，Inf(i)表示節點i的先驗重要度，α表示衡量鄰接節點重要度對節點i影響力的系數，α取值從0到1，N(i)表示節點i的鄰接節點集，d(j)表示節點i的鄰接節點j的度數。

進一步，所述步驟4標簽選擇方法的計算公式如下：

其中，LI(i,l)表示標簽l對節點i的影響力，N^l(i)表示節點i周圍標簽為l的集合，d(j)表示節點i的鄰接節點j的度數,NI(j)表示節點i的相鄰節點j的重要度。

進一步，所述步驟4標簽更新規則的計算公式如下：

其中，c_i表示節點i的鄰接標簽出現多個標簽的數量同為最大值時選擇的標簽，l max表示標簽數量為最大值的標簽集合，LI(i,l)表示標簽l對節點i的影響力。

本發明的優點和積極效果是：

本發明通過計算每個節點重要度并按節點重要度從高到低對節點排序，同時采用標簽選擇方法和標簽更新規則進行節點標簽更新，能夠在復雜度相似的情況下能夠顯著提高社區發現的質量，縮短迭代周期，能夠準確并穩定地發現網絡中的社區，可廣泛用于社區發現、社交網絡等領域。

附圖說明

圖1a為本發明更新節點4的示意圖；

圖1b為本發明更新節點6的示意圖；

圖1c為本發明更新節點2的示意圖；

圖2為本發明與NIBLPA、LPA在不同參數α得到的模塊度對比圖；

圖3為本發明與NIBLPA、LPA在參數α＝0.4時的50次重復試驗對比圖；