Structural Information and Dynamical Complexity of Networks
The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index.
Abstract
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 HK(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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Current AI and robotics research often operates on a pair of related, flawed assumptions about complexity: (i) that human-similarity is a barometer for complexity, and (ii) that the complexity of an agent is essentially the complexity of its centralized information processing (its biological or artificial brain) Tononi et al. ( 1999); Li and Pan (2016); Sporns (2022).”
From Understanding Agent Complexity Through Affordances (2025) · cites this paper as Li and Pan (2016)
Citations
Cites
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · cited 3×
“For community detection, Newman and Girvan [42] had proposed the modularity maximisation principle.”
BackgroundMethodInfluentialFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 1×
“A standard null model assumes that the expected degree after averaging over all possible configurations matches the actual degree of the original graph [27].”
BackgroundDistinct types of diffuse large B-cell lymphoma identified by gene expression profiling
Alizadeh, A. A., Eisen, M. B., Davis, R. E., Ma, C., Lossos, I. S., Rosenwald, A., Boldrick, J. C., Sabet, H., Tran, T., Yu, X., et al. (2000) · Nature · doi:10.1038/35000501 · Cited by 9,925
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Darwin, C., Burndy Library, Darwin, C., Edmonds & Remnants, & Henry Sotheran Ltd. (1859) · J. Murray eBooks · doi:10.5962/bhl.title.59991 · Cited by 6,984
The Evolution of Random Graphs
(1986) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/062/06 · Cited by 5,543
Maps of random walks on complex networks reveal community structure
Rosvall, M., & Bergstrom, C. T. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0706851105 · Cited by 4,583
Research works printed but not linked: 3
- ?uczak, 1989, Sparse random graphs with a given degree sequence, Proc Symp Random Graphs, 165
- erdõs, 1959, On random graphs I, Publ Math Inst Hungar Acad Sci, 6, 290
- konstantinova, 1990, Sensitivity of topological indices of polycyclic graphs, Vych Sistemy, 136, 38
Cited by
Items 201–269 of 269
Understanding Agent Complexity Through Affordances
Baker, B., & Roberts, S. (2025) · Minds and Machines · doi:10.1007/s11023-025-09748-7
Towards Expressive Graph Neural Networks : Theory, Algorithms, and Applications
Dasoulas, G. (2022) · theses.fr (ABES) · doi:10.70675/a0be9cd5z52adz4d3dzbd4bz98d878f10255
Gök, M. (2026) · Knowledge-Based Systems · doi:10.1016/j.knosys.2026.116614
Further Exploration of the REM Model on Community Structure Deception
Liu, Y., Li, G., Yin, P., Ma, S., Ge, Y., Zhang, L., & He, J. (2025) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-031-97352-9_18
CG-MIA: A Causal Generalization framework for cross-domain graph Membership Inference Attack
Sui, P., Yang, L., Wei, Y., Liu, S., Shao, M., & Fu, X. (2026) · Knowledge-Based Systems · doi:10.1016/j.knosys.2026.117002
SEMA: A Structural Entropy Guided Multimodal Framework for Adversarial Face Attacks
Song, R., Tian, Y., Li, M., & Yang, Z. (2025) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom66490.2025.00155
Contributions to random walk based graph representation learning
Oluigbo, I. V. (2022) · theses.fr (ABES) · doi:10.70675/70939a44z6079z4e5cz9899z8434ac7a4bb3
Zhang, Y. W., Wang, M. B., & Li, S. C. (2021) · Figshare · doi:10.6084/m9.figshare.13642442
Zhang, Y. W., Wang, M. B., & Li, S. C. (2021) · Figshare · doi:10.6084/m9.figshare.13642439
Zhang, Y. W., Wang, M. B., & Li, S. C. (2021) · Figshare · doi:10.6084/m9.figshare.13642436
Zhang, Y. W., Wang, M. B., & Li, S. C. (2021) · Figshare · doi:10.6084/m9.figshare.13642433
Zhang, Y. W., Wang, M. B., & Li, S. C. (2021) · Figshare · doi:10.6084/m9.figshare.13642445
Which plays a key role in sampling-based large-scale GNNs, sampling or iteration?
Jiang, B., Dong, L., Peng, X., Chen, R., Liu, C., & Yao, H. L. (2025) · Neurocomputing · doi:10.1016/j.neucom.2025.132246
PatternInsight: An Online Approach to Complex Pattern Detection Over Mobile Data Streams
Wu, X. T., Ren, Y., Li, Z., Xu, F., Liu, Y., & Chen, G. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3636469
Structural Entropy-based Multivariate Time Series Forecasting
Li, X., Yue, K., Yu, L., & Yang, P. (2025) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3746252.3761007
Scientific X-ray.Preprint
Li, Q., Fu, L., Wang, X., & Zhou, C. (2021) · arXiv (Cornell University)
MemPulse: Memory Pulse-Driven Adaptive Long-Context Reasoning with Fact-based Hypergraph
Tao, W., Wang, Y., Lan, Y., & Yang, C. (2026) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/2026.findings-emnlp.947
Content-Preserving Speech Representation Learning Via Adaptive Segment-Level Alignment
Dong, L., Wang, W., Yu, Z., Xiang, Y., Xian, Y., & Huang, Y. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11462234
Reasoning Structure of Large Language ModelsPreprint
Berdoz, F., Lanzendörfer, L. A., Farestam, F., & Wattenhofer, R. P. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.03883
Gupta, A., Gorle, A. R., Rajesh, A., & Weissman, T. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.07209
A survey on adversarial attacks on community detection in complex networks
Lin, C., Shen, C. Q., Zhuoyan, Y. A. N. G., Yinghan, W. A. N. G., Wang, Q. H., Guan, X., & 管, 晓. (2026) · Scientia Sinica Informationis · doi:10.1360/ssi-2025-0354
Hierarchical graph structure learning with nonlinear information bottleneck
Sun, Q., Luo, J., Yang, B., & Li, J. (2024) · Scientia Sinica Informationis · doi:10.1360/ssi-2024-0049
Subnetwork Mining Based on Structure Entropy for Analyzing Depression Disease
Mu, J., Gao, Y., Zheng, W., Yu, Q., & Huang, T. (2023) · IEEE International Conference on Medical Artificial Intelligence (MedAI) · doi:10.1109/medai59581.2023.00030
Geometric Spread Routing for Security-Oriented Communication in Mega LEO Constellations
Liu, Z., Wang, S., Pan, G., Miao, X., & Krikidis, I. (2026) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2026.3729354
DocMaster: A Hierarchical Structure-Aware System for Document AnalysisPreprint
Chen, Z., Zhou, Y., Zhang, F., Xu, Q., Yang, C., & Fang, Y. D. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.08539
Structural entropy guided hyperbolic graph transformer for graph partitioning
Yang, Z., Niu, L., & Lei, M. (2026) · Applied Soft Computing · doi:10.1016/j.asoc.2026.116367
HGDL: Holistic Graph Distribution Learner for High-Fidelity Small Graph Generation
Wang, H., Wang, Z., Yan, X., & Sun, M. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-31438-3_7
Self-Evolving Multi-Agent Framework for Efficient Decision Making in Real-Time Strategy ScenariosPreprint
Ma, L., Peng, H., Wang, Y., Luo, H., Liu, J., Gu, K., Wu, G., Lin, H., & Ren, L. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2603.23875
Identification of Topologically Associated Domains via Infomap Entropy Minimization
Liang, Q., Zhao, S., Wang, R. H., Zhang, Y. W., Chen, L., & Li, S. C. (2026) · Journal of Computational Biology · doi:10.1177/15578666261491762
SED: Structural Entropy Based Speech Discretization for Discrete Token-Based ASR
Dong, L., Wang, W., Xiang, Y., Xian, Y., & Gao, S. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11461907
Spatial Entropy based Partitioning for Spatiotemporal Graph Unlearning
Guo, Q., Sun, W., Wang, Y., & Wang, W. (2026) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611979329.27
Adaptive Consistency Graph for Long-Horizon AgentsPreprint
Wang, J., Peng, H., & Wang, Z. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.32754
Graph Augmentation and Community-Aware Social Bot Detection via Structural Entropy
Wang, W., Zeng, X., Liu, Z., & Zang, T. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-7195-5_19
Structural entropy based graph contrastive learning for node classification
Zhang, J., Duan, L., Chen, X., Li, X., Chai, J., & Yue, K. (2025) · Intelligent Data Analysis · doi:10.1177/1088467x251395501
A New Method for 3-Satisfiability Problem Phase Transition on Structural Entropy
Lin, Q., Wang, X., & Niu, J. (2020) · IEEE Access · doi:10.1109/access.2020.3047930
Structural Mutual Information and Its Application.Preprint
Tian, Y., Zhang, Z., Xiong, J., & Ma, J. (2021) · IACR Cryptology ePrint Archive
Multilinear Control Systems Theory and its Applications
Chen, C. (2021) · Deep Blue (University of Michigan) · doi:10.7302/3013
Scientific X-rayPreprint
Li, Q., Wang, X., Fu, L., & Zhou, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.03458
A Clustering Method with Graph Maximum Decoding Information
Xu, X., Lv, M., Lian, Z., Wu, Y., Jin, Y., Jiang, S., & Ding, Z. (2024) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn60899.2024.10650698
An Improved Privacy Control Scheme for Contract Algorithm Based on Structure Entropy
Wang, D., & Hu, Z. (2024) · doi:10.1145/3686490.3686534
SCHENO: Measuring Schema vs. Noise in Graphs
Hibshman, J., Hoq, A., & Weninger, T. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3543032
GEME In Government Data Governance: Graph Entropy And Attention Coordination Mechanism
Zhou, H., Zhu, J., Bao, S., & Zuo, E. (2025) · International Conference on Innovation Management and Information Systems (ICIMIS) · doi:10.1145/3745676.3745744
Dong, F. (2025) · International Conference on Intelligent Computing (ICIC) · doi:10.65286/icic.v21i2.23635
Structural Entropy Based Hierarchical Relation ExtractionPreprint
Huang, Z., Yue, K., Tang, Z., & Wang, J. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5788037
Hierarchical Superpixel Segmentation via Structural Information TheoryPreprint
Xie, M., Peng, H., Li, P., Zeng, G., Wang, S., Wu, J., Li, P., & Yu, P. S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2501.07069
Peng, K., Cao, C., Peng, H., Hao, Z., Jiang, L., Gu, K., Liu, Y., & Yu, P. S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2508.05023
Knowledge-based Graph Privacy Preservation via Structure EntropyPreprint
Yang, Z., Tian, Y., Niu, K., Li, M., Song, R., Xiong, J., & Ma, J. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6189624
Label-Free Contrastive Learning for Open-World Multimodal Social Event Detection
Yang, Z., Qin, H., Peng, H., Yu, X., Sun, L., & Jiang, L. (2026) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3773966.3777919
Personalized Privacy-Preserving Graph Neural Network Based on Community Awareness
Du, S., Tang, J., & Dang, S. (2026) · IEEE Internet of Things Journal · doi:10.1109/jiot.2026.3668140
Learning to Explore: Policy-Guided Outlier Synthesis for Graph Out-of-Distribution Detection
Sun, L., Yang, L., Tian, J., Fang, B., Yu, X., Ye, J., Tang, P., Peng, H., & Yu, P. S. (2026) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v40i30.39768
SE-GCL: Structure-Aware Graph Clustering with Entropy MinimizationPreprint
Xu, G., Zhang, X., Wang, L., Liu, J., Tang, H., Li, C., & Ouyang, Z. (2026) · Research Square · doi:10.21203/rs.3.rs-9158379/v1
Topology-Independent Strategy for Evaluating Routing Stability in MANETs
Li, J., Xia, Y., Su, J., & Song, C. (2026) · International Conference on Communications, Information System and Computer Engineering (CISCE) · doi:10.1109/cisce69494.2026.11504806
Rethinking Generalization in Graph Neural Networks: A Structural Complexity PerspectivePreprint
Wang, P., Bai, L., Yang, X., Xu, R. Y. D., & Liang, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.13597
Li, K., Jin, Y., Li, G., Wang, T., Lu, G., & Zuo, M. (2026) · Measurement · doi:10.1016/j.measurement.2026.121878
Zhao, X., Hu, Y., Luo, J., Sun, Q., & Li, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.28630
Multilevel Attacks on Community Detection: From Global Deception to Individual Evasion
Madi, S. A., & Pirrò, G. (2026) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2026.3702260
Comprehensive, Efficient Large-Scale Community Detection via Structural Entropy GamePreprint
Li, P., Xian, Y., Peng, H. H., Li, H., Yu, Z., Xiang, Y., & Yu, P. S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.13713
Multi-granularity Anomaly Detection via Attribute Subset Sequences Based on Fuzzy Entropy
Qing, C., Li, Y., Yuan, T., Zhao, J., Li, X., & Wan, J. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-30228-1_13
Accelerating MILP solving through bipartite GNN-based embeddings
Liang, T., Wu, X., Huang, J., & Feng, Q. (2026) · Expert Systems with Applications · doi:10.1016/j.eswa.2026.133717
Liu, R., & Yu, J. (2026) · International Conference on Computer Intelligence and Software Engineering (CICSE) · doi:10.1109/cicse70286.2026.11620972
Structural Security Entropy: A Novel Prior for Robust GNN-Based Security Assessment of Netlists
Karn, R. R., Knechtel, J., & Sinanoglu, O. (2026) · IEEE International On-Line Testing Symposium (IOLTS) · doi:10.1109/iolts69666.2026.11633870
Hybrid Graph Node Learning Network for Marine Radar Target Detection
Zhu, Y., Ren, H., Wang, Y., Zhou, Y., Zou, L., & Wang, X. (2026) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2026.3732287
Qv, D., Liu, P., Wang, J., Jiayi, W., & Cheng, L. (2026) · Energy · doi:10.1016/j.energy.2026.142345
Structural-Entropy-Based Speaker Diarization with Unknown Number of Speakers
Wang, Z., Dong, L., Wang, W., Xiang, Y., Gao, S., & Yu, Z. (2026) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn69854.2026.11730046
Alignment Entropy via Planar Cut Operators: Localizing Structural Uncertainty in Embedded Graphs
Fried, M. (2026) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn69854.2026.11729961
Su, D., Peng, H., Pan, Y., & Li, A. (2026) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3799682.3840913
Self-citation
Metadata
- Authors
- Li, A., & Pan, Y.
- Affiliations
- Chinese Academy of Sciences (CN)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2016-06
- Volume
- 62
- Issue
- 6
- Pages
- 3290-3339
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2338678442
- Cited by
- 200
- References
- 51
- Citations by year
- 2026: 36 · 2025: 51 · 2024: 32 · 2023: 23 · 2022: 17 · 2021: 22 · 2020: 5 · 2019: 5 · 2018: 6 · 2017: 2 · 2016: 1
- FWCI
- 2.61
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- Funders
- Hundred Talent Program of Chinese Academy of Sciences
- China Basic Research Program (973) (2014CB340302)
- Institute of Software, Chinese Academy of Sciences through the Grand Project entitled Network Algorithms and Digital Information
- National Natural Science Foundation of China (61161130530)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Systems and Dynamics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- structural information, structure entropy, random walks on graphs, noisy data, search engines, network evolution
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.