Transitions in growing networks using a structural complexity approach

Structure changes or transitions are common in growing networks (complex networks, graphs, etc.) and must be precisely determined. The introduced quantitative measure of the structural complexity of the network based on a procedure similar to the renormalization process allows one to reveal such changes. The proposed concept of the network structural complexity accounts for the difference between the actual and averaged network structures on different scales and corresponds to the qualitative comprehension of complexity. The structural complexity can be found for the weighted networks also. The structural complexities for various types of growing networks exhibiting transitions similar to phase transitions were found-the deterministic infinite and finite size artificial networks of different natures including percolation structures, and the time series of various types of cardiac rhythms mapped to complex networks using the parametric visibility graph algorithm. In all the cases the structural complexity of the growing network reaches a maximum near the transition point: the formation of a giant component in the graph or at the percolation threshold for two-dimensional and three-dimensional square lattices when a giant cluster having a fractal structure has emerged. Therefore, the structural complexity of the network allows us to detect and study processes similar to a second-order phase transition in complex networks. The structural complexity of a network node can serve as a kind of centrality index, auxiliary, or generalization to the local clustering coefficient. Such an index provides another new ranking manner for the network nodes. Being an easily computable measure, the network structural complexity might help to reveal different features of complex systems and processes of the real world.