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.