Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Non-backtracking spectra of weighted inhomogeneous random graphs

Ludovic Stephan 1, 2, * Laurent Massoulié 1, 3
* Corresponding author
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : We study a model of random graphs where each edge is drawn independently (but not necessarily identically distributed) from the others, and then assigned a random weight. When the mean degree of such a graph is low, it is known that the spectrum of the adjacency matrix $A$ deviates significantly from that of its expected value $\mathbb E A$. In contrast, we show that over a wide range of parameters the top eigenvalues of the non-backtracking matrix $B$ -- a matrix whose powers count the non-backtracking walks between two edges -- are close to those of $\mathbb E A$, and all other eigenvalues are confined in a bulk with known radius. We also obtain a precise characterization of the scalar product between the eigenvectors of $B$ and their deterministic counterparts derived from the model parameters. This result has many applications, in domains ranging from (noisy) matrix completion to community detection, as well as matrix perturbation theory. In particular, we establish as a corollary that a result known as the Baik-Ben Arous-P\'ech\'e phase transition, previously established only for rotationally invariant random matrices, holds more generally for matrices $A$ as above under a mild concentration hypothesis.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Ludovic Stephan Connect in order to contact the contributor
Submitted on : Monday, February 15, 2021 - 9:47:42 AM
Last modification on : Friday, January 21, 2022 - 3:19:28 AM
Long-term archiving on: : Sunday, May 16, 2021 - 6:04:46 PM


Files produced by the author(s)


  • HAL Id : hal-03140329, version 1
  • ARXIV : 2004.07408


Ludovic Stephan, Laurent Massoulié. Non-backtracking spectra of weighted inhomogeneous random graphs. 2021. ⟨hal-03140329⟩



Les métriques sont temporairement indisponibles