Advances in Network Complexity -- Contents -- Preface -- List of Contributors -- 1 Functional Complexity Based on Topology -- 1.1 Introduction -- 1.2 A Measure for the Functional Complexity of Networks -- 1.2.1 Topological Equivalence of LCE-Graphs -- 1.2.2 Vertex Resolution Patterns -- 1.2.3 Kauffman States for Link Invariants -- 1.2.4 Definition of the Complexity Measure -- 1.3 Applications -- 1.3.1 Creation of a Loop -- 1.3.2 Networks of Information -- 1.3.3 Transport Networks of Cargo -- 1.3.4 Boolean Networks of Gene Regulation -- 1.3.5 Topological Quantum Systems -- 1.3.6 Steering Dynamics Stored in Knots and Links -- 1.4 Conclusions -- References -- 2 Connections Between Artificial Intelligence and Computational Complexity and the Complexity of Graphs -- 2.1 Introduction -- 2.2 Representation Methods -- 2.3 Searching Methods -- 2.4 Turing Machines -- 2.5 Fuzzy Logic and Fuzzy Graphs -- 2.6 Fuzzy Optimization -- 2.7 Fuzzy Systems -- 2.8 Problems Related to AI -- 2.9 Topology of Complex Networks -- 2.10 Hierarchies -- 2.10.1 Deterministic Case -- 2.10.2 Nondeterministic Case -- 2.10.3 Alternating Case -- 2.11 Graph Entropy -- 2.12 Kolmogorov Complexity -- 2.13 Conclusion -- References -- 3 Selection-Based Estimates of Complexity Unravel Some Mechanisms and Selective Pressures Underlying the Evolution of Complexity in Artificial Networks -- 3.1 Introduction -- 3.2 Complexity and Evolution -- 3.3 Macroscopic Quantification of Organismal Complexity -- 3.4 Selection-Based Methods of Complexity -- 3.5 Informational Complexity -- 3.6 Fisher Geometric Model -- 3.7 The Cost of Complexity -- 3.8 Quantifying Phenotypic Complexity -- 3.8.1 Mutation-Based Method: Mutational Phenotypic Complexity (MPC) -- 3.8.2 Drift Load Based Method: Effective Phenotypic Complexity (EPC) -- 3.8.3 Statistical Method: Principal Component Phenotypic Complexity (PCPC).

3.9 Darwinian Adaptive Neural Networks (DANN) -- 3.10 The Different Facets of Complexity -- 3.11 Mechanistic Understanding of Phenotypic Complexity -- 3.12 Selective Pressures Acting on Phenotypic Complexity -- 3.13 Conclusion and Perspectives -- References -- 4 Three Types of Network Complexity Pyramid -- 4.1 Introduction -- 4.2 The First Type: The Life's Complexity Pyramid (LCP) -- 4.3 The Second Type: Network Model Complexity Pyramid -- 4.3.1 The Level-7: Euler (Regular) Graphs -- 4.3.2 The Level-6: Erd€os-R enyi Random Graph -- 4.3.3 The Level-5: Small-World Network and Scale-Free Models -- 4.3.4 The Level-4: Weighted Evolving Network Models -- 4.3.5 The Bottom Three Levels of the NMCP -- 4.3.5.1 The Level-3: The HUHPNM -- 4.3.5.2 The Level-2: The LUHNM -- 4.3.5.3 The Level-1: The LUHNM-VSG -- 4.4 The Third Type: Generalized Farey Organized Network Pyramid -- 4.4.1 Construction Method of the Generalized Farey Tree Network (GFTN) -- 4.4.2 Main Results of the GFTN -- 4.4.2.1 Degree Distribution -- 4.4.2.2 Clustering Coefficient -- 4.4.2.3 Diameter and Small World -- 4.4.2.4 Degree-Degree Correlations -- 4.4.3 Weighted Property of GFTN -- 4.4.4 Generalized Farey Organized Network Pyramid (GFONP) -- 4.4.4.1 Methods -- 4.4.4.2 Main Results of GFONP -- 4.4.4.3 Brief Summary -- 4.5 Main Conclusions -- Acknowledgment -- References -- 5 Computational Complexity of Graphs -- 5.1 Introduction -- 5.2 Star Complexity of Graphs -- 5.2.1 Star Complexity of Almost All Graphs -- 5.2.2 Star Complexity and Biclique Coverings -- 5.3 From Graphs to Boolean Functions -- 5.3.1 Proof of the Strong Magnification Lemma -- 5.3.2 Toward the (2 + c)n Lower Bound -- 5.4 Formula Complexity of Graphs -- 5.5 Lower Bounds via Graph Entropy -- 5.5.1 Star Complexity and Affine Dimension of Graphs -- 5.6 Depth-2 Complexity -- 5.6.1 Depth-2 with AND on the Top.

