CIF:Small: Towards Information Content of Dynamic Structures

大脑网络、蛋白质-蛋白质相互作用和社会网络都建立在集合、树和图的基本成分上，但缺乏用于这种高级动态数据结构的信息理论。这种数据结构的基本问题包括：结构和时间信息的存储和处理的基本限制是什么？从大型生物数据库中提取信息的限制是什么？要可靠地回答查询，一个不完整的数据库最少需要什么位？这个项目试图找到这些问题的答案，并通过找到有效的算法来评估结构和时间信息，从而在动态结构的信息论中取得进展。该项目的具体目标如下：1)在广泛的动态结构中找到信息内容的基本极限，包括动态网络、马尔可夫场和结构复杂的通道，如玻尔兹曼通道；2)通过以下方法检查动态网络：(A)推断控制网络演化的潜在动态过程；(B)确定描述动态网络的最小比特数；以及(C)推断诸如节点到达的时空特性；3)理解具有局部相互依赖、约束和通常由马尔可夫场描述的相互作用的大系统的结构特性；4)分析噪声信道上的结构信息流。作为项目的一部分，开发的工具将用于描述生物和社会网络的特征，破译人脑的进化，开发错误信息的全面正式模型，以及设计强大的普适通信基础设施。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.