CAREER:Information-Theoretic Foundations of Community Detection and Graphical Channels

Princeton University, Princeton NJ

Investigators

Abstract

The main goal of this project is to establish the fundamental limits of community detection. In virtually all applications dealing with networks and large data sets, one wishes to extract sub-groups of data points that are similar, i.e., communities. While community detection techniques are expanding daily with practical successes, relatively less attention has been paid to the fundamental limits, and consequently to where current algorithms stand. By establishing the fundamental limits of community detection, this project offers a novel take on community detection algorithms, and expands information theory in a prominent area where it can naturally flourish. The project will work with real data sets from social and biological networks. In particular, it develops a new initiative to extract communities in Hi-C genomic data, contributing to unveil the 3D folding structure of DNA. The project will focus in particular on the stochastic block model, a canonical model for community detection. The investigator's recent work leverages information theory to provide the first necessary and sufficient conditions for exact recovery in the stochastic block model, and an efficient algorithm achieving the limit. This opens the door to a new perspective on community detection, which is developed in this project by casting community detection as unorthodox error-control coding problems. In this context, new types of f-divergences are expected to play a key role, analogous to the Kullback-Leibler divergence in Shannon's channel coding theorem, while other weaker recovery requirements may rely on unorthodox broadcasting problems, graph entropic inequalities, and information-estimation problems. This makes the study of community detection a rich area connecting information theory, machine learning and networks; less focused on ergodic results; and more interlaced with graph theory and spectral analysis. In particular, this project will show how these problems, as well as more general low-rank approximation problems, can be studied under the novel and unifying theme of graphical channels.