Many complex systems including neural networks, ecosystems, physical materials or the World Wide Web involve individual components which interact in large networks. The structure of these networks influences the character and properties of these systems, and researchers have found that useful insight into their dynamics emerges from analysis of the eigenvalues and eigenvectors of the so-called adjacency matrix, which reflects the network structure. Such analysis is especially useful for understanding how systems behave nearby a stationary state, as happens in disease spreading or biological systems perturbed from stable states.
Most systems are best described as directed networks, in which the interactions between elements have a preferred direction. Unfortunately, the properties of the eigenvectors of random graphs have mainly been studied so far for undirected graphs, and the statistical properties of directed random graphs have so far eluded mathematical analysis. In a new paper, LML External Fellow Fernando Metz and Izaak Neri of Kings College London help rectify this issue by developing an exact theory for the statistical properties of the eigenvectors of directed random graphs with a prescribed degree distribution. They address one issue of great importance in networks in general, which is the frequent occurrence of a general delocalization-localization transition with changes in system structure. Such transitions generally involve a qualitative change in system properties, such as the metal-insulator phase transition in solid state physics, or the transition from an algorithmically successful to a failure phase in spectral algorithms.
In the paper, Metz and Neri derive exact analytic expressions for the inverse participation ratio and for the critical point of the localization-delocalization transition in the directed network case. In short, if the network outdegree distribution has finite moments, then right eigenvectors at the edge of the spectrum are localized below a critical mean outdegree. Surprisingly, this critical point of the localization-delocalization transition is universal, in the sense it only depends on the lower moments of the distribution of the edge weights, regardless of the network topology. Moreover, the right eigenvectors are always localized if the degree distribution has diverging moments. The paper also shows that, in contrast to the common expectation, traditional random matrix theory fails in describing the eigenvector statistics even when the network is densely connected. This result is deeply related to a breakdown of the classical central limit theorem in random graph models.
Overall, their analysis sheds light on the relationship between graph topology and the localization of eigenvectors in directed random graphs. Therefore, Metz and Neri conclude that localization in directed random graphs is fundamentally different from localization in undirected graphs, for which degree fluctuations are always important.
The paper is available at https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.126.040604
Leave a Reply