Advances in Network Complexity

A well–balanced overview of mathematical approaches to complex systems ranging from applications in chemistry and ecology to basic research questions on network complexity. Matthias Dehmer, Abbe Mowshowitz, and Frank Emmert–Streib, well–known pioneers in the field, have edited this volume with a view to balancing classical and modern approaches to ensure broad coverage of contemporary research problems. The book is a valuable addition to the literature and a must–have for anyone dealing with network compleaity and complexity issues.

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.3 Applications 9 1.4 Conclusions 14 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.11 Graph Entropy 32 2.12 Kolmogorov Complexity 34 2.13 Conclusion 37 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.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 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.4 The Third Type: Generalized Farey Organized Network Pyramid 78 4.5 Main Conclusions 96 5 Computational Complexity of Graphs 99 Stasys Jukna 5.1 Introduction 99 5.2 Star Complexity of Graphs 100 5.3 From Graphs to Boolean Functions 107 5.4 Formula Complexity of Graphs 116 5.5 Lower Bounds via Graph Entropy 121 5.6 Depth–2 Complexity 126 5.7 Depth–3 Complexity 138 5.8 Network Complexity of Graphs 145 5.9 Conclusion and Open Problems 150 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.3 An Exploration of Irreducible Graphs 161 6.4 Bounds on the Linear Complexity of Graphs 164 6.5 Some Families of Graphs 168 6.6 Bounds for Graphs in General 173 6.6.1 Clique Partitions 173 6.7 Conclusion 174 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 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.9 Other Work on Complexity Measures 204 8.10 Conclusion 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 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.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.7 Experimental Results 241 10.8 Conclusions and Future Work 245 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 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.4 Network Centrality 274 12.5 Conclusion 282 References 283 Index 287

Matthias Dehmer studied mathematics at the University of Siegen, Germany, and received his PhD in computer science from the Darmstadt University of Technology, Germany. Afterwards, he was a research fellow at Vienna Bio Center, Austria, Vienna University of Technology and University of Coimbra, Portugal. Currently, he is Professor at UMIT – The Health and Life Sciences University, Austria, and is Head of the Institute for Bioinformatics and TranslationalResearch. His research interests are in bioinformatics, chemical graph theory, systems biology, complex networks, complexity, statistics and information theory. He has published extensively on network complexity and methods to analyze complex networks quantitatively. Abbe Mowshowitz studied mathematics at the University of Chicago (BA 1961), and both mathematics and computer science 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. Frank Emmert–Streib studied physics at the University of Siegen, Germany, gaining his PhD in theoretical physics from the University of Bremen. He was a postdoctoral research associate at the Stowers Institute for Medical Research, Kansas City, USA, and a senior fellow at the University of Washington, Seattle, USA. Currently, he is Lecturer/Assistant Professor at the Queen′s University Belfast, UK, at the Center for Cancer Research and Cell Biology, heading the Computational Biology and Machine Learning Lab. His research interests are in the field of computational biology, machine learning and network medicine.

“In summary, “Advances in Network Complexity” is a valuable treatise, outlining the many facets of the contemporary approaches to network complexity. It will be useful for both experts and beginners. It should be a must for any decent science library.”  ( MATCH Communications in Mathematical and in Computer Chemistry, 1 March 2014) “This volume will be particularly valuable to researchers in these areas as a resource to learn about earlier threads of network analysis coming from unfamiliar fields such as computer science and pure mathematics.”  ( Journal of Complex Networks, 1 March 2014) “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 will be useful for both experts and beginners. It should be a must for any decent science library.