SFI Mentors: Cris Moore and Pan Zhang
Abstract: 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 despite the existence of theoretically detectable community structure [1]. Krzakala et al. demonstrate in [1] that a novel operator|the so-called \nonbacktracking matrix" B|is in fact amenable to spectral clustering methods in where other operators fail. This project, in collaboration with Cris Moore and Pan Zhang, will explore yet another matrix, the \z-Laplacian" Lz = zA-D, which has been observed to share important spectral properties with B [2]. We hope build on prior work by Zhang, Moore, and Newman on Lz, in particular using techniques from the theory of random matrices to facilitate further analytic and numerical study of this matrix and it's use in community detection.
References
[1] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborova, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935{20940, 2013.
[2] Alaa Saade, Florent Krzakala, and Lenka Zdeborova. Spectral density of the non-backtracking operator. arXiv preprint arXiv:1404.7787, 2014.