Advances in Network Complexity: (Quantitative and Network Biology)

A well-balanced overview of mathematical approaches to describe complex systems, ranging from chemical reactions to gene regulation networks, from ecological systems to examples from social sciences. Matthias Dehmer and Abbe Mowshowitz, a well-known pioneer in the field, co-edit this volume and are careful to include not only classical but also non-classical approaches so as to ensure topicality. Overall, a valuable addition to the literature and a must-have for anyone dealing with complex systems.

Table of Contents:
Preface XI List of Contributors XIII 1 Functional Complexity Based on Topology 1 Hildegard Meyer-Ortmanns 1.1 Introduction 1 1.2 A Measure for the Functional Complexity of Networks 3 1.2.1 Topological Equivalence of LCE-Graphs 3 1.2.2 Vertex Resolution Patterns 5 1.2.3 Kauffman States for Link Invariants 6 1.2.4 Definition of the Complexity Measure 8 1.3 Applications 9 1.3.1 Creation of a Loop 10 1.3.2 Networks of Information 10 1.3.3 Transport Networks of Cargo 10 1.3.4 Boolean Networks of Gene Regulation 12 1.3.5 Topological Quantum Systems 12 1.3.6 Steering Dynamics Stored in Knots and Links 13 1.4 Conclusions 14 References 15 2 Connections Between Artificial Intelligence and Computational Complexity and the Complexity of Graphs 17 Angel Garrido 2.1 Introduction 17 2.2 Representation Methods 18 2.3 Searching Methods 20 2.4 Turing Machines 22 2.5 Fuzzy Logic and Fuzzy Graphs 24 2.6 Fuzzy Optimization 26 2.7 Fuzzy Systems 27 2.8 Problems Related to AI 27 2.9 Topology of Complex Networks 28 2.10 Hierarchies 30 2.10.1 Deterministic Case 30 2.10.2 Nondeterministic Case 31 2.10.3 Alternating Case 31 2.11 Graph Entropy 32 2.12 Kolmogorov Complexity 34 2.13 Conclusion 37 References 38 3 Selection-Based Estimates of Complexity Unravel Some Mechanisms and Selective Pressures Underlying the Evolution of Complexity in Artificial Networks 41 Herve Le Nagard and Olivier Tenaillon 3.1 Introduction 41 3.2 Complexity and Evolution 42 3.3 Macroscopic Quantification of Organismal Complexity 43 3.4 Selection-Based Methods of Complexity 44 3.5 Informational Complexity 44 3.6 Fisher Geometric Model 46 3.7 The Cost of Complexity 48 3.8 Quantifying Phenotypic Complexity 49 3.8.1 Mutation-Based Method: Mutational Phenotypic Complexity (MPC) 49 3.8.2 Drift Load Based Method: Effective Phenotypic Complexity (EPC) 50 3.8.3 Statistical Method: Principal Component Phenotypic Complexity (PCPC) 50 3.9 Darwinian Adaptive Neural Networks (DANN) 52 3.10 The Different Facets of Complexity 54 3.11 Mechanistic Understanding of Phenotypic Complexity 56 3.12 Selective Pressures Acting on Phenotypic Complexity 57 3.13 Conclusion and Perspectives 57 References 59 4 Three Types of Network Complexity Pyramid 63 Fang Jin-Qing, Li Yong, and Liu Qiang 4.1 Introduction 63 4.2 The First Type: The Life's Complexity Pyramid (LCP) 64 4.3 The Second Type: Network Model Complexity Pyramid 67 4.3.1 The Level-7: Euler (Regular) Graphs 68 4.3.2 The Level-6: ErdEUROos-Renyi Random Graph 68 4.3.3 The Level-5: Small-World Network and Scale-Free Models 69 4.3.4 The Level-4: Weighted Evolving Network Models 70 4.3.5 The Bottom Three Levels of the NMCP 71 4.3.5.1 The Level-3: The HUHPNM 72 4.3.5.2 The Level-2: The LUHNM 72 4.3.5.3 The Level-1: The LUHNM-VSG 73 4.4 The Third Type: Generalized Farey Organized Network Pyramid 78 4.4.1 Construction Method of the Generalized Farey Tree Network (GFTN) 78 4.4.2 Main Results of the GFTN 80 4.4.2.1 Degree Distribution 80 4.4.2.2 Clustering Coefficient 81 4.4.2.3 Diameter and Small World 82 4.4.2.4 Degree-Degree Correlations 83 4.4.3 Weighted Property of GFTN 85 4.4.4 Generalized Farey Organized Network Pyramid (GFONP) 87 4.4.4.1 Methods 87 4.4.4.2 Main Results of GFONP 90 4.4.4.3 Brief Summary 95 4.5 Main Conclusions 96 Acknowledgment 96 References 96 5 Computational Complexity of Graphs 99 Stasys Jukna 5.1 Introduction 99 5.2 Star Complexity of Graphs 100 5.2.1 Star Complexity of Almost All Graphs 104 5.2.2 Star Complexity and Biclique Coverings 107 5.3 From Graphs to Boolean Functions 107 5.3.1 Proof of the Strong Magnification Lemma 111 5.3.2 Toward the (2pc)n Lower Bound 114 5.4 Formula Complexity of Graphs 116 5.5 Lower Bounds via Graph Entropy 121 5.5.1 Star Complexity and Affine Dimension of Graphs 125 5.6 Depth-2 Complexity 126 5.6.1 Depth-2 with AND on the Top 128 5.6.2 Depth-2 with XOR on the Top 130 5.6.3 Depth-2 with Symmetric Top Gates 131 5.6.4 Weight of Symmetric Depth-2 Representations 134 5.7 Depth-3 Complexity 138 5.7.1 Depth-3 Complexity with XOR Bottom Gates 141 5.8 Network Complexity of Graphs 145 5.8.1 Realizing Graphs by Circuits 148 5.9 Conclusion and Open Problems 150 References 151 6 The Linear Complexity of a Graph 155 David L. Neel and Michael E. Orrison 6.1 Rationale and Approach 155 6.2 Background 157 6.2.1 Adjacency Matrices 157 6.2.2 Linear Complexity of a Matrix 158 6.2.3 Linear Complexity of a Graph 159 6.2.4 Reduced Version of a Matrix 160 6.3 An Exploration of Irreducible Graphs 161 6.3.1 Uniqueness and Prevalence 163 6.3.2 Structural Characteristics of the Irreducible Subgraph 164 6.4 Bounds on the Linear Complexity of Graphs 164 6.4.1 Naive Bounds 165 6.4.2 Bounds from Partitioning Edge Sets 166 6.4.3 Bounds for Direct Products of Graphs 167 6.5 Some Families of Graphs 168 6.5.1 Trees 168 6.5.2 Cycles 169 6.5.3 Complete Graphs 169 6.5.4 Complete k-partitite Graphs 170 6.5.5 Johnson Graphs 171 6.5.6 Hamming Graphs 173 6.6 Bounds for Graphs in General 173 6.6.1 Clique Partitions 173 6.7 Conclusion 174 References 175 7 Kirchhoff's Matrix-Tree Theorem Revisited: Counting Spanning Trees with the Quantum Relative Entropy 177 Vittorio Giovannetti and Simone Severini 7.1 Introduction 177 7.2 Main Result 178 7.3 Bounds 181 7.4 Conclusions 188 Acknowledgments 189 References 189 8 Dimension Measure for Complex Networks 191 O. Shanker 8.1 Introduction 191 8.2 Volume Dimension 192 8.3 Complex Network Zeta Function and Relation to Kolmogorov Complexity 193 8.4 Comparison with Complexity Classes 194 8.5 Node-Based Definition 195 8.6 Linguistic-Analysis Application 196 8.7 Statistical Mechanics Application 198 8.8 Function Values 201 8.8.1 Discrete Regular Lattice 201 8.8.2 Random Graph 202 8.8.3 Scale-Free Network and Fractal Branching Tree 202 8.9 Other Work on Complexity Measures 204 8.9.1 Early Measures of Complexity 205 8.9.2 Box Counting Dimension 205 8.9.3 Metric Dimension 206 8.10 Conclusion 206 References 206 9 Information-Based Complexity of Networks 209 Russell K. Standish 9.1 Introduction 209 9.2 History and Concept of Information-Based Complexity 210 9.3 Mutual Information 212 9.4 Graph Theory, and Graph Theoretic Measures: Cyclomatic Number, Spanning Trees 213 9.5 Erdos-Renyi Random Graphs, Small World Networks, Scale-free Networks 215 9.6 Graph Entropy 216 9.7 Information-Based Complexity of Unweighted, Unlabeled, and Undirected Networks 216 9.8 Motif Expansion 218 9.9 Labeled Networks 218 9.10 Weighted Networks 219 9.11 Empirical Results of Real Network Data, and Artificially Generated Networks 220 9.12 Extension to Processes on Networks 220 9.13 Transfer Entropy 222 9.14 Medium Articulation 223 9.15 Conclusion 225 References 225 10 Thermodynamic Depth in Undirected and Directed Networks 229 Francisco Escolano and Edwin R. Hancock 10.1 Introduction 229 10.2 Polytopal vs Heat Flow Complexity 231 10.3 Characterization of Polytopal and Flow Complexity 233 10.3.1 Characterization of Phase Transition 233 10.4 The Laplacian of a Directed Graph 236 10.5 Directed Heat Kernels and Heat Flow 238 10.6 Heat Flow-Thermodynamic Depth Complexity 239 10.6.1 Definitions for Undirected Graphs 239 10.6.2 Extension for Digraphs 241 10.7 Experimental Results 241 10.7.1 Undirected graphs: Complexity of 3D Shapes 241 10.7.2 Directed Graphs: Complexity of Human Languages 244 10.8 Conclusions and Future Work 245 Acknowledgments 246 References 246 11 Circumscribed Complexity in Ecological Networks 249 Robert E. Ulanowicz 11.1 A New Metaphor 249 11.2 Entropy as a Descriptor of Structure 250 11.3 Addressing Both Topology and Magnitude 251 11.4 Amalgamating Topology with Magnitudes 252 11.5 Effective Network Attributes 253 11.6 Limits to Complexity 253 11.7 An Example Ecosystem Network 255 11.8 A New Window on Complex Dynamics 257 References 258 12 Metros as Biological Systems: Complexity in Small Real-life Networks 259 Sybil Derrible 12.1 Introduction 259 12.2 Methodology 261 12.3 Interpreting Complexity 264 12.3.1 Numerically 267 12.3.1.1 Scale-free 267 12.3.1.2 Small World 268 12.3.1.3 Impacts of Complexity 269 12.3.2 Graphically 271 12.4 Network Centrality 274 12.4.1 Centrality Indicators 275 12.4.1.1 Degree Centrality 275 12.4.1.2 Closeness Centrality 275 12.4.1.3 Betweenness Centrality 276 12.4.2 Network Centrality of Metro Networks 277 12.4.2.1 Degree Centrality 277 12.4.2.2 Closeness Centrality 278 12.4.2.3 Betweenness Centrality 279 12.5 Conclusion 282 References 283 Index 287

