Graph Theory and Complex Networks AN INTRODUCTION by Maarten van Steen

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

The book is only part of what is needed to teach this material. Practice is very important. To this end, we have collected numerous exercises, but have also prepared lab assignments (big and small). The latter are done using Mathematica with Combinatorica, which we have found to be an extremely powerful tool. This site holds supplementary material including:

• Exercises (and solutions)
• Slides and handouts
• Mathematica notebooks with example code
• Data sets and graph generators

All material, including the book, can be freely accessed