Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes

Weijin JIANG; Ying YANG; Tiantian LUO; Wenying ZHOU; En LI; Xiaowei ZHANG

doi:10.11959/j.issn.2096-3750.2022.00282

您当前的位置：

首页 >

文章列表页 >

Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes

Theory and Technology | 更新时间：2024-06-05

- Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes
- Chinese Journal on Internet of Things Vol. 6, Issue 3, Pages: 133-145(2022)
- 作者机构：
  
  1. 湖南工商大学计算机学院，湖南长沙 410205
  2. 数据智能与智慧社会国家重点实验室（培育）基地，湖南长沙 410205
  3. 湖南工商大学前沿交叉学院，湖南长沙 410205
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-3750.2022.00282
  CLC： TP301.6
- Online First：2022-09，
  
  Published：30 September 2022
- 稿件说明：
移动端阅览
Weijin JIANG, Ying YANG, Tiantian LUO, et al. Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes[J]. Chinese Journal on Internet of Things, 2022, 6(3): 133-145.
DOI：

Weijin JIANG, Ying YANG, Tiantian LUO, et al. Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes[J]. Chinese Journal on Internet of Things, 2022, 6(3): 133-145. DOI： 10.11959/j.issn.2096-3750.2022.00282.

摘要

挖掘网络中的关键节点在信息传播、病毒营销、舆论控制等的演进过程中发挥着巨大的作用，关键节点的识别可以有效地帮助控制网络攻击、检测金融风险、抑制病毒和谣言的传播、防止恐怖袭击等。为了突破现有节点影响力评估方法存在的算法复杂度高、准确度低以及评价指标内在作用机制评估角度片面的限制，提出了一种识别关键节点的综合影响力（CI

comprehensive influence）评估算法。该算法通过同时处理网络的局部和全局拓扑来对节点重要性进行排序，从多个角度整合网络属性信息，提供更全面的节点重要性度量。算法中的全局属性考虑的是邻居节点以及节点之间的最短距离，节点的信息熵用来表示节点的局部属性，通过一个参数来调整全局和局部属性的权重比。使用SIR（susceptible infected recovered）模型和Kendall相关系数作为评价标准，在不同规模的现实世界网络上进行实验分析，结果表明，所提出的方法能在识别关键节点方面优于介数中心性（BC

betweenness centrality）、接近中心性（CC

closeness centrality）、重力指数中心性（GIC

gravity index centrality）、全局结构模型（GSM

global structure model）等著名的启发式算法，并且具有更好的排序单调性、更稳定的度量结果，对网络拓扑的适应性更强，适用于绝大多数具有不同结构的真实网络。

Abstract

Mining key nodes in the network plays a great role in the evolution of information dissemination

virus marketing

and public opinion control

etc.The identification of key nodes can effectively help to control network attacks

detect financial risks

suppress the spread of viruses diseases and rumors

and prevent terrorist attacks.In order to break through the limitations of existing node influence assessment methods with high algorithmic complexity and low accuracy

as well as one-sided perspective of assessing the intrinsic action mechanism of evaluation metrics

a comprehensive influence (CI) assessment algorithm for identifying critical nodes was proposed

which simultaneously processes the local and global topology of the network to perform node importance.The global attributes in the algorithm consider the information entropy of neighboring nodes and the shortest distance nodes between nodes to represent the local attributes of nodes

and the weight ratio of global and local attributes was adjusted by a parameter.By using the SIR (susceptible infected recovered) model and Kendall correlation coefficient as evaluation criteria

experimental analysis on real-world networks of different scales shows that the proposed method is superior to some well-known heuristic algorithms such as betweenness centrality (BC)

closeness centrality (CC)

gravity index centrality(GIC)

and global structure model (GSM)

and has better ranking monotonicity

more stable metric results

more adaptable to network topologies

and is applicable to most of the real networks with different structure of real networks.

关键词

Keywords

references

LI X X , HU W , SHANG T , et al . Security analysis of power system network based on complex network [C ] // Proceedings of 2020 IEEE 4th Conference on Energy Internet and Energy System Integration . Piscataway,IEEE Press , 2020 : 4336 - 4341 .