About the Author :
Volume editors: Matthias Dehmer studied mathematics at the University of Siegen (Germany) and received his Ph.D. in computer science from the Technical University of Darmstadt (Germany). Afterwards, he was a research fellow at Vienna Bio Center (Austria), Vienna University of Technology, and University of Coimbra (Coimbra). He obtained his habilitation in applied discrete mathematics from the Vienna University of Technology. Currently, he is Professor at UMIT - TheHealth and Life Sciences University (Austria). His research interests are in bioinformatics, systems biology, network biology, complex networks, complexity and information theory. In particular, he is also working on machine learning-based methods to design new data analysis methods for solving problems in computational biology. Abbe Mowshowitz studied mathematics at the University of Chicago (BA 1961), and both mathematics and computer sciance at the University of Michigan (PhD 1967). He has held academic positions at the University of Toronto, The University of British Columbia, Erasmus University-Rotterdam, the University of Amsterdam and has been a professor of computer science at the City College of New York and in the PhD Program in Computer Science of the City University of New York since 1984. His research interests lie in applications of graph theory to the analysis of complex networks, and in the study of virtual organization. Series Editors: Matthias Dehmer (See above) Frank Emmert-Streib studied physics at the University of Siegen (Germany) and received his Ph.D. in Theoretical Physics from the University of Bremen (Germany). He was a postdoctoral research associate at the Stowers Institute for Medical Research (Kansas City, USA) in the Department for Bioinformatics and a Senior Fellow at the University of Washington (Seattle, USA) in the Department of Biostatistics and the Department of Genome Sciences. Currently, he is Lecturer/Assistant Professor at the Queen?s University Belfast at the Center for Cancer Research and Cell Biology (CCRCB) leading the Computational Biology and Machine Learning Lab. His research interests are in the ?eld of Computational Biology, Machine Learning and Biostatistics in the development and application of methods from statistics and machine learning for the analysis of high-throughput data from genomics and genetics experiments. Matthias Dehmer studied mathematics at the University of Siegen (Germany) and received his Ph.D. in computer science from the Technical University of Darmstadt (Germany). Afterwards, he was a research fellow at Vienna Bio Center (Austria) and at the Vienna University of Technology. Currently, he is Professor at UMIT - The Health and Life Sciences University (Austria) leading the Insititute for Bioinformatics and Translational Research. His research interests are in bioinformatics, systems biology, complex networks and statistics. In particular, he is also working on machine learning-based methods to design new data analysis methods for solving problems in computational and systems biology.

Review :
"Theory and practical applications are intertwined to give the reader a deeper appreciation of the problems and possible solutions. Network complexity is a rapidly evolving field touching on a wide range of issues from pure mathematics, physics and chemistry to industrial processes and consumer behavior. This book satisfies a pressing need for a comprehensive overview of the current state of the field." (AMS Journal, 1 October 2013) "Overall, a valuable addition to the literature and a must-have for anyone dealing with complex systems. The articles of this volume will not be reviewed individually." (Zentralblatt Math, 1 September 2013) "In summary, Advances in Network Complexity is a valuable treatise, outlining the many facets of the contemporary approaches to network complexity... It should be a must for any decent science library." (MATCH Communications in Mathematical and in Computer Chemistry, 1 December 2013) In summary, \Advances in Network Complexity" is a valuable treatise, outliningthe many facets of the contemporary approaches to network complexity. It will beuseful for both experts and beginners. It should be a must for any decent sciencelibrary.