Analysis of Complex Networks

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