Characterizing cycle structure in complex networks
arXiv:2001.08541
Abstract
Cycle is the simplest structure that brings redundant paths in network connectivity and feedback effects in network dynamics. Focusing on cycle structure, this paper defines a new matrix, named cycle number matrix, to represent cycle information of a network, and an index, named cycle ratio, to quantify the node importance. Experiments on real networks suggest that cycle ratio contains rich information in addition to well-known benchmark indices, for example, the node rankings by cycle ratio are largely different from rankings by degree, H-index, coreness, betweenness and articulation ranking, while the rankings by degree, H-index, coreness are very similar to each other. Extensive experiments on identifying vital nodes that maintain network connectivity, facilitate network synchronization and maximize the early reach of spreading show that cycle ratio is competitive to betweenness and overall better than other benchmarks. We believe the in-depth analyses on cycle structure may yield novel insights, metrics, models and algorithms for network science.
35 pages, 26 figures and 8 tables
References in corpus (11)
- Finding community structure in networks using the eigenvectors of matrices
- Synchronization in complex networks
- Mitigation of Malicious Attacks on Networks
- Thresholds for epidemic spreading in networks
- The Rich-Club Phenomenon In The Internet Topology
- Local structure of directed networks
- Fast influencers in complex networks
- Identifying vital nodes by Achlioptas process
- Distribution of shortest cycle lengths in random networks
- Statistical analysis of articulation points in configuration model networks
- Control Efficacy on COVID-19