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

这个项目的主要目标是建立社区检测的基本界限。在几乎所有处理网络和大数据集的应用中，人们希望提取相似的数据点的子组，即社区。虽然社区检测技术每天都在扩大，并取得了实际的成功，但相对较少地关注基本限制，从而关注当前的算法所处的位置。通过建立社区检测的基本限制，该项目为社区检测算法提供了一种新的方式，并在一个突出的领域扩展了信息理论，在这个领域它可以自然地蓬勃发展。该项目将使用来自社会和生物网络的真实数据集。特别是，它开发了一种在Hi-C基因组数据中提取群落的新倡议，有助于揭示DNA的3D折叠结构。该项目将特别关注随机块模型，这是一种用于群落检测的规范模型。研究者的最新工作利用信息论，给出了随机分块模型精确恢复的第一个充要条件，并给出了一个达到极限的有效算法。这为社区检测打开了一扇新的大门，它是在这个项目中通过将社区检测描述为非正统的差错控制编码问题来开发的。在这种情况下，新类型的f-发散有望发挥关键作用，类似于香农信道编码定理中的Kullback-Leibler发散，而其他较弱的恢复要求可能依赖于非正统广播问题、图熵不等和信息估计问题。这使得社区检测的研究成为连接信息论、机器学习和网络的一个丰富的领域；较少关注遍历结果；更多地与图论和谱分析交织在一起。特别是，这个项目将展示如何在图形通道的新颖和统一的主题下研究这些问题以及更一般的低阶近似问题。

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.