Volume 107, Number 5, September 2014
|Number of page(s)||6|
|Published online||04 September 2014|
Spectral density of the non-backtracking operator on random graphs
1 Laboratoire de Physique Statistique, CNRS UMR 8550, Université P. et M. Curie Paris 6 et École Normale Supérieure - 24, rue Lhomond, 75005 Paris, France
2 ESPCI and CNRS UMR 7083 Gulliver - 10 rue Vauquelin, 75005 Paris, France
3 Institut de Physique Théorique, IPhT, CEA Saclay and URA 2306, CNRS - Orme des Merisiers, 91191 Gif-sur-Yvette, France
Received: 5 May 2014
Accepted: 12 August 2014
The non-backtracking operator was recently shown to provide a significant improvement when used for spectral clustering of sparse networks. In this paper we analyze its spectral density on large random sparse graphs using a mapping to the correlation functions of a certain interacting quantum disordered system on the graph. On sparse, tree-like graphs, this can be solved efficiently by the cavity method and a belief propagation algorithm. We show that there exists a paramagnetic phase, leading to zero spectral density, that is stable outside a circle of radius , where ρ is the leading eigenvalue of the non-backtracking operator. We observe a second-order phase transition at the edge of this circle, between a zero and a non-zero spectral density. The fact that this phase transition is absent in the spectral density of other matrices commonly used for spectral clustering provides a physical justification of the performances of the non-backtracking operator in spectral clustering.
PACS: 02.10.Yn – Matrix theory / 89.75.Hc – Networks and genealogical trees / 89.20.-a – Interdisciplinary applications of physics
© EPLA, 2014
Initial download of the metrics may take a while.