KHOSROSERESHKI F , MOAVENI B . Traffic modeling and validation for intersecting metro lines by considering the effect of transfer stations [J ] . IEEE Access, , 10 : 1946 - 1955 .

GARCIA J O , ASHOURVAN A , MULDOON S , et al . Applications of community detection techniques to brain graphs,algorithmic considerations and implications for neural function [J ] . Proceedings of the IEEE , 2018 , 106 ( 5 ): 846 - 867 .

ZHAO J Y , MO H M , DENG Y . An efficient network method for time series forecasting based on the DC algorithm and visibility relation [J ] . IEEE Access , 8 : 7598 - 7608 .

LI X Y , ZHOU M Y , WU X Y , et al . A novel method to identify multiple influential nodes in complex networks [J ] . Scientia Sinica Informationis , 2019 , 49 ( 10 ): 1333 - 1342 .

LIU X , HE D , LIU C , et al . Social network information propagation dynamic analysis based on time-varying damping motion [J ] . Scientia Sinica Informationis , 2021 , 51 ( 11 ): 1867 .

TRONCOSO F , WEBER R . Integrating relations and criminal background to identifying key individuals in crime networks [J ] . Decision Support Systems , 2020 ,139,113405.

HUANG C S , ZHU L . Robust evaluation method of communication network based on the combination of complex network and big data [J ] . Neural Computing and Applications , 2021 , 33 ( 3 ): 887 - 896 .

FAN L J , JIANG Z Y , WANG Q . Robustness evaluation for real traffic network from complex network perspective [J ] . International Journal of Modern Physics C , 2021 , 32 ( 8 ): 2150102 .

ZHUD R , WANGH F , DUAN J D , et al . Study of Improved PageRank algorithm in key node identification of power system [C ] // Proceedings of 2020 4th International Conference on HVDC (HVDC) . Piscataway:IEEE Press , 2020 : 1154 - 1159 .

XU X , ZHU C , WANG Q Y , et al . Identifying vital nodes in complex networks by adjacency information entropy [J ] . Scientific Reports,2020,10 , 2691 .

MAJI G , MANDAL S , SEN S . A systematic survey on influential spreaders identification in complex networks with a focus on K-shell based techniques [J ] . Expert Systems With Applications , 2020 ,161:113681.

MAJI G , NAMTIRTHA A , DUTTA A , et al . Influential spreaders identification in complex networks with improved K-shell hybrid method [J ] . Expert Systems With Applications , 2020 ,144,113092.

ZHAO G H , JIA P , ZHOU A M , et al . InfGCN,identifying influential nodes in complex networks with graph convolutional networks [J ] . Neurocomputing , 2020 , 414 : 18 - 26 .

YANG H H , AN S . Critical nodes identification in complex networks [J ] . Symmetry , 2020 , 12 ( 1 ): 123 .

GUO C G , YANG L W , CHEN X , et al . Influential nodes identification in complex networks via information entropy [J ] . Entropy (Basel,Switzerland) , 2020 , 22 ( 2 ): 242 .

MAHARANI W , ADIWIJAYA , GOZALI A A . Degree centrality and eigenvector centrality in twitter [C ] // Proceedings of 2014 8th International Conference on Telecommunication Systems Services and Applications (TSSA) . Piscataway,IEEE Press , 2014 : 1 - 5 .

LIU X Y , DING N , LIU C , et al . Novel social network community discovery method combined local distance with node rank optimization function [J ] . Applied Intelligence , 2021 , 51 ( 7 ): 4788 - 4805 .

WANG Y F , YAN G H , MA Q Q , et al . Identifying influential spreaders on weighted networks based on Cluster Rank [C ] // Proceedings of 2017 10th International Symposium on Computational Intelligence and Design (ISCID) . Piscataway,IEEE Press , 2017 : 476 - 479 .

KITSAK M , GALLOS L K , HAVLIN S , et al . Identification of influential spreaders in complex networks [J ] . Nature Physics , 2010 , 6 ( 11 ): 888 - 893 .

