The spectral density of dense random networks and the breakdown of the Wigner semicircle law of random matrix theory

The theory of random networks is useful in modelling systems of many interacting units, ranging from neurons in the brain and computers and routers in the Internet to species in an ecosystem. In this theory, a key mathematical quantity is the eigenvalue spectrum of the adjacency matrix, the entries of which reflect the connections between different network elements. The eigenvalue spectrum controls the dynamical behaviour of many processes occurring on a network, so understanding how network architecture influences this spectrum is a natural focus of considerable research.

One network model of special interest – known as the configuration model – allows researchers to freely adjust the degree distribution of the network, while maintaining an entirely random pattern of network connections. The degree of a network element counts the number of links attached to it. In a notable work, LML External Isaac Pérez Castillo, along with collaborators, established a set of exact equations determining the eigenvalue distribution of the configuration model. This result provides a starting point to study how the nature of degree fluctuations influences network spectra. So far, these equations can be solved analytically only in the so-called dense limit, when the average degree becomes infinitely large, and the random network effectively becomes fully connected. Previous works have shown that the eigenvalues of dense networks follow the Wigner semicircle law of random matrix theory, and it is widely believed that this result is universal, i.e., the details of the network structure are irrelevant to the dense limit.

However, all results for the spectra of dense networks are limited to models with weak degree fluctuations. Little is known about the role of degree fluctuations in the dense limit and the universal character of the semicircle distribution. In a new paper, LML External Fellow Fernando Metz addresses this question in a work with Jeferson Silva of the Federal University of Rio Grande do Sul in Porto Alegre, Brazil. Focussing on the dense limit of the eigenvalue distribution of networks, they consider four different examples in which the degree variance scales differently with the average degree. In general, their results show that, in the dense limit, the eigenvalue distribution is determined by the degree fluctuations, and the standard Wigner result breaks down if the degree fluctuations are strong enough. In one case – for dense random graphs with an exponential degree distribution – they find a surprising logarithmic divergence in the spectral density and the absence of sharp spectral edges. In other words, the eigenvalue distribution has support on the entire real line, in sharp contrast to the Wigner law of random matrix theory. Based on an exact calculation, the authors also establish a sufficient condition for the breakdown of the Wigner law.

The LML provided financial support for Jeferson Silva by funding a scientific initiation scholarship.

His paper is available at https://arxiv.org/pdf/2007.15155.pdf

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *