Structural Information and Dynamical Complexity of Networks
文献类型：期刊论文
| 作者 | Li, AS ; Pan, YC |
| 刊名 | IEEE TRANSACTIONS ON INFORMATION THEORY
 |
| 出版日期 | 2016 |
| 卷号 | 62期号:6页码:3290-3339 |
| 关键词 | Shannon entropy structural information dynamical complexity of networks graph characterisation networks |
| ISSN号 | 0018-9448 |
| 中文摘要 | In 1953, Shannon proposed the question of quantification of structural information to analyze communication systems. The question has become one of the longest great challenges in information science and computer science. Here, we propose the first metric for structural information. Given a graph G, we define the K-dimensional structural information of G (or structure entropy of G), denoted by H-K (G), to be the minimum overall number of bits required to determine the K-dimensional code of the node that is accessible from random walk in G. The K-dimensional structural information provides the principle for completely detecting the natural or true structure, which consists of the rules, regulations, and orders of the graphs, for fully distinguishing the order from disorder in structured noisy data, and for analyzing communication systems, solving the Shannon's problem and opening up new directions. The K-dimensional structural information is also the first metric of dynamical complexity of networks, measuring the complexity of interactions, communications, operations, and even evolution of networks. The metric satisfies a number of fundamental properties, including additivity, locality, robustness, local and incremental computability, and so on. We establish the fundamental theorems of the one-and two-dimensional structural information of networks, including both lower and upper bounds of the metrics of classic data structures, general graphs, the networks of models, and the networks of natural evolution. We propose algorithms to approximate the K-dimensional structural information of graphs by finding the K-dimensional structure of the graphs that minimizes the K-dimensional structure entropy. We find that the K-dimensional structure entropy minimization is the principle for detecting the natural or true structures in real-world networks. Consequently, our structural information provides the foundation for knowledge discovering from noisy data. We establish a black hole principle by using the two-dimensional structure information of graphs. We propose the natural rank of locally listing algorithms by the structure entropy minimization principle, providing the basis for a next-generation search engine. |
| 英文摘要 | In 1953, Shannon proposed the question of quantification of structural information to analyze communication systems. The question has become one of the longest great challenges in information science and computer science. Here, we propose the first metric for structural information. Given a graph G, we define the K-dimensional structural information of G (or structure entropy of G), denoted by H-K (G), to be the minimum overall number of bits required to determine the K-dimensional code of the node that is accessible from random walk in G. The K-dimensional structural information provides the principle for completely detecting the natural or true structure, which consists of the rules, regulations, and orders of the graphs, for fully distinguishing the order from disorder in structured noisy data, and for analyzing communication systems, solving the Shannon's problem and opening up new directions. The K-dimensional structural information is also the first metric of dynamical complexity of networks, measuring the complexity of interactions, communications, operations, and even evolution of networks. The metric satisfies a number of fundamental properties, including additivity, locality, robustness, local and incremental computability, and so on. We establish the fundamental theorems of the one-and two-dimensional structural information of networks, including both lower and upper bounds of the metrics of classic data structures, general graphs, the networks of models, and the networks of natural evolution. We propose algorithms to approximate the K-dimensional structural information of graphs by finding the K-dimensional structure of the graphs that minimizes the K-dimensional structure entropy. We find that the K-dimensional structure entropy minimization is the principle for detecting the natural or true structures in real-world networks. Consequently, our structural information provides the foundation for knowledge discovering from noisy data. We establish a black hole principle by using the two-dimensional structure information of graphs. We propose the natural rank of locally listing algorithms by the structure entropy minimization principle, providing the basis for a next-generation search engine. |
| 收录类别 | SCI |
| 语种 | 英语 |
| WOS记录号 | WOS:000380070600022 |
| 公开日期 | 2016-12-09 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/17329]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Li, AS,Pan, YC. Structural Information and Dynamical Complexity of Networks[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2016,62(6):3290-3339. |
| APA | Li, AS,&Pan, YC.(2016).Structural Information and Dynamical Complexity of Networks.IEEE TRANSACTIONS ON INFORMATION THEORY,62(6),3290-3339. |
| MLA | Li, AS,et al."Structural Information and Dynamical Complexity of Networks".IEEE TRANSACTIONS ON INFORMATION THEORY 62.6(2016):3290-3339. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。