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.