# Book:Maarten van Steen/Graph Theory and Complex Networks

## Maarten van Steen: *Graph Theory and Complex Networks*

Published $2010$, **Maarten van Steen**

- ISBN 978-9081540612.

### Subject Matter

### Contents

- Preface

- 1 Introduction
- 1.1 Communication networks
- Historical perspective
- From telephony to the Internet
- The Web and Wikis
- 1.2 Social networks
- Online communities
- Traditional social networks
- 1.3 Networks everywhere
- 1.4 Organization of this book

- 2 Foundations
- 2.1 Formalities
- Graphs and vertex degrees
- Degree sequence
- Subgraphs and line graphs
- 2.2 Graph representations
- Data structures
- Graph isomorphism
- 2.3 Connectivity
- 2.4 Drawing graphs
- Graph embeddings
- Planar graphs

- 3 Extensions
- 3.1 Directed graphs
- Basics of directed graphs
- Connectivity for directed graphs
- 3.2 Weighted graphs
- 3.3 Colorings
- Edge colorings
- Vertex colorings

- 4 Network traversal
- 4.1 Euler tours
- Constructing an Euler tour
- The Chinese postman problem
- 4.2 Hamilton cycles
- Properties of Hamiltonian graphs
- Finding a Hamilton cycle
- Optimal Hamilton cycles

- 5 Trees
- 5.1 Background
- Trees in transportation networks
- Trees as data structures
- 5.2 Fundamentals
- 5.3 Spanning trees
- 5.4 Routing in communication networks
- Dijkstra's algorithm
- The Bellman-Ford algorithm
- A note on algorithmic performance

- 6 Network analysis
- 6.1 Vertex degrees
- Degree distribution
- Degree correlations
- 6.2 Distance statistics
- 6.3 Clustering coefficient
- Some effects of clustering
- Local view
- Global view
- 6.4 Centrality

- 7 Random networks
- 7.1 Introduction
- 7.2 Classical random networks
- Degree distribution
- Other metrics for random graphs
- 7.3 Small worlds
- 7.4 Scale-free networks
- Fundamentals
- Properties of scale-free networks
- Related networks

- 8 Modern computer networks
- 8.1 The Internet
- Computer networks
- Measuring the topology of the Internet
- 8.2 Peer-to-peer overlay networks
- Structured overlay networks
- Random overlay networks
- 8.3 The World Wide Web
- The organization of the Web
- Measuring the topology of the Web

- 9 Social networks
- 9.1 Social network analysis: introduction
- Examples
- Historical background
- Sociograms in practice: a teacher's aid
- 9.2 Some basic concepts
- Centrality and prestige
- Structural balance
- Cohesive subgroups
- Affiliation networks
- 9.3 Equivalence
- Structural equivalence
- Automorphic equivalence
- Regular equivalence

- Conclusions
- Mathematical notations
- Index
- Bibliography