Random Graph Dynamics

I have been meaning to acquaint myself with the incredibly active and well-publicized field of random graph dynamics ever since seeing an exciting set of lectures on the topic by Jennifer Tour Chayes. This book captures the flavor of many of the significant results in this area and exposes the arguments supporting them. It is an unforbidding 200-page paperback, but don’t be fooled into thinking of it as a quick read. It is dense with equations and subtle arguments expressed with a minimal number of words. Yet the tone remains chatty and entertaining throughout: “In any case, this does not seem to be a good model for sex in Sweden.” “Only a mathematician would be pessimistic enough to think that this bounded sequence might not converge, so following the three physicists we assume…” The author even challenges readers to tackle a number of his own conjectures.

The book surveys work on many families of random graphs: Erdős-Renyi, small worlds, fixed degree distributions, preferential attachment graphs, and the CHKNS model. One could use the book as a map of the literature, to locate important papers relating to each topic, but its contribution is far greater. The author presents complete proofs of many results, by way of linking theorems to each other and to urns, martingales, and random walks. In this, the text adds value because it refines results which have been published along the way with vague definitions or slightly misstated parameters. Noteworthy results covered are phase transitions, power law degree distributions for preferential attachment graphs, diameter, epidemic progression, and voter models.

I often wished for a glossary of symbols used, though I estimate it might run to several pages. Researchers and students working in this area would be well-advised to devote the time necessary for a close reading.

Sommer Gentry is an Associate Professor of Mathematics at the United States Naval Academy, and a Research Associate in the Johns Hopkins School of Medicine’s Department of Surgery. She studied operations research at Stanford University and M.I.T. Her research is in optimization and simulation for improving transplantation and organ allocation policy. She designed optimization methods used for nationwide kidney paired donation registries in both the United States and Canada. She is a recipient of the Mathematical Association of America's Alder Award for distinguished teaching by a beginning college or university mathematics faculty member.