This book aims to explain the basics of graph theory that are needed at an introductory level for students in computer or information sciences. To motivate students and to show that even these basic notions can be extremely useful, the book also aims to provide an introduction to the modern field of network science. Mathematics is often unnecessarily difficult for students, at times even intimidating. For this reason, explicit attention is paid in the first chapters to mathematical notations and proof techniques, emphasizing that the notations form the biggest obstacle, not the mathematical concepts themselves. This approach allows to gradually prepare students for using tools that are necessary to put graph theory to work: complex networks. In the second part of the book the student learns about random networks, small worlds, the structure of the Internet and the Web, peer-to-peer systems, and social networks. Again, everything is discussed at an elementary level, but such that in the end students indeed have the feeling that they: 1.Have learned how to read and understand the basic mathematics related to graph theory. 2.Understand how basic graph theory can be applied to optimization problems such as routing in communication networks. 3.Know a bit more about this sometimes mystical field of small worlds and random networks. There is an accompanying web site www.distributed-systems.net/gtcn from where supplementary material can be obtained, including exercises, Mathematica notebooks, data for analyzing graphs, and generators for various complex networks.
Author(s): Maarten van Steen
Publisher: Maarten van Steen
Year: 2010
Language: English
Pages: 299
Tags: Математика;Дискретная математика;Теория графов;
Preface......Page 11
Introduction......Page 15
Historical perspective......Page 18
From telephony to the Internet......Page 20
The Web and Wikis......Page 22
Online communities......Page 23
Traditional social networks......Page 24
Networks everywhere......Page 25
Organization of this book......Page 27
Foundations......Page 31
Graphs and vertex degrees......Page 32
Degree sequence......Page 37
Subgraphs and line graphs......Page 42
Data structures......Page 45
Graph isomorphism......Page 47
Connectivity......Page 51
Graph embeddings......Page 59
Planar graphs......Page 64
Extensions......Page 69
Basics of directed graphs......Page 71
Connectivity for directed graphs......Page 75
Weighted graphs......Page 79
Edge colorings......Page 83
Vertex colorings......Page 85
Network traversal......Page 93
Euler tours......Page 95
Constructing an Euler tour......Page 96
The Chinese postman problem......Page 101
Properties of Hamiltonian graphs......Page 106
Finding a Hamilton cycle......Page 111
Optimal Hamilton cycles......Page 114
Trees......Page 119
Trees in transportation networks......Page 121
Trees as data structures......Page 123
Fundamentals......Page 126
Spanning trees......Page 130
Routing in communication networks......Page 133
Dijkstra's algorithm......Page 134
The Bellman-Ford algorithm......Page 137
A note on algorithmic performance......Page 141
Network analysis......Page 145
Vertex degrees......Page 147
Degree distribution......Page 148
Degree correlations......Page 150
Distance statistics......Page 154
Some effects of clustering......Page 157
Local view......Page 158
Global view......Page 160
Centrality......Page 164
Random networks......Page 169
Introduction......Page 171
Classical random networks......Page 172
Degree distribution......Page 173
Other metrics for random graphs......Page 176
Small worlds......Page 180
Fundamentals......Page 186
Properties of scale-free networks......Page 192
Related networks......Page 195
Modern computer networks......Page 199
Computer networks......Page 201
Measuring the topology of the Internet......Page 206
Peer-to-peer overlay networks......Page 209
Structured overlay networks......Page 210
Random overlay networks......Page 218
The organization of the Web......Page 226
Measuring the topology of the Web......Page 228
Social networks......Page 237
Examples......Page 239
Historical background......Page 241
Sociograms in practice: a teacher's aid......Page 245
Centrality and prestige......Page 248
Structural balance......Page 254
Cohesive subgroups......Page 260
Affiliation networks......Page 266
Structural equivalence......Page 269
Automorphic equivalence......Page 272
Regular equivalence......Page 273
Conclusions......Page 275
Mathematical notations......Page 281
Index......Page 285
Bibliography......Page 293
