Networks, Crowds, and Markets: Reasoning about a Highly Connected World

Post date: Sep 15, 2011 9:50:11 PM

As complex systems made of individual nodes connected by links, networks are behind many natural and artificial phenomena. So, it comes as no surprise that scientists from different disciplines try to understand how connected systems work. This book is a recent addition to the growing collection of recent textbooks that deal with networks [1,2,3], with substantial overlap among them. While these others try to understand networks by mainly focusing on the mathematical [1], algorithmic [2], or game-theoretic [3] aspects of existing models, Easley and Kleinberg survey the field with a strong emphasis on connecting models to real-world situations. This is partially due to the book’s origin: an undergraduate course at Cornell University. Hence, mathematical details have been stripped away, whenever possible, and algorithmic considerations are almost missing.

It is, however, an excellent introductory textbook. The 24 chapters are organized into seven blocks that correspond to its central themes. Most chapters include optional sections at the end, with advanced material that would not typically be taught in a standard undergraduate one-semester course. They also include lists of exercises, most of which are quite mechanical, intended to acquaint students with the material covered in each chapter (generally, you can find more demanding problems and open questions in Newman’s book [1]).

After the usual introductory overview chapter, the first block of chapters starts the study of network structure by introducing graph theory and some key topics related to social networks. An easy-to-understand nontechnical introduction to graph theory is followed by a nice treatment of strong and weak ties in social networks, key structural metrics (such as clustering coefficient and betweenness), external factors that affect link formation (such as homophily and affiliation), and the stability of positive and negative relationships (structural balance).

The second part of the book introduces game theory as a key tool to model interdependence in the behavior of individuals. Like the rest of the book, it is written clearly and provides many intuitive examples that highlight the key issues discussed in each section. Modeling traffic through a network and auctions are discussed as two interesting applications of game theory that sometimes lead to counterintuitive conclusions (for example, Braess’ paradox, which states that adding capacity to a network can sometimes slow down the traffic).

A third block of chapters combines the material from the previous two, from an economic point of view. A preliminary chapter on matching markets sets the stage; without taking network structure into account, it focuses on optimal assignments and market-clearing prices. Later, trading networks--markets with intermediaries--and network exchange theory receive their deserved share of attention, as they model the natural convergence of network structure (graphs) and strategic interaction (games).

The fourth part of the book changes its application domain. This time, the focus of study is information networks and the World Wide Web (WWW). In less than 100 pages, readers learn about the bow-tie structure of the Web, the link analysis algorithms used in Web searches (such as Kleinberg’s HITS algorithms and Google’s PageRank), and the sponsored search markets at the heart of keyword-based advertising.

The fifth and sixth blocks of chapters turn their attention to network dynamics. They study situations in which a person’s behavior and decisions depend on other individuals’ choices. First, they are studied for their aggregate effects, such as information cascades and the rich-get-richer phenomena. For instance, readers will learn that the so-called “wisdom of crowds” does not always produce accurate results, due to network effects. The second set of chapters on network dynamics analyzes how individuals are influenced by their neighbors. Taking a closer look at the fine structure of the network, readers can study social contagion as a rational decision-making process (with the help of threshold models) and epidemics as a probabilistic random process (with the help of standard SIR/SIS models). The small-world phenomenon is also studied in its own chapter, due to its importance for finding short paths and performing decentralized searches.

The final set of chapters deals with key societal institutions. They are not typical network topics, but they are often taught in multiagent systems courses [4]. However, their importance is clear when you take into account how their design can produce different forms of aggregate behavior in connected systems. In particular, the authors discuss the ways in which markets serve to aggregate individual beliefs (information asymmetry in markets), how to reach a single decision (voting mechanisms), and how to allocate resources (property rights).

This unusual range of topics is what makes this book invaluable. Instead of just focusing on abstract mathematical models and their formal properties, it puts models in their proper place within a process that begins with empirical observations, leads to mathematical models, is followed by some predictions, and is then subject to experimental validation that starts the cycle anew. In the meantime, one reasons about the connected world around us, discovers some facts, gets some insight into the behavior of complex systems, and even enjoys some “aha!” moments. The book is a pleasure to read.

Reviewer: Fernando Berzal

Review #: CR138598 (1107-0698)

1)

2)

3)

4)

Newman, M.E.J., Networks: An Introduction. Oxford University Press, New York, NY, 2010.

Lewis, T.G. Network Science: Theory and Applications. John Wiley and Sons, Inc., Hoboken, NJ, 2009.

Jackson, M.O. Social and Economic Networks. Princeton University Press, Princeton, NJ, 2008.

Shoham, Y.; Leyton-Brown, K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, New York, NY, 2008.

También disponible en