Username   Password       Forgot your password?  Forgot your username? 


Node Importance Ranking of Complex Network based on Degree and Network Density

Volume 15, Number 3, March 2019, pp. 850-860
DOI: 10.23940/ijpe.19.03.p14.850860

Hui Xua,b, Jianpei Zhanga, Jing Yanga, and Lijun Lunc

aCollege of Computer Science and Technology, Harbin Engineering University, Harbin, 150001, China
bLibrary, Heilongjiang University of Chinese Medicine, Harbin, 150040, China
cCollege of Computer Science and Information Engineering, Harbin Normal University, Harbin, 150025, China

(Submitted on November 10, 2018; Revised on December 12, 2018; Accepted on January 8, 2019)


Node importance ranking of complex networks is of great significance to the study of network robustness. The classical centrality measure degree can reflect the number of neighbors of a node, but it ignores the information between its neighbors. In order to mine the important nodes in the network accurately and efficiently, a method of ranking the node importance of complex networks based on multi-attribute evaluation and node deletion is proposed in this paper. Based on the degree attributes of the target node and its neighbors, this method introduces two attributes, which are the local network density centered on the target node and the assortativity coefficient. It takes into account the characteristics of the scale, tightness, and topology of the local area network where the node and its neighbors are located. This paper conducts deliberate attack experiments on four real networks. Through a comparison between the experimental results of the maximal connected coefficient and network efficiency, our approach is proven to be valid and feasible.


