Li, Angsheng

Title: Structural Information Theory and Its Applications: Principles for Distinguishing Order from Disorder

Abstract: It had been a great challenge to measure the information embedded in a graph or physical system such that the structural information determines and decodes the essential structure or functional structure of the graph or physical system. Such a missing metric was regarded as a fundamental gap in the theoretical underpinnings of information science and computer science. Recently, Li and Pan introduced the notion of coding tree of a graph which encodes a large-scale graph by a tree such that a vertex of the graph is encoded by a leaf node of the tree, defined the notion of structural entropy of the graph given by a coding tree as the amount of information required to determine the tree codeword of the vertex that is accessible from random walk in the graph, and defined the structural entropy of the graph as the minimum amount of information required to determine the codeword of a coding tree for the vertex that is accessible from random walk in the graph. The structural entropy of a graph defined in this way is hence the information embedded in the graph that determines and decodes the coding tree of the graph that minimizes the uncertainty of the positioning of the graph. The new notions build a new theory, the structural information theory. The theory has enormous applications in a wide range of disciplines, including data processing, network analysis, network algorithms etc. In this talk, I will introduce the basics of the theory and a few representative applications.