Algebra & Combinatorics Seminar

Structural information theory

  • 演讲者:李昂生教授(中国科学院软件研究所)

  • 时间:2017-09-18 14:30-15:30

  • 地点:慧园3栋 415报告厅

Shannon's entropy is the measure of uncertainty of a probabilistic distribution. However it had been a longstanding challenge to define the information embedded in a physical system, allowing us to decode the essential structure of the system by excluding the perturbation by noises and random variations.  In this talk, I will introduce a new theory, the structural information theory, to resolve this challenge.  For a graph, we introduce the notion of priority tree coding of the graph, in which all the leaves of the priority tree are the codewords of the vertices of the graph, we define the structural information of the graph by a coding tree to be the number of bits required to determine the codeword (defined by the coding tree) of the vertex that is accessible from random walk in the graph. The structural information of the graph is defined as the minimum number of bits required to determine the codeword given by a coding tree of the vertex that is accessible from random walk in the graph.  The metric of structural information allows us to establish a new theory, that is, the structural information theory. The metric of structural information provides a principle to decode the essential structure of a noisy structures, with a wide range of applications. In this talk, I will introduce this new theory and its applications in network engineering.