Weighted Directed Network Evaluation Algorithm Based on Propagation Model
ZHANG Xiruo, LIAO Yuan, PENG Jiaqin, YANG Yuhang, HUANG Liya
a. College of Electronic and Optical Engineering; b. College of Flexible Electronics(future technology), Nanjing University of Posts and Telecommunications, Nanjing 210023, China
Abstract：To investigate node importance in the extensive weighted directed networks in real-world scenarios, this paper proposes the Cross K-Propagation Number (CKPN) algorithm, which is a node evaluation algorithm for weighted directed networks based on propagation models. This algorithm analyzes node information from both local and global perspectives, examines the interaction between nodes under different propagation orders and adjusts the contribution allocation of the in-degree and out-degree in the directed network. ARPA network, WSIR model and deliberate attack model are used to verify the effectiveness of the proposed method. The results show that the CKPN algorithm considers the information comprehensively and the evaluation results are detailed. It has good effect in large-scale networks and is more accurate than the traditional algorithm that only considers the network topology.
[1] 王淑良,陈辰,张建华,等.基于复杂网络的关联公共交通系统韧性分析[J].复杂系统与复杂性科学,2022,19(4):47-54. WANG S L, CHEN C, ZHANG J H, et al. Resilience analysis of public interdependent transport system based on complex network[J]. Complex Systems and Complexity Science, 2022, 19(4):47-54. [2] 王小俊,王彬,夏一丹,等.基于介中心性及K-shell的脑网络核心节点评价方法[J].计算机工程与应用,2017,53(11):44-49. WANG X J, WANG B, XIA Y D, et al.Evaluation method of node centrality for brain network based on betweenness centrality and K-shell[J]. Computer Engineering and Applications, 2017, 53(11):44-49. [3] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1978, 1(3):215-239. [4] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1):35-41. [5] SABIDUSSI G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4):581-603. [6] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11):888-893. [7] 吴英晗,李明达,胡枫.基于熵的多属性决策超网络重要节点识别方法[J].复杂系统与复杂性科学, 2023, 20(4):40-46. WU Y H, LI M D, HU F.A. Multi-attribute decision making method based on entropy to identify important nodes in hypernetworks[J]. Complex Systems and Complexity Science, 2023, 20(4):40-46. [8] KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the Association for Computing Machinery, 1999, 46(5):604-632. [9] DONG C, XU G, MENG L, et al. CPR-TOPSIS: a novel algorithm for finding influential nodes in complex networks based on communication probability and relative entropy[J]. Physica A: Statistical Mechanics and Its Applications, 2022(603):127797. [10] 王班,马润年,王刚,等.改进的加权网络节点重要性评估的互信息方法[J].计算机应用, 2015, 35(7):1820-1823. WANG B, MA R N, WANG G, et al. Improved evaluation method for node importance based on mutual information in weighted networks[J]. Journal of Computer Applications, 2015, 35(7):1820-1823. [11] 王雨,郭进利.基于多重影响力矩阵的有向加权网络节点重要性评估方法[J].物理学报, 2017, 66(5):050201. WANG Y, GUO J L. Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix[J]. Acta Physica Sinica, 2017, 66(5):050201. [12] PAGE L, BRIN S, MOTWANI R, et al. The pagerank citation ranking: bringing order to the web[J]. World Wide Web, 1999, 2(1):107-117. [13] 潘伟丰,李兵,马于涛,等.基于加权PageRank算法的关键包识别方法[J].电子学报, 2014, 42(11):2174-2183. PAN W F, LI B, MA Y T, et al. Identifying the key packages using weighted pagerank algorithm[J]. Acta Electronica Sinica, 2014, 42(11):2174 -2183. [14] XU X, ZHU C, WANG Q Y, et al. Identifying vital nodes in complex networks by adjacency information[J]. Scientific Reports, 2020(10):2619. [15] XU X, ZHU X Q, HUANG X Q, et al. Node importance evaluation of multi-level directed weighted network based on ISM and SH combination model[C]. International Conference on Informatics, Networking and Computing, 2022(10):69-75. [16] 黄丽亚,汤平川,霍宥良,等.基于加权K-阶传播数的节点重要性[J].物理学报, 2019, 68(12):128901. HUANG L Y, TANG P C, HUO Y L, et al. Node importance based on the weighted K-order propagation number algorithm[J]. Acta Physica Sinica, 2019, 68(12):128901. [17] 周立欣,刘臣,霍良安,等.基于交叉度的有向网络中心节点识别算法研究[J].计算机应用研究, 2016, 33(11):3299-3306. ZHOU L X, LIU C, HUO L A, et al. Identification algorithms of center node in directed complex networks based on cross degree[J]. Application Research of Computers, 2016, 33(11):3299-3306. [18] HU P, FAN W L, MEI S W. Identifying node importance in complex networks[J]. Physica A, 2015(429):169-176. [19] GARAS A, ARGYRAKIS P, ROZENBLAT C, et al. Worldwide spreading of economic crisis[J]. New Journal of Physics, 2010, 12(11):113043. [20] KNIGHT W R. A computer method for calculating kendall′s tau with ungrouped data [J]. Journal of the American Statistical Association, 1966, 61(314):436-439. [21] SADE D S. Linkages and cliques in grooming matrices[J]. Folia Primatologica, 1972, 18(3/4):196-223. [22] COLEMAN J S. Introduction to Mathematical Sociology[M]. London: London Free Press Glencoe, 1972. [23] FREEMAN L C, WEBSTER C M, KIRKE D M. Exploring social structure using dynamic three-dimensional color images[J]. Social Networks, 1988, 20(2):109-118. [24] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393:440-442. [25] JAMES M. Peer Influence groups: identifying dense clusters in large networks[J]. Social Networks, 2001, 23(4):261-283. [26] YANG G Z, QI X G, LIU L F. Research on network robustness based on different deliberate attack methods[J]. Physica A, 2022(545):123588. [27] WHITE J G, SOUTHGATE E, THOMSON J N, et al. Factors that determine connectivity in the nervous system of Caenorhabditis elegans[J]. Cold Spring Harb Symp Quant Biol, 1983, 48:633-640.
