Introduction to the Introduction

The theory of random graphs began in the late 1950s in several papers by Erdös and Rényi. However, the introduction at the end of the twentieth century of the small world model of Watts and Strogatz (1998) and the preferential attachment model of Barabási and Albert (1999) have led to an explosion of research. Querying the Science Citation Index in early July 2005 produced 1154 citations for Watts and Strogatz (1998) and 964 for Barabási and Albert (1999). Survey articles of Albert and Barabási (2002), Dorogovstev and Mendes (2002), and Newman (2003) each have hundreds of references. A book edited by Newman, Barabási, and Watts (2006) contains some of the most important papers. Books by Watts (2003) and Barabási (2002) give popular accounts of the new science of networks, which explains “how everything is connected to everything else and what it means for science, business, and everyday life.”

While this literature is extensive, many of the papers are outside the mathematical literature, which makes writing this book a challenge and an opportunity. A number of articles have appeared in Nature and Science. These journals with their impressive impact factors are, at least in the case of random graphs, the home of 10 second sound bite science.