Book:Maarten van Steen/Graph Theory and Complex Networks

Maarten van Steen: Graph Theory and Complex Networks

Published $\text {2010}$, Maarten van Steen

ISBN 978-9081540612

Subject Matter

• Graph Theory

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