Book contents
- Frontmatter
- Contents
- Preface
- List of abbreviations
- 1 A brief history of the Internet
- 2 How the Internet works
- 3 Measuring the global Internet
- 4 The Internet's large-scale topology
- 5 Modeling the Internet
- 6 Internet robustness
- 7 Virtual and social networks in the Internet
- 8 Searching and walking on the Internet
- 9 Epidemics in the Internet
- 10 Beyond the Internet's skeleton: traffic and global performance
- 11 Outlook
- Appendix 1 Graph theory applied to topology analysis
- Appendix 2 Interface resolution and router topology
- Appendix 3 Numerical analysis of heavy tailed distributions
- Appendix 4 Degree correlations
- Appendix 5 Scale-free networks: scaling relations
- Appendix 6 The SIR model of virus propagation
- References
- Index
Appendix 1 - Graph theory applied to topology analysis
Published online by Cambridge University Press: 12 January 2010
- Frontmatter
- Contents
- Preface
- List of abbreviations
- 1 A brief history of the Internet
- 2 How the Internet works
- 3 Measuring the global Internet
- 4 The Internet's large-scale topology
- 5 Modeling the Internet
- 6 Internet robustness
- 7 Virtual and social networks in the Internet
- 8 Searching and walking on the Internet
- 9 Epidemics in the Internet
- 10 Beyond the Internet's skeleton: traffic and global performance
- 11 Outlook
- Appendix 1 Graph theory applied to topology analysis
- Appendix 2 Interface resolution and router topology
- Appendix 3 Numerical analysis of heavy tailed distributions
- Appendix 4 Degree correlations
- Appendix 5 Scale-free networks: scaling relations
- Appendix 6 The SIR model of virus propagation
- References
- Index
Summary
The natural framework for a correct mathematical description of complex networks is graph theory. The origins of graph theory can be traced back to the pioneering work of Euler to solve the Königsberg bridges problem (Euler, 1736), and has now reached a maturity in which a wealth of results of immediate applicability are useful for the understanding of real complex networks. In this appendix we shall provide a cursory introduction to the main definitions and concepts of graph theory, useful for the analysis of real networks. The main sources followed are the books by Chartrand and Lesniak (1986), Bollobás (1998), and Bollobás (1985), as well as the review articles by Albert and Barabási (2002), Dorogovtsev and Mendes (2002), and Newman (2003), covering more recent aspects.
Graphs and subgraphs
An undirected graph G is defined by a pair of sets G = (V, E), where V is a non-empty countable set of elements, called vertices or nodes, and E is a set of unordered pairs of different vertices, called edges or links. Throughtout the book a vertex is reffered to by its order i in the set V. The edge (i, j) joins the vertices i and j, which are said to be adjacent or connected. The total number of vertices in the graph (the cardinality of the set V) is denoted as N, the size of the graph.
- Type
- Chapter
- Information
- Evolution and Structure of the InternetA Statistical Physics Approach, pp. 229 - 237Publisher: Cambridge University PressPrint publication year: 2004