Random Graphs and Complex Networks

by Remco van der Hofstad

Overview

This rigorous introduction to network science presents random graphs as models for real-world networks. Such networks have distinctive empirical properties and a wealth of new models have emerged to capture them. Classroom tested for over ten years, this text places recent advances in a unified framework to enable systematic study. Designed for a master's-level course, where students may only have a basic background in probability, the text covers such important preliminaries as convergence of random variables, probabilistic bounds, coupling, martingales, and branching processes. Building on this base - and motivated by many examples of real-world networks, including the Internet, collaboration networks, and the World Wide Web - it focuses on several important models for complex networks and investigates key properties, such as the connectivity of nodes. Numerous exercises allow students to develop intuition and experience in working with the models.

Product Details

ISBN-13:	9781107172876
Publisher:	Cambridge University Press
Publication date:	12/22/2016
Series:	Cambridge Series in Statistical and Probabilistic Mathematics , #43
Pages:	236
Product dimensions:	7.24(w) x 10.31(h) x 0.87(d)

About the Author

Remco van der Hofstad is Full Professor of Probability at Eindhoven University of Technology and Acting Scientific Director of the European Institute for Statistics, Probability, Stochastic Operations Research and their Applications (Eurandom). He has authored over 100 research articles and has taught courses on random graphs at over ten institutions. He received the 2003 Prix Henri Poincaré (jointly with Gordon Slade) and the 2007 Rollo Davidson Prize, and he is a laureate of the 2003 Innovative Research VIDI Scheme and the 2008 Innovative Research VICI Scheme.

Table of Contents

Preface; Course outline; 1. Introduction; Part I. Preliminaries: 2. Probabilistics methods; 3. Branching processes; Part II. Basic Models: 4. Phase transition for the Erdos–Renyi random graph; 5. Erdos–Renyi random graph revisited; Part III. Models for Complex Networks: 6. Generalized random graphs; 7. Configuration model; 8. Preferential attachment models; Appendix; Glossary; References; Index.

Editorial Reviews

"… a modern and deep, yet accessible, introduction to the models that make up [the] basis for the theoretical study of random graphs and complex networks. The book strikes a balance between providing broad perspective and analytic rigor that is a pleasure for the reader."
Adam Wierman, California Institute of Technology

"This text builds a bridge between the mathematical world of random graphs and the real world of complex networks. It combines techniques from probability theory and combinatorics to analyze the structural properties of large random graphs. Accessible to network researchers from different disciplines, as well as masters and graduate students, the material is suitable for a one-semester course, and is laced with exercises that help the reader grasp the content. The exposition focuses on a number of core models that have driven recent progress in the field, including the Erdős–Rényi random graph, the configuration model, and preferential attachment models. A detailed description is given of all their key properties. This is supplemented with insightful remarks about properties of related models so that a full panorama unfolds. As the presentation develops, the link to complex networks provides constant motivation for the routes that are being chosen."
Frank den Hollander, Leiden University

"The first volume of Remco van der Hofstad's Random Graphs and Complex Networks is the definitive introduction into the mathematical world of random networks. Written for students with only a modest background in probability theory, it provides plenty of motivation for the topic and introduces the essential tools of probability at a gentle pace. It covers the modern theory of Erdős–Rényi graphs, as well as the most important models of scale-free networks that have emerged in the last fifteen years. This is a truly wonderful first volume; the second volume, leading up to current research topics, is eagerly awaited."
Peter Mörters, University of Bath

"This new book on random graph models for complex networks is a wonderful addition to the field. It takes the uninitiated reader from the basics of graduate probability to the classical Erdős–Rényi random graph before terminating at some of the fundamental new models in the discipline. The author does an exemplary job of both motivating the models of interest and building all the necessary mathematical tools required to give a rigorous treatment of these models. Each chapter is complemented by a comprehensive set of exercises allowing the reader ample scope to actively master the techniques covered in the chapter."
Shankar Bhamidi, University of North Carolina, Chapel Hill

"This book is invaluable for anybody who wants to learn or teach the modern theory of random graphs and complex networks. I have used it as a textbook for long and short courses at different levels. Students always like the book because it has all they need: exciting high-level ideas, motivating examples, very clear proofs, and an excellent set of exercises. Easy to read, extremely well structured, and self-contained, the book builds proficiency with random graph models essential for state-of-the-art research."
Nelly Litvak, University of Twente

'What makes the book particularly interesting is that it provides all important preliminaries for readers not having the basic background knowledge of random graphs. … The book is well-suited for a graduate course on random graphs, where students may only have minimal background in probability theory, as the book provides plenty of motivation for the topic and covers all important preliminaries. All the chapters are supplemented by extensive exercises to develop better intuition and to progressively master the models covered in the book. In a nutshell, the book is easy to follow and well-organized for developing proficiency in random graph models necessary for state of the art research.' Ghulam Abbas, Complex Adaptive Systems Modeling

'The writing is of a high standard. I would certainly recommend it to a starting graduate student, even if their first degree was not mathematics.' Tobias Muller, Nieuw Archief voor Weskunde

From the Publisher