MALANG K , WANG S L , PHAPHUANGWITTAYAKUL A , et al . Identifying influential nodes of global terrorism network,a comparison for skeleton network extraction [J ] . Physica A,Statistical Mechanics and Its Applications , 2020 ,545,123769.

OKAMOTO K , CHEN W , LI X Y . Ranking of closeness centrality for large-scale social networks [C ] // Frontiers in Algorithmics , 2008 : 186 - 195 .

BARTHLEMY M . Betweenness centrality in large complex networks [J ] . The European Physical Journal B - Condensed Matter , 2004 , 38 ( 2 ): 163 - 168 .

KUMAR P V , BALASUBRAMANIAN C . Trilateral spearman katzcentrality based least angle regression for influential node tracing in social network [J ] . Wireless Personal Communications , 2022 , 122 ( 3 ): 2767 - 2790 .

YANG Y Z , WANG X , CHEN Y , et al . Identifying key nodes in complex networks based on global structure [J ] . IEEE Access , 8 : 32904 - 32913 .

IBNOULOUAFI A , EL HAZITI M , CHERIFI H . M-Centrality,identifying key nodes based on global position and local degree variation [J ] . Journal of Statistical Mechanics,Theory and Experiment , 2018 , 2018 ( 7 ): 073407 .

LI Z , REN T , MA X Q , et al . Identifying influential spreaders by gravity model [J ] . Scientific Reports , 2019 9,8387.

ZHUANG Y B , LI Z H , ZHUANG Y J . Identification of influencers in online social networks,measuring influence considering multidimensional factors exploration [J ] . Heliyon , 2021 , 7 ( 4 ): e06472 - 327 .

CHIANG M F , LIM E P , LEE W C , et al . CO2Vec,embeddings of co-ordered networks based on mutual reinforcement [C ] // Proceedings of 2020 IEEE 7th International Conference on Data Science and Advanced Analytics . Piscataway,IEEE Press , 2020 : 148 - 157 .

XU Y , FENG Z D , QI X Q . Signless-Laplacian eigenvector centrality:a novel vital nodes identification method for complex networks [J ] . Pattern Recognition Letters , 2021 , 148 : 7 - 14 .

WU X M , WU J S , LI Y F , et al . Link prediction of time-evolving network based on node ranking [J ] . Knowledge-Based Systems , 2020 ,195,105740.

PAGE L , BRIN S , MOTWANI R , et al . The Pagerank citation ranking,bringing order to the Web [EB ] . 1998 .

ZHANG Y C , YU J X , HOU J Y , et al . HITS and related algorithms [EB ] . 2006 .

LI Q , ZHOU T , LÜL Y , , et al . Identifying influential spreaders by weighted LeaderRank [J ] . Physica A,Statistical Mechanics and Its Applications , 2014 , 404 : 47 - 55 .

TONG Q , WEI S , CHANG Z . How to identify the most powerful node in complex networks? A novel entropy centrality approach [J ] . Entropy , 2017 , 19 ( 11 ): 614 .

BARBEHENN M . A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices [J ] . IEEE Transactions on Computers , 1998 , 47 ( 2 ): 263 .

NIE T Y , GUO Z , ZHAO K , et al . Using mapping entropy to identify node centrality in complex networks [J ] . Physica A,Statistical Mechanics and Its Applications , 2016 , 453 : 290 - 297 .

MA LL , MA C , ZHANG H F , et al . Identifying influential spreaders in complex networks based on gravity formula [J ] . Physica A,Statistical Mechanics and Its Applications , 2016 , 451 : 205 - 212 .

ULLAH A , WANG B , SHENG J F , et al . Identification of nodes in fluence based on global structure model in complex networks [J ] . Scientific Reports,2021,11 , 6173 .

Views

387

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Load optimization strategy for low earth orbit satellite communication systems based on critical node analysis

Related Author

MI Yuting

ZHAO Bai

LIU Xiaoyu

OUYANG Jian

LIN Min

Related Institution

School of Communications and Information Engineering, Nanjing University of Posts and Telecommunications

⁰