传统簇生长法时间复杂度高、对分形标度关系刻画不够精准,且关键节点在控制网络结构和功能方面具有重要作用。为选择具有代表性的节点来分析网络自相似分形问题,提出一种基于K-shell的复杂网络簇生长法,通过K-shell分解和节点信息熵选取核心层最具影响力节点作为簇生长法的种子节点计算网络的分形维数。实验结果表明所提方法对网络的分形性质刻画得更加细致,能够计算出更加准确的分形维数。
The traditional cluster-growing method has high time complexity, inaccurate description of fractal scale relationship, and key nodes are important in controlling network structure and function. In order to select representative nodes to analyze the network self-similarity fractal problem, we propose a K-shell-based cluster-growting method of complex networks, in which the most influential nodes in the core layer are selected as the seed nodes of the cluster growth method to calculate the fractal dimension of the network through K-shell decomposition and node information entropy. Experimental results show that the proposed method can perfectly observe the fractal properties of the network and calculate the fractal dimension more accurately.
[1] WATTS D J, STROGATZ S H. Collective dynamics of ‘small world’networks[J]. Nature,1998,393(6684): 440-442.
[2] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[3] SONG C, HAVLIN S, MAKSE H A. Self-similarity of complex networks[J]. Nature, 2005, 433(7024): 392-395.
[4] SONG C, GALLOS L K, HAVLIN S, et al. How to calculate the fractal dimension of a complex network: the box covering algorithm[J]. Journal of Statistical Mechanics: Theory and Experiment, 2007(3): P03006.
[5] SHANKER O. Defining dimension of a complex network[J]. Modern Physics Letters B, 2007, 21(6): 321-326.
[6] SHANKER O. Graph zeta function and dimension of complex network[J]. Modern Physics Letters B, 2007, 21(11): 639-644.
[7] GUO L, XU C. The fractal dimensions of complex networks[J]. Chinese Physics Letters, 2009, 26(8): 088901.
[8] ZHANG S Y. Emergence law of self-similar structure of complex system and complex network[J]. Complex System and Complexity Science,2006(4):41-51.
[9] KIMJ S, GOH K I, KAHNG B, et al. A box-covering algorithm for fractal scaling in scale-free networks[J]. Chaos: an Interdisciplinary Journal of Nonlinear Science, 2007, 17(2): 026116.
[10] GAO L, HU Y, DI Z. Accuracy of the ball-covering approach for fractal dimensions of complex networks and a rank-driven algorithm[J]. Physical Review E, 2008, 78(4): 046109.
[11] SUN Y, ZHAO Y. Overlapping-box-covering method for the fractal dimension of complex networks[J]. Physical Review E, 2014, 89(4): 042809.
[12] ZHENG W, YOU Q, LIU F, et al. Fractal analysis of overlapping box covering algorithm for complex networks[J]. IEEE Access, 2020, 8: 53274-53280.
[13] LIU J L, YU Z G, ANH V. Determination of multifractal dimensions of complex networks by means of the sandbox algorithm[J]. Chaos: an Interdisciplinary Journal of Nonlinear Science, 2015, 25(2): 023103.
[14] SONG Y Q, LIU J L, YU Z G, et al. Multifractal analysis of weighted networks by a modified sandbox algorithm[J]. Scientific reports, 2015, 5(1): 1-10.
[15] WEI B, DENG Y. A cluster-growing dimension of complex networks: from the view of node closeness centrality[J]. Physica A: Statistical Mechanics and its Applications, 2019, 522: 80-87.
[16] XIE L X, SUN H, YANG H Y, et al. Key node identification method of complex network based on K-shell[J]. Journal of Tsinghua University(Natural Science Edition),2022,62(5):849-861.
[17] GUO C, YANG L, CHEN X, et al. Influential nodes identification in complex networks via information entropy[J]. Entropy, 2020, 22(2): 242.
[18] ZHANG J, ZHANG Q, WU L, et al. Identifying influential nodes in complex networks based on multiple local attributes and information entropy[J]. Entropy, 2022, 24(2): 293.
[19] FAN W L, LIU Z G, HU P. Identifying node importance based on information entropy in complex networks[J]. Physica Scripta, 2013, 88(6): 065201.
[20] NEWMAN M E J, WATTS D J. Renormalization group analysis of the small-world network model[J]. Physics Letters A, 1999, 263(4-6): 341-346.
[21] ROZENFELD H D, SONG C, MAKSE H A. Small-world to fractal transition in complex networks: a renormalization group approach[J]. Physical review letters, 2010, 104(2): 025701.
