CIF:Small: Towards Information Content of Dynamic Structures

Purdue University, West Lafayette IN

Investigators

Abstract

Brain networks, protein‐protein interactions, and social networks all build on basic ingredients of sets, trees, and graphs, yet a theory of information for such advanced dynamic data structures is lacking. Fundamental questions for such data structures include: What are the fundamental limits on storage and processing of structural and temporal information? What are the limits on the extraction of information from large biological databases? What are the fewest bits of an incomplete database needed to reliably answer a query? This project seeks to find answers to these questions and thus make headway in information theory for dynamic structures by finding efficient algorithms to appraise structural and temporal information – whether it is embodied in graphs of social networks, Markov fields of images, or protein tertiary structures. The specific goals of the project are as follows: 1) Finding fundamental limits of information content in a wide range of dynamic structures, including dynamic networks, Markov fields, and structurally complex channels such as Boltzmann’s channel; 2) Examining dynamic networks by: (a) Inferring underlying dynamic processes governing network evolution; (b) determining the minimum number of bits to describe dynamic networks; and (c) inferring spatial‐temporal properties such as node arrivals; 3) Understanding structural properties of large systems with local mutual dependencies, constraints, and interactions often described by Markov fields; 4) Analyzing flow of structural information over a noisy channel. Tools developed as part of the project will be used in areas such as characterization of biological and social networks, deciphering evolution of the human brain, development of a comprehensive formal model for misinformation, and designing a robust pervasive communications infrastructure. 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.