CAREER: Information Propagation over Networks

通信、可靠计算、统计物理、计算生物学和机器学习领域的各种问题都与大型网络中的信息传播有关。例如，在社交网络或通信网络设置中，当其代理相互之间嘈杂地通信时，了解哪些类型的网络能够通过网络成功地传输信息是很重要的。在皮下水平，一个共同的理论框架驻留在许多这样的问题的核心，从看似不同的领域。这个项目调查了来自网络某些部分的信息在流经网络其余部分的过程中如何随着时间的推移而消散。对这一现象的现有分析仅限于非常简单的网络结构和信息度量。因此，有必要对现有思想进行重大发展，以模拟和分析上述应用领域中更复杂的问题。这个项目旨在发展这样一个信息在网络上传播和消散的一般和基本理论，这将反过来为其他几个应用领域提供见解。此外，该项目的研究活动还得到了协同教育部分和学生指导活动的补充。这个项目的研究分为两个互补的方向。第一个要点的目标是描述可能传播信息的网络结构。为了实现这一点，将构建和分析可能传播信息的图，并开发证明不可能传播信息的一般技术。第二个要点的目标是发展对图上信息收缩的基本理解。为了实现这一目标，信息论不等式的类别和相关的替代技术来捕获信息的收缩将被建立和研究。预计这些研究成果将在通信、计算、统计推断和机器学习等广泛学科中得到应用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.