Handbook of Graph Theory, 2nd Edition

Chapter 12

Communication Networks

Section 12.1 Complex Networks

Anthony Bonato

Ryerson University

Fan Chung

University of California, San Diego

Introduction

The study of complex networks analyzes graph-theoretical properties arising in real-world networks, ranging from technological, social, and biological. Web pages and their links, protein-protein interaction networks, and on-line social networks such as Facebook and LinkedIn are some of the commonly studied examples of such networks.

Never before have we confronted graphs of not only such tremendous sizes but also extraordinary richness and complexity, both at a theoretical and a practical level. Numerous problems arise. For example, what are basic structures of such large networks? How do ...