Graph Theory and Complex Networks

You can get a digital (personalized) copy of this book for free.

Goals

GTCN 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.

I take the starting-point that mathematics for most students is unnecessarily intimidating. 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. Taking this approach has allowed me 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, 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.

Courseware

We have some additional material that may help to teach and learn the material:

• Exercises (with solutions)
• Slides (with or without animations) and handouts.

Figures

To make things a bit simple for those wanting to prepare presentations, exams, etc., all figures (in PDF) are in a single zip file.