Community Detection with the z-Laplacian

Community detection is a fundamental problem in network science, with broad applications across the biological and social arenas. A common approach is to leverage the spectral properties of an operator related to the network (most commonly the adjacency matrix or graph Laplacian), though there are regimes where these techniques are known to fail on sparse networks despite the existence of theoretically detectable community structure [3],[4]. This work introduces an operator we term the “z-Laplacian” L_z = zA – D, which has been observed to share important spectral properties with the non-backtracking matrix of [3],[6] and which we believe can find communities even in the sparse case. We augment tools from the theory of random matrices with message-passing and population dynamics approaches in order to study the spectrum of L_z.