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

该项目的主要目标是确定社区检测的基本限度。在处理网络和大数据集的几乎所有应用中，人们希望提取相似的数据点的子组，即，社区.虽然社区检测技术正在扩大每天与实际的成功，相对较少的关注已经支付的基本限制，因此，目前的算法stand. By建立社区检测的基本限制，该项目提供了一个新的社区检测算法，并扩展信息理论在一个突出的领域，它可以自然蓬勃发展。该项目将使用来自社会和生物网络的真实的数据集。特别是，它开发了一个新的倡议，以提取社区在Hi-C基因组数据，有助于揭示DNA的三维折叠结构.该项目将特别关注随机块模型，社区检测的一个典型模型.研究人员最近的工作利用信息论提供了第一个必要和充分条件，在随机块模型的精确恢复，并实现了限制的有效算法。这打开了一个新的视角社区检测，这是在这个项目中开发的铸造社区检测作为非正统的错误控制编码问题。在这种情况下，新类型的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.