Small: New Directions in Community Detection

Northwestern University, Evanston IL

Investigators

Abstract

Community detection is the problem of identifying community structure in a network. With applications to fields such as biology, sociology, telecommunications, and transportation, community detection is an important question in network science. Community detection is a well-studied problem in probability, statistics, and theoretical computer science, where the network is typically assumed to be random. While there has been much research on community detection in random networks, the standard probabilistic model is too restrictive to model many network-science applications and cannot effectively capture certain features of real-world networks: higher order interactions, overlapping communities, and hierarchical structure. The project will advance the understanding of network science and network inference, by studying richer, more expressive, and realistic formulations of community detection that move beyond the standard Stochastic Block Model (SBM). Broad goals include community detection in the hypergraph generalization of the SBM, using tensor methods to find overlapping communities in hypergraphs, recovering hierarchical community structure, and understanding the capabilities and limits of simple spectral algorithms for many community-detection problems. Tackling the above questions will involve developing new mathematical and algorithmic techniques related to random matrices and random tensors, and bringing them to bear upon problems in community detection. The project will involve graduate student training and co-mentorship by the PIs across computer science and mathematics, as well as outreach to middle- and high-school students. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.