Advances in network complexity
 Responsibility
 edited by Matthias Dehmer, Abbe Mowshowitz, and Frank EmmertStreib.
 Language
 English.
 Publication
 Weinheim, Germany : WileyBlackwell, 2013.
 Copyright notice
 ©2013
 Physical description
 xiv, 293 pages : illustrations (some colour) ; 25 cm.
 Series
 Quantitative and network biology ; v. 4.
Access
Creators/Contributors
 Contributor
 Dehmer, Matthias, 1968 editor of compilation.
 Mowshowitz, Abbe editor of compilation.
 EmmertStreib, Frank, editor of compilation.
Contents/Summary
 Bibliography
 Includes bibliographical references and index.
 Contents

 Preface XI List of Contributors XIII 1 Functional Complexity Based on Topology 1 Hildegard MeyerOrtmanns 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 SelectionBased 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 SelectionBased 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 JinQing, 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 Depth2 Complexity 126 5.7 Depth3 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 MatrixTree 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 NodeBased Definition 195 8.6 LinguisticAnalysis 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 InformationBased Complexity of Networks 209 Russell K. Standish 9.1 Introduction 209 9.2 History and Concept of InformationBased Complexity 210 9.3 Mutual Information 212 9.4 Graph Theory, and Graph Theoretic Measures: Cyclomatic Number, Spanning Trees 213 9.5 ErdosRenyi Random Graphs, Small World Networks, Scalefree Networks 215 9.6 Graph Entropy 216 9.7 InformationBased 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 FlowThermodynamic 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 Reallife 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.
 (source: Nielsen Book Data)
 Publisher's Summary
 A wellbalanced 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 wellknown pioneer in the field, coedit this volume and are careful to include not only classical but also nonclassical approaches so as to ensure topicality. Overall, a valuable addition to the literature and a musthave for anyone dealing with complex systems.
(source: Nielsen Book Data)
Subjects
Bibliographic information
 Publication date
 2013
 Copyright date
 2013
 Series
 Quantitative and network biology ; volume 4
 ISBN
 9783527332915 (hardback)
 352733291X (hardback)
 9783527670475 (ePDF)
 9783527670482 (ePUB)
 9783527670499 (mobi)
 9783527670468 (oBook)