[發明專利]一種通信網絡中關鍵節點的選取方法及系統

有效

• 申請號: 201910202036.0
• 申請日: 2019-03-18
• 公開（公告）號: CN109921939B
• 公開（公告）日: 2022-04-15
• 發明（設計）人: 周明洋;吳向陽;曹楊;羅燎;廖好;陸克中;毛睿
• 申請（專利權）人: 中電科大數據研究院有限公司;深圳大學
• 主分類號: H04L41/0803
• 分類號: H04L41/0803;H04L41/12;H04L41/14;H04L41/28
• 代理公司: 北京高沃律師事務所 11569
• 代理人: 程華

本發明公開了一種通信網絡中關鍵節點的選取方法及系統。本發明的選取方法基于瑞利熵的重疊影響力算法，計算關鍵節點間的影響力，提高了關鍵節點的綜合影響力，同時由于網絡中環路的情況，網絡中信息的傳遞的情況混雜，本發明通過瑞利熵的重疊影響力算法刻畫網絡中信息的傳遞混雜行為，并且在實際網絡中有較好的表現，并且本發明通過對關鍵節點移除，使整個網絡將會散列成很多個互不連接的群體，在實際應用中，能較好的控制病毒或信息的傳播。

技術領域

本發明涉及網絡管理領域，特別涉及一種通信網絡中關鍵節點的選取方法及系統。

背景技術

大量自然和人工系統的結構都可以抽象為由點和線組成的網絡，包括食物鏈網絡、社交網絡等。這些網絡具有相似的拓撲網絡，其次這些網絡也具有一些類似的動力學行為。信息傳播和擴散是網絡中常見的一種動力學行為，在網絡中，信息以一定的概率從一個節點傳遞到另一個節點，傳播概率一般存在一個臨界閾值，如果傳播概率高于該臨界閾值，初始的少量信息會迅速擴散到整個網絡；反之，信息在傳遞過程中會消亡。在網絡的拓撲結構分析中發現少量的節點對整個網絡的連通性具有重要影響，網絡中的信息傳遞主要通過這些關鍵節點的轉發進行。如果對網絡中信息傳播行為進行控制，只需要對網絡中的關鍵節點進行控制或者保護即可，因此如何尋找高影響力節點是問題的關鍵，很多人致力于高影響力節點的研究。

傳統的高影響力節點選取的算法，主要有兩種方案：啟發式算法和基于目標函數的優化算法。啟發式算法一般根據節點的重要性進行選擇，節點重要性可根據節點度、介數、聚類系數、PageRank指標進行確定。根據使用信息的差異，啟發式算法可分為基于局部信息的重要性指標和基于全局拓撲信息的重要性指標。基于局部信息的方法確定節點的重要性時僅根據節點的鄰居節點或次近鄰節點確定，包括節點度、2-近鄰、聚類系數等。而基于全局拓撲信息的方法計算節點的重要性時需要整個網絡的拓撲信息，包括介數、PageRank、非回溯矩陣、隨機游走等指標。

在啟發式算法中存在不同指標對關鍵節點的選取方法，介紹如下：

節點度(HD，High Degree)，該算法根據節點的度進行排序，依次選擇度大的節點，通常為便于比較而對中心性指標作歸一化處理，度為k_i的節點的歸一化的度中心性值定義為：

其中，N表示網絡中節點的總數量。

節點介數(BW，Betweenness)，節點的介數定義為網絡中所有最短路徑中經過該節點的路徑數量占最短路徑總數的比例，該算法依次選擇介數大的節點作為關鍵節點。具體地，節點i的介數定義為：

其中，g_st為從節點s到節點t的最短路徑的數目，為從節點s到節點t的g_st條最短路徑中經過節點i的最短路徑的數目。

K-殼算法(K-shell)，K-shell和K-core成對出現。網絡中反復刪除度小于K的節點，直至所有節點的度大于等于K為止，剩余的網絡即為該網絡的K-core。如果一個節點存在于K-core中而不存在于(K+1)-core中，則該節點位于K-shell中。該算法根據節點的K-shell依次選擇K-shell大的節點。

傳統算法中還有基于稀疏矩陣的綜合影響力算法(CI)，該算法基于邊滲流理論，在忽略網絡中環路的情況下，僅考慮網絡為樹狀網絡，可以推導出單個節點影響力為公式：

S_m＝(d_m-1)∑_j∈Ball-2(d_j-1)

其中，d_m為節點m的度，Ball-2是距離節點m為2的點集合，d_j是與節點m距離為2的節點的度，該算法選擇關鍵節點時根據單個節點的影響力進行排序，依次選擇關鍵節點。