5.6.2 Depth-2 with XOR on the Top -- 5.6.3 Depth-2 with Symmetric Top Gates -- 5.6.4 Weight of Symmetric Depth-2 Representations -- 5.7 Depth-3 Complexity -- 5.7.1 Depth-3 Complexity with XOR Bottom Gates -- 5.8 Network Complexity of Graphs -- 5.8.1 Realizing Graphs by Circuits -- 5.9 Conclusion and Open Problems -- References -- 6 The Linear Complexity of a Graph -- 6.1 Rationale and Approach -- 6.2 Background -- 6.2.1 Adjacency Matrices -- 6.2.2 Linear Complexity of a Matrix -- 6.2.3 Linear Complexity of a Graph -- 6.2.4 Reduced Version of a Matrix -- 6.3 An Exploration of Irreducible Graphs -- 6.3.1 Uniqueness and Prevalence -- 6.3.2 Structural Characteristics of the Irreducible Subgraph -- 6.4 Bounds on the Linear Complexity of Graphs -- 6.4.1 Naive Bounds -- 6.4.2 Bounds from Partitioning Edge Sets -- 6.4.3 Bounds for Direct Products of Graphs -- 6.5 Some Families of Graphs -- 6.5.1 Trees -- 6.5.2 Cycles -- 6.5.3 Complete Graphs -- 6.5.4 Complete k-partitite Graphs -- 6.5.5 Johnson Graphs -- 6.5.6 Hamming Graphs -- 6.6 Bounds for Graphs in General -- 6.6.1 Clique Partitions -- 6.7 Conclusion -- References -- 7 Kirchhoff's Matrix-Tree Theorem Revisited: Counting Spanning Trees with the Quantum Relative Entropy -- 7.1 Introduction -- 7.2 Main Result -- 7.3 Bounds -- 7.4 Conclusions -- Acknowledgments -- References -- 8 Dimension Measure for Complex Networks -- 8.1 Introduction -- 8.2 Volume Dimension -- 8.3 Complex Network Zeta Function and Relation to Kolmogorov Complexity -- 8.4 Comparison with Complexity Classes -- 8.5 Node-Based Definition -- 8.6 Linguistic-Analysis Application -- 8.7 Statistical Mechanics Application -- 8.8 Function Values -- 8.8.1 Discrete Regular Lattice -- 8.8.2 Random Graph -- 8.8.3 Scale-Free Network and Fractal Branching Tree -- 8.9 Other Work on Complexity Measures -- 8.9.1 Early Measures of Complexity.

8.9.2 Box Counting Dimension -- 8.9.3 Metric Dimension -- 8.10 Conclusion -- References -- 9 Information-Based Complexity of Networks -- 9.1 Introduction -- 9.2 History and Concept of Information-Based Complexity -- 9.3 Mutual Information -- 9.4 Graph Theory, and Graph Theoretic Measures: Cyclomatic Number, Spanning Trees -- 9.5 Erdos-Renyi Random Graphs, Small World Networks, Scale-free Networks -- 9.6 Graph Entropy -- 9.7 Information-Based Complexity of Unweighted, Unlabeled, and Undirected Networks -- 9.8 Motif Expansion -- 9.9 Labeled Networks -- 9.10 Weighted Networks -- 9.11 Empirical Results of Real Network Data, and Arti.cially Generated Networks -- 9.12 Extension to Processes on Networks -- 9.13 Transfer Entropy -- 9.14 Medium Articulation -- 9.15 Conclusion -- References -- 10 Thermodynamic Depth in Undirected and Directed Networks -- 10.1 Introduction -- 10.2 Polytopal vs Heat Flow Complexity -- 10.3 Characterization of Polytopal and Flow Complexity -- 10.3.1 Characterization of Phase Transition -- 10.4 The Laplacian of a Directed Graph -- 10.5 Directed Heat Kernels and Heat Flow -- 10.6 Heat Flow-Thermodynamic Depth Complexity -- 10.6.1 Definitions for Undirected Graphs -- 10.6.2 Extension for Digraphs -- 10.7 Experimental Results -- 10.7.1 Undirected graphs: Complexity of 3D Shapes -- 10.7.2 Directed Graphs: Complexity of Human Languages -- 10.8 Conclusions and Future Work -- Acknowledgments -- References -- 11 Circumscribed Complexity in Ecological Networks -- 11.1 A New Metaphor -- 11.2 Entropy as a Descriptor of Structure -- 11.3 Addressing Both Topology and Magnitude -- 11.4 Amalgamating Topology with Magnitudes -- 11.5 Effective Network Attributes -- 11.6 Limits to Complexity -- 11.7 An Example Ecosystem Network -- 11.8 A New Window on Complex Dynamics -- References.

12 Metros as Biological Systems: Complexity in Small Real-life Networks -- 12.1 Introduction -- 12.2 Methodology -- 12.3 Interpreting Complexity -- 12.3.1 Numerically -- 12.3.1.1 Scale-free -- 12.3.1.2 Small World -- 12.3.1.3 Impacts of Complexity -- 12.3.2 Graphically -- 12.4 Network Centrality -- 12.4.1 Centrality Indicators -- 12.4.1.1 Degree Centrality -- 12.4.1.2 Closeness Centrality -- 12.4.1.3 Betweenness Centrality -- 12.4.2 Network Centrality of Metro Networks -- 12.4.2.1 Degree Centrality -- 12.4.2.2 Closeness Centrality -- 12.4.2.3 Betweenness Centrality -- 12.5 Conclusion -- References -- Index.