Characterizing cycle structure in complex networks

A cycle is the simplest structure that brings redundant paths in network connectivity and feedback effects in network dynamics. An in-depth understanding of which cycles are important and what role they play on network structure and dynamics, however, is still lacking. In this paper, we define the cycle number matrix, a matrix enclosing the information about cycles in a network, and the cycle ratio, an index that quantifies node importance. Experiments on real networks suggest that cycle ratio contains rich information in addition to well-known benchmark indices. For example, node rankings by cycle ratio are largely different from rankings by degree, H-index, and coreness, which are very similar indices. Numerical experiments on identifying vital nodes for network connectivity and synchronization and maximizing the early reach of spreading show that the cycle ratio performs overall better than other benchmarks. Finally, we highlight a significant difference between the distribution of shorter cycles in real and model networks. We believe our in-depth analyses on cycle structure may yield insights, metrics, models, and algorithms for network science. Characterising the structure of real-world complex networks is of crucial importance to understand the emerging dynamics taking place on top of them. In this work the authors investigate the cycle organization of synthetic and real systems, and use such information to define a centrality measure that is more informative than traditional indexes to the end of understanding network dismantling, synchronization, and spreading processes

Automated summary

The paper introduces the concepts of the cycle number matrix and cycle ratio, which prove to be more effective in evaluating node importance compared to traditional indices through experiments. The cycle ratio outperforms other benchmarks in terms of network connectivity, synchronization, and maximizing the reach of spreading.