[發明專利]一種傳播網絡的關鍵路徑提取方法

有效

• 申請號: 201711475729.4
• 申請日: 2017-12-29
• 公開（公告）號: CN108183956B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 劉金碩;牟成豪;李改潮;李晨曦;李揚眉;楊廣益;陳煜森;鄧娟
• 申請（專利權）人: 武漢大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/721
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 薛玲

1.一種傳播網絡的關鍵路徑提取方法，其特征在于，包括以下步驟：

步驟1：傳播網絡中添加一個額外節點得到額外節點傳播網絡，并與傳播網絡中的每一個節點建立雙向連接從而建立強連通圖；

步驟2：計算額外節點傳播網絡中任意兩節點間的節點相似度；

步驟3：通過額外節點傳播網絡中節點總數初始化節點影響力列向量，根據節點相似度以及節點出度建立概率轉移矩陣，進行全局投票迭代并在每次全局投票迭代中通過概率轉移矩陣更新節點影響力列向量；

步驟4：遍歷排除額外節點傳播網絡中任意兩個用戶節點的最短路徑，并對每條最短路徑構建路徑節點影響力行向量以及路徑節點相似度行向量；

步驟5：通過額外節點傳播網絡中路徑節點影響力行向量以及路徑節點相似度行向量計算得到每條最短路徑的路徑綜合影響力，根據路徑綜合影響力對每條最短路徑進行排序得到關鍵路徑。

2.根據權利要求1所述的傳播網絡的關鍵路徑提取方法，其特征在于，步驟1中所述傳播網絡為信息傳播網絡；

步驟2中所述節點相似度的計算公式為：

其中，所述額外節點網絡中節點個數為N，a_ij為節點布爾值，若節點i與節點j之間存在連接則a_ij＝1，否則a_ij＝0，S_j(i,j)表示節點i與節點j之間對于節點j的節點相似度，F₁(i)表示節點i的關注節點集合，F₂(i)表示節點i的被關注節點集合，F₁(j)表示節點j的關注節點集合，F₂(j)表示節點j的被關注節點集合，d表示阻尼系數，用來平衡關注節點集合與被關注節點集合兩個因素的權重,max表示求0.01與之間的最大值；

步驟3中所述節點影響力列向量為：

其中，所述額外節點網絡中節點個數為N，I₀～I_N表示節點0至節點N的影響力I₀～I_N初始化均為1/N；

步驟3中所述概率轉移矩陣為：

其中，所述額外節點網絡中節點個數為N，p_ij表示從節點j投票給節點i的票數，K_j表示節點j在額外節點傳播網絡中的節點出度，S_j(i,j)表示節點i與節點j之間對于節點j的節點相似度；

步驟3中所述每次全局投票迭代的過程為：

v_t+1＝Mv_t(0≤t≤Ti)

其中，Ti為最大迭代次數，v_t表示第t次全局投票迭代的節點影響力列向量，每次全局投票迭代通過概率轉移矩陣更新節點影響力列向量至到最大迭代次數Ti或者M為已經全局投票迭代的次數，β為給定的閾值；

步驟4中遍歷排除額外節點的傳播網絡中任意兩個節點的最短路徑，所述路徑節點影響力行向量為：

其中，所述額外節點網絡中節點個數為N，尾部填充0進行位數全局對齊,表示節點i到n的最短路徑的路徑節點影響力行向量；

步驟4中所述路徑節點相似度行向量為：

其中，所述額外節點網絡中節點個數為N，尾部填充0進行位數全局對齊,表示節點i到n的最短路徑的路徑節點相似度行向量；

作為優選，步驟5中所述路徑綜合影響力為：

PR_i＝P_i,nP_i,S^T(0≤i,n≤N-1)

其中，所述額外節點網絡中節點個數為N，通過計算獲得所述額外節點傳播網絡中步驟4中所述每條最短路徑的路徑綜合影響力，進一步根據路徑綜合影響力從大到小排序，從而得到步驟4中任意兩個用戶節點的最短路徑的重要性排序。