O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Analysis of Complex Networks

Book Description

Mathematical problems such as graph theory problems are of increasing importance for the analysis of modelling data in biomedical research such as in systems biology, neuronal network modelling etc. This book follows a new approach of including graph theory from a mathematical perspective with specific applications of graph theory in biomedical and computational sciences. The book is written by renowned experts in the field and offers valuable background information for a wide audience.

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright
  4. Contents
  5. Preface
  6. List of Contributors
  7. 1: Entropy, Orbits, and Spectra of Graphs
    1. 1.1 Introduction
    2. 1.2 Entropy or the Information Content of Graphs
    3. 1.3 Groups and Graph Spectra
    4. 1.4 Approximating Orbits
    5. 1.5 Alternative Bases for Structural Complexity
  8. 2: Statistical Mechanics of Complex Networks
    1. 2.1 Introduction
    2. 2.2 Macroscopics: Entropies for Networks
    3. 2.3 Microscopics: Hamiltonians of Networks – Network Thermodynamics
    4. 2.4 Ensembles of Random Networks – Superstatistics
    5. 2.5 Conclusion
  9. 3: A Simple Integrated Approach to Network Complexity and Node Centrality
    1. 3.1 Introduction
    2. 3.2 The Small-World Connectivity Descriptors (Bourgas Indices, BI)
    3. 3.3 The Integrated Centrality Measure
  10. 4: Spectral Theory of Networks: From Biomolecular to Ecological Systems
    1. 4.1 Introduction
    2. 4.2 Background on Graph Spectra
    3. 4.3 Spectral Measures of Node Centrality
    4. 4.4 Global Topological Organization of Complex Networks
    5. 4.5 Communicability in Complex Networks
    6. 4.6 Network Bipartivity
    7. 4.7 Conclusion
  11. 5: On the Structure of Neutral Networks of RNA Pseudoknot Structures
    1. 5.1 Motivation and Background
    2. 5.2 Preliminaries
    3. 5.3 Connectivity
    4. 5.4 The Largest Component
    5. 5.5 Distances in n -Cubes
    6. 5.6 Conclusion
  12. 6: Graph Edit Distance – Optimal and Suboptimal Algorithms with Applications
    1. 6.1 Introduction
    2. 6.2 Graph Edit Distance
    3. 6.3 Computation of GED
    4. 6.4 Applications
    5. 6.5 Experimental Evaluation
    6. 6.6 Summary and Conclusions
  13. 7: Graph Energy
    1. 7.1 Introduction
    2. 7.2 Bounds for the Energy of Graphs
    3. 7.3 Hyperenergetic, Hypoenergetic, and Equienergetic Graphs
    4. 7.4 Graphs Extremal with Regard to Energy
    5. 7.5 Miscellaneous
    6. 7.6 Concluding Remarks
  14. 8: Generalized Shortest Path Trees: A Novel Graph Class by Example of Semiotic Networks
    1. 8.1 Introduction
    2. 8.2 A Class of Tree-Like Graphs and Some of Its Derivatives
    3. 8.3 Semiotic Systems as Conceptual Graphs
  15. 9: Applications of Graph Theory in Chemo- and Bioinformatics
    1. 9.1 Introduction
    2. 9.2 Molecular Graphs
    3. 9.3 Common Problems with Molecular Graphs
    4. 9.4 Comparisons and 3D Alignment of Protein Structures
    5. 9.5 Identification of Macromolecular Assemblies in Crystal Packing
    6. 9.6 Chemical Graph Formats
    7. 9.7 Chemical Software Packages
    8. 9.8 Chemical Databases and Resources
    9. 9.9 Subgraph Isomorphism Solution in SQL
    10. 9.10 Cycles in Graphs
    11. 9.11 Aromatic Properties
    12. 9.12 Planar Subgraphs
    13. 9.13 Conclusion
  16. 10: Structural and Functional Dynamics in Cortical and Neuronal Networks
    1. 10.1 Introduction
    2. 10.2 Structural Dynamics
    3. 10.3 Functional Dynamics
    4. 10.4 Summary
  17. 11: Network Mapping of Metabolic Pathways
    1. 11.1 Introduction
    2. 11.2 Brief Overview of Network Mapping Methods
    3. 11.3 Modeling Metabolic Pathway Mappings
    4. 11.4 Computing Minimum Cost Homomorphisms
    5. 11.5 Mapping Metabolic Pathways
    6. 11.6 Implications of Pathway Mappings
    7. 11.7 Conclusion
  18. 12: Graph Structure Analysis and Computational Tractability of Scheduling Problems
    1. 12.1 Introduction
    2. 12.2 The Connected List Coloring Problem
    3. 12.3 Some Practical Problems Reducible to the CLC Problem
    4. 12.4 A Parameterized Class of Subproblems of the CLC Problem
    5. 12.5 Complexities of Eight Representatives of Class CLC( X )
    6. 12.6 A Basis System of Problems
    7. 12.7 Conclusion
  19. 13: Complexity of Phylogenetic Networks: Counting Cubes in Median Graphs and Related Problems
    1. 13.1 Introduction
    2. 13.2 Preliminaries
    3. 13.3 Treelike Equalities and Euler-Type Inequalities
    4. 13.4 Cube Polynomials
    5. 13.5 Hamming Polynomials
    6. 13.6 Maximal Cubes in Median Graphs of Circular Split Systems
    7. 13.7 Applications in Phylogenetics
    8. 13.8 Summary and Conclusion
  20. 14: Elementary Elliptic (R, q)-Polycycles
    1. 14.1 Introduction
    2. 14.2 Kernel Elementary Polycycles
    3. 14.3 Classification of Elementary ({2, 3, 4, 5}, 3)-Polycycles
    4. 14.4 Classification of Elementary ({2, 3}, 4)-Polycycles
    5. 14.5 Classification of Elementary ({2, 3}, 5)-Polycycles
    6. 14.6 Conclusion
  21. 15: Optimal Dynamic Flows in Networks and Algorithms for Finding Them
    1. 15.1 Introduction
    2. 15.2 Optimal Dynamic Single-Commodity Flow Problems and Algorithms for Solving Them
    3. 15.3 Optimal Dynamic Multicommodity Flow Problems and Algorithms for Solving Them
    4. 15.4 Conclusion
  22. 16: Analyzing and Modeling European R&D Collaborations: Challenges and Opportunities from a Large Social Network
    1. 16.1 Introduction
    2. 16.2 Data Preparation
    3. 16.3 Network Definition
    4. 16.4 Network Structure
    5. 16.5 Community Structure
    6. 16.6 Communities in the Framework Program Networks
    7. 16.7 Binary Choice Model
    8. 16.8 Summary
  23. 17: Analytic Combinatorics on Random Graphs
    1. 17.1 Introduction
    2. 17.2 Trees
    3. 17.3 Random Mappings
    4. 17.4 The Random Graph Model of Erdőos and Rényi
    5. 17.5 Planar Graphs
  24. Index