Book:Maarten van Steen/Graph Theory and Complex Networks

From ProofWiki
Jump to: navigation, search

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