|
|
复杂网络中基于引力模型的关键节点识别方法
|
Abstract:
基于引力模型的关键节点识别方法是常见的一类识别方法，但该类方法存在以下两方面不足，一是衡量节点“质量”时考虑的因素单一，二是所需的运行时间代价较高。通过优化这两方面不足，本文提出了一种改进的引力模型识别方法。首先，综合考虑节点的度、H指数中心性和聚类系数以衡量节点“质量”，并利用信息熵对节点“质量”进行区分。然后，重新考虑节点的影响范围以减少所提方法的运行时间代价。最后，将本文提出的方法与六种基准方法在八个数据集上进行比较。实验结果表明，本文提出的方法在单调性、鲁棒性和准确性方面均表现出明显优势。与基于引力模型的识别方法相比，本文提出方法的运行时间可以降低18.97%~87.65%。
The key node identification method based on gravity model is a common type of identification method, but this type of method has the following two shortcomings: the first is the single factor considered when measuring “mass” of the node; the second is the high cost of required running time. Therefore, this paper proposes an improved gravity model identification method by optimizing these two shortcomings. Initially, “mass” of the node is measured by comprehensively considering the degree, the H-index centrality and the clustering coefficient, and the information entropy is used to distinguish “mass” of the node. Then, the influence range of the node is being reconsidered to reduce the runtime cost of the proposed method. Finally, the method proposed in this paper is compared with six benchmark methods on eight datasets. Experimental results show that the proposed method has obvious advantages in monotonicity, robustness and accuracy. The running time of the proposed method in this paper can be reduced by 18.97% - 87.65% compared with the identification method based on the gravity model.
| [1] | 周建林, 樊瑛, 狄增如. 复杂网络进展[J]. 北京师范大学学报(自然科学版), 2023, 59(5): 691-704. |
| [2] | Su, M., Luan, W., Li, Z., Wan, S. and Zhang, Z. (2019) Evolution and Determinants of an Air Transport Network: A Case Study of the Chinese Main Air Transport Network. Sustainability, 11, Article 3933. https://doi.org/10.3390/su11143933 |
| [3] | Li, G., Zhang, L., Wang, Y. and Kang, Z. (2023) Critical Node Identification Method of Power Grid Based on the Improved Entropy Weight Method. Electronics, 12, Article 2439. https://doi.org/10.3390/electronics12112439 |
| [4] | Li, J., Lin, Y. and Su, Q. (2024) Identifying Critical Nodes of Cyber-Physical Power Systems Based on Improved Adaptive Differential Evolution. Electric Power Systems Research, 229, Article 110112. https://doi.org/10.1016/j.epsr.2024.110112 |
| [5] | Kou, J., Jia, P., Liu, J., Dai, J. and Luo, H. (2023) Identify Influential Nodes in Social Networks with Graph Multi-Head Attention Regression Model. Neurocomputing, 530, 23-36. https://doi.org/10.1016/j.neucom.2023.01.078 |
| [6] | Jain, S. and Sinha, A. (2023) TriBeC: Identifying Influential Users on Social Networks with Upstream and Downstream Network Centrality. International Journal of General Systems, 52, 275-296. https://doi.org/10.1080/03081079.2023.2194642 |
| [7] | Yao, X., Gu, Y., Gu, C. and Huang, H. (2022) Fast Controlling of Rumors with Limited Cost in Social Networks. Computer Communications, 182, 41-51. https://doi.org/10.1016/j.comcom.2021.10.041 |
| [8] | Chen, D., Lü, L., Shang, M., Zhang, Y. and Zhou, T. (2012) Identifying Influential Nodes in Complex Networks. Physica A: Statistical Mechanics and Its Applications, 391, 1777-1787. https://doi.org/10.1016/j.physa.2011.09.017 |
| [9] | Newman, M.E.J. (2005) A Measure of Betweenness Centrality Based on Random Walks. Social Networks, 27, 39-54. https://doi.org/10.1016/j.socnet.2004.11.009 |
| [10] | Kitsak, M., Gallos, L.K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., et al. (2010) Identification of Influential Spreaders in Complex Networks. Nature Physics, 6, 888-893. https://doi.org/10.1038/nphys1746 |
| [11] | Meng, L., Xu, G., Yang, P. and Tu, D. (2022) A Novel Potential Edge Weight Method for Identifying Influential Nodes in Complex Networks Based on Neighborhood and Position. Journal of Computational Science, 60, Article 101591. https://doi.org/10.1016/j.jocs.2022.101591 |
| [12] | Ma, L., Ma, C., Zhang, H. and Wang, B. (2016) Identifying Influential Spreaders in Complex Networks Based on Gravity Formula. Physica A: Statistical Mechanics and Its Applications, 451, 205-212. https://doi.org/10.1016/j.physa.2015.12.162 |
| [13] | Li, Z., Ren, T., Ma, X., Liu, S., Zhang, Y. and Zhou, T. (2019) Identifying Influential Spreaders by Gravity Model. Scientific Reports, 9, Article No. 8387. https://doi.org/10.1038/s41598-019-44930-9 |
| [14] | Zhang, Q., Shuai, B. and Lü, M. (2022) A Novel Method to Identify Influential Nodes in Complex Networks Based on Gravity Centrality. Information Sciences, 618, 98-117. https://doi.org/10.1016/j.ins.2022.10.070 |
| [15] | Lü, L., Chen, D., Ren, X., Zhang, Q., Zhang, Y. and Zhou, T. (2016) Vital Nodes Identification in Complex Networks. Physics Reports, 650, 1-63. https://doi.org/10.1016/j.physrep.2016.06.007 |
| [16] | Lü, L., Zhou, T., Zhang, Q. and Stanley, H.E. (2016) The H-Index of a Network Node and Its Relation to Degree and Coreness. Nature Communications, 7, Article No. 10168. https://doi.org/10.1038/ncomms10168 |
| [17] | Zhao, S. and Sun, S. (2023) Identification of Node Centrality Based on Laplacian Energy of Networks. Physica A: Statistical Mechanics and Its Applications, 609, Article 128353. https://doi.org/10.1016/j.physa.2022.128353 |
| [18] | Xi, Y. and Cui, X. (2023) Identifying Influential Nodes in Complex Networks Based on Information Entropy and Relationship Strength. Entropy, 25, Article 754. https://doi.org/10.3390/e25050754 |
| [19] | Tong, T., Dong, Q., Sun, J. and Jiang, Y. (2023) Vital Spreaders Identification Synthesizing Cross Entropy and Information Entropy with Kshell Method. Expert Systems with Applications, 224, Article 119928. https://doi.org/10.1016/j.eswa.2023.119928 |
| [20] | 吴亚丽,任远光,董昂,等. 基于邻域K-shell分布的关键节点识别方法[J]. 计算机工程与应用, 2024, 60(2): 87-95. |
| [21] | Newman, M.E.J. (2006) Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physical Review E, 74, Article 036104. https://doi.org/10.1103/physreve.74.036104 |
| [22] | Rossi, R. and Ahmed, N. (2015) The Network Data Repository with Interactive Graph Analytics and Visualization. Proceedings of the AAAI Conference on Artificial Intelligence, 29, 4292-4293. https://doi.org/10.1609/aaai.v29i1.9277 |
| [23] | Kunegis, J. (2013) KONECT: The Koblenz Network Collection. Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, 13-17 May 2013, 1343-1350. https://doi.org/10.1145/2487788.2488173 |
| [24] | Moody, J. (2001) Peer Influence Groups: Identifying Dense Clusters in Large Networks. Social Networks, 23, 261-283. https://doi.org/10.1016/s0378-8733(01)00042-9 |
| [25] | Zheng, J. and Liu, J. (2023) A New Scheme for Identifying Important Nodes in Complex Networks Based on Generalized Degree. Journal of Computational Science, 67, Article 101964. https://doi.org/10.1016/j.jocs.2023.101964 |
| [26] | Liu, S. and Gao, H. (2022) The Self-Information Weighting-Based Node Importance Ranking Method for Graph Data. Entropy, 24, Article 1471. https://doi.org/10.3390/e24101471 |
| [27] | Fan, W., He, Y., Han, X. and Feng, Y. (2021) A New Model to Identify Node Importance in Complex Networks Based on DEMATEL Method. Scientific Reports, 11, Article No. 22829. https://doi.org/10.1038/s41598-021-02306-y |
