CAREER: Information Propagation over Networks

通信、可靠计算、统计物理、计算生物学和机器学习领域中的各种问题都与大型网络中的信息传播有关。例如，在社交或通信网络环境中，重要的是了解哪些类型的网络在其代理相互嘈杂地通信时能够通过网络成功地传输信息。在皮下层面，一个共同的理论框架存在于许多这样的问题的核心，这些问题来自看似不同的领域。本项目研究源自网络的某些部分的信息在流经网络的其余部分时如何随时间消散。现有对这一现象的分析仅限于非常简单的网络结构和信息措施。因此，有必要对现有思想进行重大发展，以对上述应用领域中更复杂的问题进行建模和分析。这个项目旨在开发这样一个关于网络上信息传播和耗散的通用和基本理论，这反过来又将在其他几个应用领域提供见解。此外，该项目的研究活动还得到了协同教育部分以及学生辅导活动的补充。这个项目的研究被分成两个互补的推进。第一个推力的目标是描述信息传播可能的网络结构。为了实现这一点，将构建和分析信息传播可能的图表，并开发出证明何时不可能传播信息的一般技术。第二个重点的目标是发展对图上的信息收缩的基础理解。为了实现这一点，将建立和研究几类信息论不等式和相关的替代技术来捕捉信息收缩。从这些突击中得出的结果预计将在包括通信、计算、统计推理和机器学习在内的广泛学科中具有实用价值。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

A variety of problems in the domains of communications, reliable computation, statistical physics, computational biology, and machine learning are concerned with the propagation of information in large networks. For example, in a social or communication network setting, it is important to understand what kinds of networks enable successful transmission of information through the network when its agents noisily communicate with each other. At a subcutaneous level, a common theoretical framework resides at the heart of many such problems from seemingly disparate domains. This project investigates how information originating from certain parts of a network dissipates over time as it flows through the remainder of the network. Existing analyses of this phenomenon are limited to very simple network structures and measures of information. Thus, significant development of existing ideas is necessary to model and analyze more complex problems in the aforementioned application areas. This project aims to develop such a general and fundamental theory of information propagation and dissipation over networks, which would in turn provide insights in several other application domains. Furthermore, the research activities of this project are complemented by a synergistic educational component as well as student mentoring activities. The research in this project is split into two complementary thrusts. The objective of the first thrust is to characterize the structure of networks for which propagation of information is possible. To achieve this, graphs where information propagation is possible will be constructed and analyzed, and general techniques to prove when such propagation is impossible will be developed. The objective of the second thrust is to develop a foundational understanding of information contraction over graphs. To achieve this, classes of information theoretic inequalities and related alternative techniques to capture the contraction of information will be established and investigated. The results derived in these thrusts are anticipated to have utility in a wide range of disciplines including communications, computation, statistical inference, and machine learning.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.