References: 35

        1. D. J. Watts and S. H. Strogatz, “Collective Dynamics of Small-World Networks,” Nature, Vol. 393, No. 6684, pp. 440-442, June 1998
        2. A. L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, No. 5439, pp. 509-512, October 1999
        3. M. Canini, D. Venzano, P. Peresíni, D. Kostić, and J. Rexford, “A NICE Way to Test Open-Flow Applications,” in Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, pp. 10, USENIX Association, Berkeley, April 2012
        4. R. P. Satorras and A. Vespignani, “Epidemic Spreading in Scale-Free Networks,” Physical Review Letters, Vol. 86, No. 14, pp. 3200-3203, April 2000
        5. T. Rogers and A. J. Mckane, “Modes of Competition and the Fitness of Evolved Populations,” Physical Review E Statistical Nonlinear & Soft Matter Physics, Vol. 92, No. 3, pp. 032708, September 2015
        6. R. Kinney, P. Crucitti, R. Albert, and V. Latora, “Modeling Cascading Failures in The North American Power Grid,” European Physical Journal B-Condensed Matter, Vol. 46, No. 1, pp. 101-107, July 2005
        7. G. Z. Wang, Y. J. Cao, Z. J. Bao, and Z. X. Han, “A Novel Local-World Evolving Network Model for Power Grid,” Acta Physica Sinica, Vol. 58, No. 6, pp. 3597-3602, July 2009
        8. T. Opsahl, F. Agneessens, and J. Skvoretz, “Node Centrality in Weighted Networks: Generalizing Degree and Shortest Paths,” Social Networks, Vol. 32, No. 3, pp. 245-251, July 2010
        9. X. L. Ren and L. Y. Lü, “Review of Ranking Nodes in Complex Networks,” Chinese Science Bulletin, Vol. 59, No. 13, pp. 1175, January 2014
        10. Y. Moreno, M. Nekovee, and A. F. Pacheco, “Dynamics of Rumor Spreading in Complex Networks,” Physical Review E Statistical Nonlinear and Soft Matter Physic, Vol. 69, No. 2, pp. 066130, June 2004
        11. D. Chen, L. Lü, M. S. Shang, Y. C. Zhang, and T. Zhou, “Identifying Influential Nodes in Complex Networks,” Physica A Statistical Mechanics & its Applications, Vol. 391, No. 4, pp. 1777-1787, February 2012
        12. Y. Liu, B. Wei, Y. Du, F. Y. Xiao, and Y. Deng, “Identifying Influential Spreaders by Weight Degree Centrality in Complex Networks,” Chaos Solitons & Fractals, Vol. 86, pp. 1-7, May 2016
        13. M. Kitsak, L. K. Gallos, S. Havlin, and F. Lilijeros, “Identifying Influential Spreaders in Complex Networks,” Nature Physics, Vol. 6, No. 11, pp. 888-893, January 2010
        14. A. Zeng and C. J. Zhang, “Ranking Spreaders by Decomposing Complex Networks,” Physics Letters A, Vol. 377, No. 14, pp. 1031-1035, June 2013
        15. J. Bae and S. Kim, “Identifying and Ranking Influential Spreaders in Complex Networks by Neighborhood Coreness,” Physica A Statistical Mechanics & its Applications, Vol. 395, No. 4, pp. 549-559, February 2014
        16. L. L. Ma, C. Ma, H. F. Zhang, and B. H. Wang, “Identifying Influential Spreaders in Complex Networks based on Gravity Formula,” Physica A Statistical Mechanics & its Applications, Vol. 451, pp. 205-212, June 2016
        17. Y. Liu, M. Tang, T. Zhou, and Y. H. Do, “Core-Like Groups Result in Invalidation of Identifying Super-Spreader by K-Shell Decomposition,” Scientific Reports, Vol. 5, pp. 9602, May 2015
        18. Y. Liu, M. Tang, T. Zhou, and Y. H. Do, “Improving the Accuracy of the K-Shell Method by Removing Redundant Links: From a Perspective of Spreading Dynamics,” Scientific Reports, Vol. 5, pp. 9602, August 2015
        19. K. I. Goh, E. Oh, B. Kahng, and D. Kim, “Betweenness Centrality Correlation in Social Networks,” Physical Review E Statistical Nonlinear & Soft Matter Physics, Vol. 67, No. 1, pp. 017101, January 2003
        20. G. Sabidussi, “The Centrality of a Graph,” Psychometrika, Vol. 31, No. 4, pp. 581-603, December 1966
        21. M. Rutter and G. W. Brown, “The Reliability and Validity of Measures of Family Life and Relationships in Families Containing a Psychiatric Patient,” Social Psychiatry, Vol. 1, No. 1, pp. 38-53, August 1966
        22. Z. M. Ren, F. Shao, J. G. Liu, and Q. Guo, “Node Importance Measurement based on the Degree and Clustering Coefficient Information,” Acta Physica Sinica, Vol. 62, No. 12, pp. 505, June 2013
        23. J. N. Yang, J. G. Liu, and G. Qiang, “Node Importance Idenfication for Temporal Network based on Inter-Layer Similarity,” Acta Physica Sinica, Vol. 67, No. 4, pp. 048901, January 2018
        24. C. Moore, G. Ghoshal, and M. E. Newman, “Exact Solutions for Models of Evolving Networks with Addition and Deletion of Nodes,” Physical Review E Statistical Nonlinear & Soft Matter Physics, Vol. 74, No. 2, pp. 036121, September 2006
        25. S. Brin and L. Page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine,” Computer Networks, Vol. 56, No. 18, pp. 3825-3833, December 2012
        26. L. Y. Lü, Y. C. Zhang, C. H. Yeung, and T. Zhou, “Leaders in Social Networks, the Delicious Case,” PLoS ONE, Vol. 6, No. 6, pp. e21202, December 2011
        27. Y. R. Gu and Z. Y. Zhu, “Node Ranking in Complex Networks based on LeaderRank and Modes Similarity,” Journal of University of Electronic Science & Technology of China, Vol. 46, No. 2, pp. 441-448, March 2017
        28. E. F. Codd, “A Relational Model for Large Shared Data Banks,” Communications of the ACM, Vol. 13, pp. 377-387, January 1970
        29. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations can Geographic Isolation Explain this Unique Trait ?” Behavioral Ecology and Sociobiology, Vol. 54, No. 4, pp. 396-405, September 2003
        30. J. G. White, E. Southgate, J. N. Thomson, and S. Brenner, “The Structure of The Nervous System of the Nematode Caenorhabditis Elegans,” Philosophical Transactions of the Royal Society B Biological Sciences, Vol. 314, No. 1165, pp. 1-340, November 1986
        31. Y. C. Lai, A. E. Motter, and T. Nishikawa, “Attacks and Cascades in Complex Networks,” Complex Networks, Vol. 650, No. 650, pp. 299-310, August 2004
        32. S. Dereich and P. Mörters, “Random Networks with Sublinear Preferential Attachment: The Giant Component,” Annals of Probability, Vol. 41, No. 1, pp. 329-384, July 2013
        33. Y. R. Ruan, S. Y. Lao, J. D. Wang, L. Bai, and L. D. Chen, “Node Importance Measurement based on Neighborhood Similarity in Complex Network,” Acta Physica Sinica, Vol. 66, No. 3, pp. 038902, December 2017
        34. D. Taylor, S. A. Myers, A. Clauset, M. A. Porter, and P. J. Mucha, “Eigenvector-based Centrality Measures for Temporal Networks,” Physics, Vol. 15, No. 1, pp. 537-574, July 2015
        35. P. W. Holland and S. Leinhardt, “Transitivity in Structural Models of Small Groups,” Small Group Research, Vol. 2, No. 2, pp. 49-66, May 1977


        Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

        This site uses encryption for transmitting your passwords.