You are previewing Complex Networks.
O'Reilly logo
Complex Networks

Book Description

Examining important results and analytical techniques, this graduate-level textbook is a step-by-step presentation of the structure and function of complex networks. Using a range of examples, from the stability of the internet to efficient methods of immunizing populations, and from epidemic spreading to how one might efficiently search for individuals, this textbook explains the theoretical methods that can be used, and the experimental and analytical results obtained in the study and research of complex networks. Giving detailed derivations of many results in complex networks theory, this is an ideal text to be used by graduate students entering the field. End-of-chapter review questions help students monitor their own understanding of the materials presented.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Contents
  6. 1. Introduction
    1. 1.1 Graph theory
    2. 1.2 Scale-free processes and fractal structures
  7. Part I: Random Network Models
    1. 2. The Erdős–Rényi models
      1. 2.1 Erdős–Rényi graphs
      2. 2.2 Scale-free networks
      3. 2.3 Diameter and fractal dimensions
      4. 2.4 Random graphs as a model of real networks
      5. 2.5 Outlook and applications
    2. 3. Observations in real-world networks: the Internet, epidemics, proteins and DNA
      1. 3.1 Real-world complex networks
      2. 3.2 Properties of real-world networks
      3. 3.3 Betweenness centrality: what is your importance in the network?
      4. 3.4 Conclusions
    3. 4. Models for complex networks
      1. 4.1 Introduction
      2. 4.2 Introducing shortcuts: small-world networks
      3. 4.3 Random graphs with a given degree distribution
      4. 4.4 Introducing correlations
      5. 4.5 Randomly directed networks: modeling the WWW
      6. 4.6 Introducing geography: embedded scale-free lattices
      7. 4.7 Hierarchical and fractal networks
      8. Exercises
    4. 5. Growing network models: the Barabási–Albert model and its variants
      1. 5.1 The Barabási–Albert model
      2. 5.2 Variants of the Barabási–Albert model
      3. 5.3 Linearized chord diagram (LCD)
      4. 5.4 Fitness models
      5. Exercises
  8. Part II: Structure and Robustness of Complex Networks
    1. 6. Distances in scale-free networks: the ultra small world
      1. 6.1 Introduction
      2. 6.2 Minimal distance networks
      3. 6.3 Random scale-free networks
      4. 6.4 Layer structure and Internet tomography – how far do your emails travel?
      5. 6.5 Discussion and conclusions
      6. Exercises
    2. 7. Self-similarity in complex networks
    3. 8. Distances in geographically embedded networks
    4. 9. The structure of networks: the generating function method
      1. 9.1 Introduction
      2. 9.2 General results
      3. 9.3 Scale-free networks
      4. Exercises
    5. 10. Percolation on complex networks
      1. 10.1 Introduction
      2. 10.2 Random breakdown
      3. 10.3 Intentional attack
      4. 10.4 Critical exponents
      5. 10.5 Percolation in networks with correlations
      6. 10.6 k-core percolation: fault tolerant networks
      7. 10.7 Conclusions
      8. Exercises
    6. 11. Structure of random directed networks: the bow tie
      1. 11.1 Introduction
      2. 11.2 Structure
      3. 11.3 The giant component
      4. 11.4 Percolation in directed scale-free networks
      5. 11.5 Critical exponents
      6. 11.6 Summary
      7. Exercises
    7. 12. Introducing weights: bandwidth allocation and multimedia broadcasting
      1. 12.1 Introduction
      2. 12.2 Random weighted networks
      3. 12.3 Correlated weighted networks
      4. 12.4 Summary
      5. Exercises
  9. Part III: Network Function: Dynamics and Applications
    1. 13. Optimization of the network structure
      1. 13.1 Introduction
      2. 13.2 Optimization analysis
      3. 13.3 General results
      4. 13.4 Summary
    2. 14. Epidemiological models
      1. 14.1 Introduction
      2. 14.2 Epidemic dynamics and epidemiological models
      3. Exercises
    3. 15. Immunization
      1. 15.1 Random immunization
      2. 15.2 Targeted immunization: choosing the right people to immunize
      3. 15.3 Acquaintance immunization: choosing the right people with minimal information
      4. 15.4 Numerical results for the SIR model
      5. 15.5 Conclusion
      6. Exercises
    4. 16. Thermodynamic models on networks
      1. 16.1 Introduction
      2. 16.2 The Ising model in complex networks
      3. 16.3 Summary
      4. Exercises
    5. 17. Spectral properties, transport, diffusion and dynamics
      1. 17.1 The spectrum of the adjacency matrix
      2. 17.2 The Laplacian
      3. 17.3 The spectral gap and diffusion on graphs
      4. 17.4 Traffic and self-similarity
      5. 17.5 Summary
      6. Exercises
    6. 18. Searching in networks
      1. 18.1 Introduction
      2. 18.2 Searching using degrees
      3. 18.3 Searching in networks using shortcuts
      4. 18.4 Summary
      5. Exercises
    7. 19. Biological networks and network motifs
      1. 19.1 Structure of metabolic networks
      2. 19.2 Structure of genetic networks
      3. 19.3 Network motifs
      4. 19.4 Summary
  10. Appendix A: Probability theoretical methods
  11. Appendix B: Asymptotics and orders of magnitude
  12. Appendix C: Algorithms for network simulation and investigation
  13. References
  14. Index