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

doi:10.23940/ijpe.19.03.p14.850860

Int J Performability Eng ›› 2019, Vol. 15 ›› Issue (3): 850-860.doi: 10.23940/ijpe.19.03.p14.850860

Previous Articles Next Articles

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

Hui Xu^{a, b}, Jianpei Zhang^{a, *}, Jing Yang^a, and Lijun Lun^c

a College of Computer Science and Technology, Harbin Engineering University, Harbin, 150001, China;
b Library, Heilongjiang University of Chinese Medicine, Harbin, 150040, China;
c College of Computer Science and Information Engineering, Harbin Normal University, Harbin, 150025, China

Submitted on ; Revised on ;
Contact: zhangjianpei@hrbeu.edu.cn
About author:Hui Xu is studying for a doctorate in the College of Computer Science and Technology at Harbin Engineering University. She works in Heilongjiang University of Chinese Medicine. Her research interests are social computing, data mining technology, and software theory.Jianpei Zhang is a professor in the College of Computer Science and Technology at Harbin Engineering University. He is the director of the Institute of Computer Software and Theory of Harbin Engineering University. He has long been engaged in database theory and application, data mining technology, software theory, and other aspects of teaching and research work. Jing Yang is a professor in the College of Computer Science and Technology at Harbin Engineering University and an expert of the Harbin Informatization Committee. Her main research interests include database theory and application, data mining technology, knowledge database system, and software theory.Lijun Lun is a professor in the College of Computer Science and Information Engineering at Harbin Normal University. He teaches courses on operating systems and software engineering, object-oriented software engineering, advanced software engineering, and new software technologies. His research interests are software testing and software metrics.

Abstract

Abstract: 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.

Key words: node importance, robustness, degree, network density

Hui Xu, Jianpei Zhang, Jing Yang, and Lijun Lun. Node Importance Ranking of Complex Network based on Degree and Network Density [J]. Int J Performability Eng, 2019, 15(3): 850-860.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

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ć,J. Rexford, “A NICE Way to Test Open-Flow Applications,” inProceedings 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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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

[1]	Jianwei Zhang, Chunfeng Du, Zengyu Cai, Wenqian Wang, and Zuodong Wu. Content-Centric Network Caching Strategy based on Node Situational Degree [J]. Int J Performability Eng, 2019, 15(8): 2190-2198.
[2]	Kai Li, Wei Wu, and Fusheng Liu. Complex Network Reliability Analysis based on Entropy Theory [J]. Int J Performability Eng, 2019, 15(6): 1642-1651.
[3]	Chaolong Zhang, Yigang He, Shanhe Jiang, Lanfang Zhang, and Xiaolu Wang. Analog Circuit Fault Prognostic Approach using Optimized RVM [J]. Int J Performability Eng, 2019, 15(5): 1453-1461.
[4]	Yan Liu, Chunliang Chen, Kangzhu Chen, Weilong Chen, and Lijun Zhang. Evaluationof Equipment Node Importance based on Bi-Layer Coupling Complex Networks [J]. Int J Performability Eng, 2019, 15(2): 374-386.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended 10