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

职业：社区检测和图形通道的信息论基础

• 批准号: 1552131
• 负责人: Emmanuel Abbe
• 金额: $ 50万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-02-15 至 2022-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1552131&HistoricalAwards=false
• 关键词: CAREER; Information; Theoretic; Foundations; Community

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.

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