Punchline algebra book b 14.3 answers

http://www.cambridge.org/9780521195331

Networks, Crowds, and Markets

Over the past decade there has been a growing public fascination with the complex connect- edness of modern society. This connectedness is found in many incarnations: in the rapid growth of the Internet, in the ease with which global communication takes place, and in the ability of news and information as well as epidemics and financial crises to spread with surprising speed and intensity. These are phenomena that involve networks, incentives, and the aggregate behavior of groups of people; they are based on the links that connect us and the ways in which our decisions can have subtle consequences for others.

This introductory undergraduate textbook takes an interdisciplinary look at economics, sociology, computing and information science, and applied mathematics to understand net- works and behavior. It describes the emerging field of study that is growing at the interface of these areas, addressing fundamental questions about how the social, economic, and tech- nological worlds are connected.

David Easley is the Henry Scarborough Professor of Social Science and the Donald C. Opatrny ’74 Chair of the Department of Economics at Cornell University. He was previ- ously an Overseas Fellow of Churchill College, Cambridge. His research is in the fields of economics, finance, and decision theory. In economics, he focuses on learning, wealth dynamics, and natural selection in markets. In finance, his work focuses on market mi- crostructure and asset pricing. In decision theory, he works on modeling decision making in complex environments. He is a Fellow of the Econometric Society and is Chair of the NASDAQ-OMX Economic Advisory Board.

Jon Kleinberg is the Tisch University Professor in the Computer Science Department at Cornell University. He is a member of the National Academy of Engineering and the American Academy of Arts and Sciences. His research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other online media. He is the recipient of MacArthur, Packard, and Sloan Foundation Fellowships; the Nevanlinna Prize; the ACM-Infosys Foundation Award; and the National Academy of Sciences Award for Initiatives in Research.

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

David Easley Cornell University

Jon Kleinberg Cornell University

CAMBRIDGE UNIVERSITY PRESS

Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore,

São Paulo, Delhi, Dubai, Tokyo

Cambridge University Press

The Edinburgh Building, Cambridge CB2 8RU, UK

First published in print format

ISBN-13 978-0-521-19533-1

ISBN-13 978-0-511-77675-5

© David Easley and Jon Kleinberg 2010

2010

Information on this title: www.cambridge.org/9780521195331

This publication is in copyright. Subject to statutory exception and to the

provision of relevant collective licensing agreements, no reproduction of any part

may take place without the written permission of Cambridge University Press.

Cambridge University Press has no responsibility for the persistence or accuracy

of urls for external or third-party internet websites referred to in this publication,

and does not guarantee that any content on such websites is, or will remain,

accurate or appropriate.

Published in the United States of America by Cambridge University Press, New York

www.cambridge.org

eBook (NetLibrary)

Hardback

http://www.cambridge.org
http://www.cambridge.org/9780521195331
Contents

Preface page xi

1 Overview 1 1.1 Aspects of Networks 2 1.2 Central Themes and Topics 7

Part I Graph Theory and Social Networks

2 Graphs 21 2.1 Basic Definitions 21 2.2 Paths and Connectivity 23 2.3 Distance and Breadth-First Search 29 2.4 Network Data Sets: An Overview 35 2.5 Exercises 39

3 Strong and Weak Ties 43 3.1 Triadic Closure 44 3.2 The Strength of Weak Ties 46 3.3 Tie Strength and Network Structure in Large-Scale Data 51 3.4 Tie Strength, Social Media, and Passive Engagement 54 3.5 Closure, Structural Holes, and Social Capital 58 3.6 Advanced Material: Betweenness Measures and Graph Partitioning 62 3.7 Exercises 74

4 Networks in Their Surrounding Contexts 77 4.1 Homophily 77 4.2 Mechanisms Underlying Homophily: Selection and Social Influence 81 4.3 Affiliation 83 4.4 Tracking Link Formation in Online Data 88 4.5 A Spatial Model of Segregation 96 4.6 Exercises 103

v

vi contents

5 Positive and Negative Relationships 107 5.1 Structural Balance 107 5.2 Characterizing the Structure of Balanced Networks 110 5.3 Applications of Structural Balance 113 5.4 A Weaker Form of Structural Balance 115 5.5 Advanced Material: Generalizing the Definition of Structural Balance 118 5.6 Exercises 132

Part II Game Theory

6 Games 139 6.1 What Is a Game? 140 6.2 Reasoning about Behavior in a Game 142 6.3 Best Responses and Dominant Strategies 146 6.4 Nash Equilibrium 149 6.5 Multiple Equilibria: Coordination Games 151 6.6 Multiple Equilibria: The Hawk–Dove Game 154 6.7 Mixed Strategies 156 6.8 Mixed Strategies: Examples and Empirical Analysis 161 6.9 Pareto Optimality and Social Optimality 165

6.10 Advanced Material: Dominated Strategies and Dynamic Games 167 6.11 Exercises 179

7 Evolutionary Game Theory 189 7.1 Fitness as a Result of Interaction 190 7.2 Evolutionarily Stable Strategies 191 7.3 A General Description of Evolutionarily Stable Strategies 196 7.4 Relationship between Evolutionary and Nash Equilibria 197 7.5 Evolutionarily Stable Mixed Strategies 199 7.6 Exercises 204

8 Modeling Network Traffic Using Game Theory 207 8.1 Traffic at Equilibrium 207 8.2 Braess’s Paradox 209 8.3 Advanced Material: The Social Cost of Traffic at Equilibrium 211 8.4 Exercises 219

9 Auctions 225 9.1 Types of Auctions 225 9.2 When Are Auctions Appropriate? 226 9.3 Relationships between Different Auction Formats 228 9.4 Second-Price Auctions 229 9.5 First-Price Auctions and Other Formats 232 9.6 Common Values and the Winner’s Curse 233 9.7 Advanced Material: Bidding Strategies in First-Price and All-Pay

Auctions 234 9.8 Exercises 242

contents vii

Part III Markets and Strategic Interaction in Networks

10 Matching Markets 249 10.1 Bipartite Graphs and Perfect Matchings 249 10.2 Valuations and Optimal Assignments 253 10.3 Prices and the Market-Clearing Property 255 10.4 Constructing a Set of Market-Clearing Prices 258 10.5 How Does This Relate to Single-Item Auctions? 261 10.6 Advanced Material: A Proof of the Matching Theorem 262 10.7 Exercises 270

11 Network Models of Markets with Intermediaries 277 11.1 Price Setting in Markets 277 11.2 A Model of Trade on Networks 280 11.3 Equilibria in Trading Networks 286 11.4 Further Equilibrium Phenomena: Auctions and Ripple Effects 290 11.5 Social Welfare in Trading Networks 294 11.6 Trader Profits 295 11.7 Reflections on Trade with Intermediaries 297 11.8 Exercises 297

12 Bargaining and Power in Networks 301 12.1 Power in Social Networks 301 12.2 Experimental Studies of Power and Exchange 304 12.3 Results of Network Exchange Experiments 305 12.4 A Connection to Buyer–Seller Networks 309 12.5 Modeling Two-Person Interaction: The Nash Bargaining Solution 310 12.6 Modeling Two-Person Interaction: The Ultimatum Game 312 12.7 Modeling Network Exchange: Stable Outcomes 314 12.8 Modeling Network Exchange: Balanced Outcomes 317 12.9 Advanced Material: A Game-Theoretic Approach to Bargaining 320

12.10 Exercises 327

Part IV Information Networks and the World Wide Web

13 The Structure of the Web 333 13.1 The World Wide Web 333 13.2 Information Networks, Hypertext, and Associative Memory 335 13.3 The Web as a Directed Graph 340 13.4 The Bow-Tie Structure of the Web 344 13.5 The Emergence of Web 2.0 347 13.6 Exercises 349

14 Link Analysis and Web Search 351 14.1 Searching the Web: The Problem of Ranking 351 14.2 Link Analysis Using Hubs and Authorities 353 14.3 PageRank 358

viii contents

14.4 Applying Link Analysis in Modern Web Search 363 14.5 Applications beyond the Web 366 14.6 Advanced Material: Spectral Analysis, Random Walks, and Web

Search 368 14.7 Exercises 378

15 Sponsored Search Markets 385 15.1 Advertising Tied to Search Behavior 385 15.2 Advertising as a Matching Market 388 15.3 Encouraging Truthful Bidding in Matching Markets: The VCG

Principle 391 15.4 Analyzing the VCG Mechanism: Truth-Telling as a Dominant

Strategy 395 15.5 The Generalized Second-Price Auction 398 15.6 Equilibria of the Generalized Second-Price Auction 401 15.7 Ad Quality 404 15.8 Complex Queries and Interactions among Keywords 406 15.9 Advanced Material: VCG Prices and the Market-Clearing Property 407

15.10 Exercises 420

Part V Network Dynamics: Population Models

16 Information Cascades 425 16.1 Following the Crowd 425 16.2 A Simple Herding Experiment 427 16.3 Bayes’ Rule: A Model of Decision Making under Uncertainty 430 16.4 Bayes’ Rule in the Herding Experiment 434 16.5 A Simple, General Cascade Model 436 16.6 Sequential Decision Making and Cascades 440 16.7 Lessons from Cascades 442 16.8 Exercises 444

17 Network Effects 449 17.1 The Economy without Network Effects 450 17.2 The Economy with Network Effects 453 17.3 Stability, Instability, and Tipping Points 456 17.4 A Dynamic View of the Market 457 17.5 Industries with Network Goods 462 17.6 Mixing Individual Effects with Population-Level Effects 465 17.7 Advanced Material: Negative Externalities and the El Farol Bar

Problem 470 17.8 Exercises 476

18 Power Laws and Rich-Get-Richer Phenomena 479 18.1 Popularity as a Network Phenomenon 479 18.2 Power Laws 481 18.3 Rich-Get-Richer Models 482

contents ix

18.4 The Unpredictability of Rich-Get-Richer Effects 484 18.5 The Long Tail 486 18.6 The Effect of Search Tools and Recommendation Systems 489 18.7 Advanced Material: Analysis of Rich-Get-Richer Processes 490 18.8 Exercises 493

Part VI Network Dynamics: Structural Models

19 Cascading Behavior in Networks 497 19.1 Diffusion in Networks 497 19.2 Modeling Diffusion through a Network 499 19.3 Cascades and Clusters 506 19.4 Diffusion, Thresholds, and the Role of Weak Ties 509 19.5 Extensions of the Basic Cascade Model 512 19.6 Knowledge, Thresholds, and Collective Action 514 19.7 Advanced Material: The Cascade Capacity 517 19.8 Exercises 532

20 The Small-World Phenomenon 537 20.1 Six Degrees of Separation 537 20.2 Structure and Randomness 538 20.3 Decentralized Search 541 20.4 Modeling the Process of Decentralized Search 543 20.5 Empirical Analysis and Generalized Models 546 20.6 Core–Periphery Structures and Difficulties in Decentralized Search 552 20.7 Advanced Material: Analysis of Decentralized Search 554 20.8 Exercises 564

21 Epidemics 567 21.1 Diseases and the Networks That Transmit Them 567 21.2 Branching Processes 569 21.3 The SIR Epidemic Model 572 21.4 The SIS Epidemic Model 576 21.5 Synchronization 578 21.6 Transient Contacts and the Dangers of Concurrency 582 21.7 Genealogy, Genetic Inheritance, and Mitochondrial Eve 585 21.8 Advanced Material: Analysis of Branching and Coalescent Processes 590 21.9 Exercises 602

Part VII Institutions and Aggregate Behavior

22 Markets and Information 607 22.1 Markets with Exogenous Events 608 22.2 Horse Races, Betting, and Beliefs 609 22.3 Aggregate Beliefs and the “Wisdom of Crowds” 615 22.4 Prediction Markets and Stock Markets 618 22.5 Markets with Endogenous Events 622

x contents

22.6 The Market for Lemons 623 22.7 Asymmetric Information in Other Markets 627 22.8 Signaling Quality 631 22.9 Quality Uncertainty Online: Reputation Systems and Other

Mechanisms 632 22.10 Advanced Material: Wealth Dynamics in Markets 635 22.11 Exercises 641

23 Voting 645 23.1 Voting for Group Decision Making 645 23.2 Individual Preferences 646 23.3 Voting Systems: Majority Rule 649 23.4 Voting Systems: Positional Voting 654 23.5 Arrow’s Impossibility Theorem 657 23.6 Single-Peaked Preferences and the Median Voter Theorem 658 23.7 Voting as a Form of Information Aggregation 663 23.8 Insincere Voting for Information Aggregation 665 23.9 Jury Decisions and the Unanimity Rule 668

23.10 Sequential Voting and the Relation to Information Cascades 672 23.11 Advanced Material: A Proof of Arrow’s Impossibility Theorem 673 23.12 Exercises 678

24 Property Rights 681 24.1 Externalities and the Coase Theorem 681 24.2 The Tragedy of the Commons 685 24.3 Intellectual Property 688 24.4 Exercises 691

Bibliography 693 Index 711

Preface

Over the past decade, there has been a growing public fascination with the complex “connectedness” of modern society. This connectedness is found in many incarnations: in the rapid growth of the Internet and the Web, in the ease with which global communi- cation now takes place, and in the ability of news and information as well as epidemics and financial crises to spread around the world with surprising speed and intensity. These are phenomena that involve networks, incentives, and the aggregate behavior of groups of people; they are based on the links that connect us and the ways in which each of our decisions can have subtle consequences for the outcomes of everyone else.

Motivated by these developments in the world, there has been a coming-together of multiple scientific disciplines in an effort to understand how highly connected systems operate. Each discipline has contributed techniques and perspectives that are characteristically its own, and the resulting research effort exhibits an intriguing blend of these different flavors. From computer science and applied mathematics has come a framework for reasoning about how complexity arises, often unexpectedly, in systems that we design; from economics has come a perspective on how people’s behavior is affected by incentives and by their expectations about the behavior of others; and from sociology and the social sciences have come insights into the characteristic structures and interactions that arise within groups and populations. The resulting synthesis of ideas suggests the beginnings of a new area of study, focusing on the phenomena that take place within complex social, economic, and technological systems.

This book grew out of a course that we developed at Cornell, designed to introduce this topic and its underlying ideas to a broad student audience at an introductory level. The central concepts are fundamental and accessible ones, but they are dispersed across the research literatures of the many different fields contributing to the topic. The principal goal of this book is therefore to bring the essential ideas together in a single unified treatment and to present them in a way that requires as little background knowledge as possible.

xi

xii preface

Overview. The book is intended to be used at the introductory undergraduate level, and as such it has no formal prerequisites beyond a level of comfort with basic mathematical definitions at a precalculus level. In keeping with the introductory style, many of the ideas are developed in special cases and through illustrative examples; our goal is to take concepts and theories that are complex in their full generality and to provide simpler formulations where the essential ideas still come through.

In our use of the book, we find that many students are also interested in pursuing some of these topics more deeply, and so it is useful to provide pathways that lead from the introductory formulations into the more advanced literature on these topics. With this in mind, we provide optional sections labeled Advanced Material at the ends of most chapters. These advanced sections are qualitatively different from the other sections in the book; some draw on more advanced mathematics, and their presentation is at a more challenging level of conceptual complexity. Aside from the additional mathematical background required, however, even these advanced sections are self- contained; they are also strictly optional, in the sense that nothing elsewhere in the book depends on them.

Synopsis. The first chapter of the book provides a detailed description of the topics and issues that we cover. Here we give a briefer summary of the main focus areas.

The book is organized into seven parts of three to four chapters each. Parts I and II discuss the two main theories that underpin our investigations of networks and behavior: graph theory, which studies network structure, and game theory, which formulates models of behavior in environments where people’s decisions affect each other’s outcomes. Part III integrates these lines of thought into an analysis of the network structure of markets and the notion of power in such networks. Part IV pursues a different integration, discussing the World Wide Web as an information network, the problem of Web search, and the development of the markets that currently lie at the heart of the search industry. Parts V and VI study the dynamics of some of the fundamental processes that take place within networks and groups, including the ways in which people are influenced by the decisions of others. Part V pursues this topic at an aggregate scale, where we model interactions between an individual and the population as a whole. Part VI continues the analysis at the more fine-grained level of network structure, beginning with the question of influence and moving on to the dynamics of search processes and epidemics. Finally, Part VII considers how we can interpret fundamental social institutions – including markets, voting systems, and property rights – as mechanisms for productively shaping some of the phenomena we’ve been studying.

Use of the Book. The book is designed for teaching as well as for any reader who finds these topics interesting and wants to pursue them independently at a deeper level.

Several different types of courses can be taught from this book. When we teach from it at Cornell, the students in our class come from many different majors and have a wide variety of technical backgrounds; this diversity in the audience has served as our primary calibration in setting the introductory level of the book. Our course includes a portion of the material from each chapter; for the sake of concreteness, we provide the approximate weekly schedule we follow below. (There are three 50-minute lectures

preface xiii

each week, except that weeks 6 and 7 of our course contain only two lectures each. In each lecture, we don’t necessarily include all the details from each indicated section.)

Week 1: Chapters 1; 2.1–2.3; 3.1–3.3, 3.5; 4.1 Week 2: Chapters 5.1–5.3; 6.1–6.4; 6.5–6.9 Week 3: Chapters 8.1–8.2; 9.1–9.6; 10.1–10.2 Week 4: Chapters 10.3; 10.4–10.5; 11.1–11.2 Week 5: Chapters 11.3–11.4; 12.1–12.3; 12.5–12.6 Week 6: Chapters 12.7–12.8; 13 Week 7: Chapter 14.1–14.2; 14.3–14.4 Week 8: Chapter 15.1–15.2; 15.3–15.4; 15.5–15.6, 15.8 Week 9: Chapter 16.1–16.2; 16.3–16.4; 16.5–16.7 Week 10: Chapters 17.1–17.2; 17.3–17.5; 18 Week 11: Chapters 19.1–19.2; 19.3; 19.4, 19.6 Week 12: Chapter 22.1–22.4; 22.5–22.9; 7.1–7.4 Week 13: Chapters 20.1–20.2; 20.3–20.6; 21.1–21.5 Week 14: Chapters 23.1–23.5; 23.6–23.9; 24

There are many other paths that a course could follow through the book. First, a number of new courses are being developed at the interface of computer science and economics, focusing particularly on the role of economic reasoning in the design and behavior of modern computing systems. The book can be used for such courses in several ways, building on four chapters as a foundation: Chapter 2 on graphs, Chapter 6 on games, Chapter 9 on auctions, and Chapter 10 on matching markets. From here, a more expansive version of such a course could cover the remainder of Parts II and III, all of Parts IV and V, Chapter 19, and portions of Part VII. A more focused and potentially shorter version of such a course concerned principally with auctions, markets, and the online applications of these ideas could be constructed from Chapters 2, 6, 9, 10, 13, 15, 17, 18, and 22, and drawing on parts of Chapters 11, 12, 14, 16, and 19. When these courses are taught at a more advanced level, the advanced sections at the ends of most of these chapters would be appropriate material; depending on the exact level of the course, the text of many of these chapters could be used to lead into the more advanced analysis in their respective final sections.

In a different but related direction, new courses are also being developed on the topic of social computing and information networks. The book can be used for courses of this type by emphasizing Chapters 2–6, 13, 14, 17–20, and 22; many such courses also include sponsored search markets as part of their coverage of the Web, which can be done by including Chapters 9, 10, and 15 as well. The advanced sections in the book can play a role here too, depending on the level of the course.

Finally, portions of the book can serve as self-contained modules in courses on broader topics. To pick just a few examples, one can assemble such modules on network algorithms (Sections 2.3, 3.6, 5.5, 8.3, 10.6, 14.2, 14.3, 14.6, 15.9, 20.3, 20.4, and 20.7); applications of game theory (Chapters 6–9 and 11; Sections 12.9, 15.3– 15.6, 19.2, 19.3, 19.5–19.7, and 23.7–23.9); social network analysis (Chapters 2–5; Sections 12.1–12.3 and 12.5–12.8; and Chapters 18–20); the role of information in economic settings (Chapters 16 and 22, and Sections 23.6–23.10); and the analysis of large-scale network data sets (Sections 2.3, 3.2, 3.3, 3.6, 4.4, 5.3, 13.3, 13.4, 14.2–14.5, 18.2, 18.5, and 20.5). Most of these modules use graphs and/or games as fundamental

xiv preface

building blocks; for students not already familiar with these topics, Chapters 2 and 6, respectively, provide self-contained introductions.

Acknowledgments. Our work on this book took place in an environment at Cornell that was particularly conducive to interaction between computing and the social sciences. Our collaboration began as part of a project with Larry Blume, Eric Friedman, Joe Halpern, Dan Huttenlocher, and Éva Tardos funded by the National Science Foundation, followed by a campus-wide “theme project” on networks sponsored by Cornell’s Institute for the Social Sciences, with a group that included Larry and Dan together with John Abowd, Geri Gay, Michael Macy, Kathleen O’Connor, Jeff Prince, and David Strang. Our approach to the material in the book draws on perspectives – ways of thinking about these topics and ways of talking about them – that we’ve learned and acquired from this interdisciplinary set of colleagues, a group that includes some of our closest professional collaborators.

The course on which the book is based grew out of discussions that were part of the Cornell theme project; the two of us had taught distinct portions of this material separately in graduate courses that we had developed, and Michael Kearns’s Networked Life course at University of Pennsylvania demonstrated the vibrancy and relevance this material could have for an introductory undergraduate audience as well. We were intrigued by the prospect of combining different perspectives that hadn’t previously appeared together – a process that would be educational not only to the students in the course but to us as well. Creating and teaching this new interdisciplinary course was made possible by the support of our departments, Computer Science and Economics, and by support from the Solomon Fund at Cornell University.

Once the book had begun to take shape, we benefited enormously from the feed- back, suggestions, and experiences of colleagues who taught from early drafts of it. In particular, we thank Daron Acemoglu (MIT), Lada Adamic (Michigan), Allan Borodin (Toronto), Noshir Contractor (Northwestern), Jason Hartline (Northwestern), Nicole Immorlica (Northwestern), Ramesh Johari (Stanford), Samir Khuller (Mary- land), Jure Leskovec (Stanford), David Liben-Nowell (Carleton), Peter Monge (USC), Asu Ozdaglar (MIT), Vijay Ramachandran (Colgate), R. Ravi (CMU), Chuck Sev- erance (Michigan), Aravind Srinivasan (Maryland), and Luis von Ahn (CMU). The graduate and undergraduate teaching assistants in our own teaching of this subject have been very helpful as well; we thank Alex Ainslie, Lars Backstrom, Jacob Bank, Vlad Barash, Burak Bekdemir, Anand Bhaskar, Ben Cole, Bistra Dilkina, Eduard Dog- aru, Ram Dubey, Ethan Feldman, Ken Ferguson, Narie Foster, Eric Frackleton, Christie Gibson, Vaibhav Goel, Scott Grabnic, Jon Guarino, Fahad Karim, Koralai Kirabaeva, Tian Liang, Austin Lin, Fang Liu, Max Mihm, Sameer Nurmohamed, Ben Pu, Tal Rusak, Mark Sandler, Stuart Tettemer, Ozgur Yonter, Chong-Suk Yoon, and Yisong Yue.

In addition to the instructors who used early drafts, a number of other people provided extensive comments on portions of the book, leading to many improvements in the text: Lada Adamic, Robert Kerr, Evie Kleinberg, Gueorgi Kossinets, Stephen Morris, David Parkes, Rahul Sami, Andrew Tomkins, and Johan Ugander. We also thank a further set of colleagues, in addition to those already listed, who have provided very useful advice

preface xv

and suggestions on this project as it has proceeded: Bobby Kleinberg, Gene Kleinberg, Lillian Lee, Maureen O’Hara, Prabhakar Raghavan, and Steve Strogatz.

It has been a pleasure to be able to work with the editorial team at Cambridge University Press. Lauren Cowles, our main point of contact at Cambridge, has been an amazing source of advice and help, and we likewise very much appreciate the contributions of Scott Parris and David Tranah to this project, and Peggy Rote and her colleagues at Aptara for their work on the production of the book.

Finally, a profound thanks goes to our families, in continuing appreciation of their support and many other contributions.

David Easley Jon Kleinberg Ithaca, 2010

CHAPTER 1

Overview

The past decade has seen a growing public fascination with the complex “connected- ness” of modern society. At the heart of this fascination is the idea of a network – a pattern of interconnections among a set of things – and one finds networks appearing in discussion and commentary on an enormous range of topics. The diversity of con- texts in which networks are invoked is in fact so vast that it’s worth deferring precise definitions for a moment while we first recount a few of the more salient examples.

To begin with, the social networks we inhabit – the collections of social ties among friends – have grown steadily in complexity over the course of human history, due to technological advances facilitating distant travel, global communication, and digital interaction. The past half-century has seen these social networks depart even more radically from their geographic underpinnings – an effect that has weakened the tradi- tionally local nature of such structures but enriched them in other dimensions.

The information we consume has a similarly networked structure: these structures too have grown in complexity, as a landscape with a few purveyors of high-quality information (publishers, news organizations, the academy) has become crowded with an array of information sources of wildly varying perspectives, reliabilities, and motivating intentions. Understanding any one piece of information in this environment depends on understanding the way it is endorsed by and refers to other pieces of information within a large network of links.

Our technological and economic systems have also become dependent on networks of enormous complexity. This has made the behavior of these systems increasingly difficult to reason about and increasingly risky to tinker with. It has made them suscep- tible to disruptions that spread through the underlying network structures, sometimes turning localized breakdowns into cascading failures or financial crises.

The imagery of networks has made its way into many other lines of discussion as well: Global manufacturing operations now have networks of suppliers, Web sites have networks of users, and media companies have networks of advertisers. In such formulations, the emphasis is often less on the structure of the network itself than on its complexity as a large, diffuse population that reacts in unexpected ways to the actions of central authorities. The terminology of international conflict has come to reflect this

1

2 overview

27 15

23

10 20

4 13

16

34 31

14

12

18

17

30

33

32

9

2

1

5

6

21

24

25

3

8

22

11

7

19 28

29

26

Figure 1.1. The social network of friendships within a 34-person karate club [421]. (Drawing from the Journal of Anthropological Research.)

as well: for example, the picture of two opposing, state-supported armies gradually morphs, in U.S. presidential speeches, into images of a nation facing “a broad and adaptive terrorist network” [296] or “at war against a far-reaching network of violence and hatred” [328].

1.1 Aspects of Networks

How should we think about networks, at a more precise level, to bring all these issues together? In the most basic sense, a network is any collection of objects in which some pairs of these objects are connected by links. This definition is very flexible: depending on the setting, many different forms of relationships or connections can be used to define links.

Because of this flexibility, it is easy to find networks in many domains, including the ones we’ve just been discussing. As a first example of what a network looks like, Figure 1.1 depicts the social network among thirty-four people in a university karate club studied by the anthropologist Wayne Zachary in the 1970s. The people are represented by small circles, and lines join the pairs of people who are friends outside the context of the club. This is the typical way in which networks will be drawn in this book, with lines joining the pairs of objects that are connected by links.

Later in this chapter we’ll discuss some of the things one can learn from a network such as the one in Figure 1.1, as well as from larger examples such as the ones shown in Figures 1.2–1.4. These larger examples depict e-mail exchanges among employees of a company (Figure 1.2); loans among financial institutions (Figure 1.3); and links among blogs on the Web (Figure 1.4). In each case, links indicate the pairs that are connected (specifically, people connected by e-mail exchange, financial institutions by a borrower–lender relationship, and blogs via a link on the Web from one to the other, respectively).

aspects of networks 3

Figure 1.2. Social networks based on communication and interaction can be constructed from the traces left by online data. In this case, the pattern of e-mail communication among 436 employees of the Hewlett Packard Research Lab is superimposed on the offi- cial organizational hierarchy [6]. (Image from http://www-personal.umich.edu/ladamic/img/ hplabsemailhierarchy.jpg, courtesy of Elsevier Science and Technology Journals.)

GSCC

GWCC

Tendril

DC

GOUT GIN

Figure 1.3. The network of loans among financial institutions can be used to analyze the roles that different participants play in the financial system and how the interactions among these roles affect the health of individual participants and the system as a whole. The network is annotated in a way that reveals its dense core, according to a scheme that we describe in Chapter 13. (Image from Bech and Atalay, [50].)

4 overview

Figure 1.4. The links among Web pages can reveal densely knit communities and prominent sites. In this case, the network structure of political blogs prior to the 2004 U.S. presiden- tial election reveals two natural and well-separated clusters [5]. (Image from Association for Computing Machinery, Inc.; http://www-personal.umich.edu/ ladamic/img/politicalblogs.jpg.)

Simply from their visual appearance, we can already see some of the complexity inherent in network structures. It is generally difficult to summarize succinctly the whole network; some parts are more or less densely interconnected, sometimes with central “cores” containing most of the links and sometimes with natural splits into multiple tightly-linked regions. Participants in the network can be more central or more peripheral; they can straddle the boundaries of different tightly-linked regions or sit squarely in the middle of one. Developing a language for talking about the typical structural features of networks is an important first step in understanding them.

Behavior and Dynamics. But the structure of the network is only a starting point. When people talk about the “connectedness” of a complex system, in general they are really talking about two related issues. One is connectedness at the level of structure – who is linked to whom – and the other is connectedness at the level of behavior – the fact that each individual’s actions have implicit consequences for the outcomes of everyone in the system.

This means that, in addition to a language for discussing the structure of networks, we also need a framework for reasoning about behavior and interaction in network contexts. And just as the underlying structure of a network can be complex, so too can the coupled behavior of its inhabitants. If individuals have strong incentives to achieve good outcomes, then they not only will appreciate that their outcomes depend on how others behave, but they also take this into account in planning their own actions.

aspects of networks 5

Search volume for YouTube

1.0

2006 2007 2008

2.0

Google Trends

Figure 1.5. The rapidly growing popularity of YouTube is characteristic of the way in which new products, technologies, or innovations rise to prominence through feedback effects in the behavior of many individuals across a population. The plot depicts the number of Google queries for YouTube over time. The image comes from the site Google Trends (http://www.google.com/trends?q=youtube); by design, the units on the y-axis are suppressed in the output from this site.

As a result, models of networked behavior must take strategic behavior and strategic reasoning into account.

A fundamental point here is that, in a network setting, you should evaluate your actions not in isolation but with the expectation that the world will react to what you do. This means that cause-and-effect relationships can become quite subtle. Changes in a product, a Web site, or a government program can seem like good ideas when evaluated using the assumption that everything else will remain static, but in reality such changes can easily create incentives that shift behavior across the network in ways that were initially unintended.

Moreover, such effects are at work whether we are able to see the network or not. When a large group of people is tightly interconnected, these people often respond in complex ways that are only apparent at the population level, even though these effects may come from implicit networks that we do not directly observe. Consider, for ex- ample, the way in which new products, Web sites, or celebrities rise to prominence (as illustrated, for example, by Figures 1.5 and 1.6, which show the growth in popularity

1.0

2005 2006 2007 2008

Search volume for Flickr

2.0

Google Trends

Figure 1.6. This companion to Figure 1.5 shows the rise of the social media site Flickr; the growth in popularity has a very similar pattern to that of other sites, including YouTube. (Image from Google Trends, http://www.google.com/trends?q=flickr.)

6 overview

of the social media sites YouTube and Flickr, respectively, over the past several years). What we see in these figures is a growing awareness and adoption of a new innova- tion that is visible in aggregate, across a whole population. What are the underlying mechanisms that lead to such success? Standard refrains are often invoked in these sit- uations: the rich get richer, winners take all, small advantages are magnified to a critical mass, and new ideas get attention that becomes “viral.” But the rich don’t always get richer and small advantages don’t always lead to success. Some social networking sites flourish, like Facebook, while others, like SixDegrees.com, vanish. To understand how these processes work and how they are realized through the interconnected actions of many people, we need to study the dynamics of aggregate behavior.

A Confluence of Ideas. Understanding highly connected systems, then, requires a set of ideas for reasoning about network structure, strategic behavior, and the feedback effects they produce across large populations. These are ideas that have traditionally been dispersed across many different disciplines. However, in parallel with the increas- ing public interest in networks, there has been a coming-together of scientific fields around the topic of network research. Each of these fields brings important ideas to the discussion, and a full understanding seems to require a synthesis of perspectives from all of them.

One of the central goals in this book is to help bring about such a synthesis, by combining approaches that have traditionally been pursued separately. From computer science, applied mathematics, and operations research we draw on a language for talking about the complexity of network structure, information, and systems with interacting agents. From economics we draw on models for the strategic behavior of individuals who interact with each other and operate as members of larger aggregates. From sociology – particularly the more mathematical aspects concerned with social networks – we draw on a broad set of theoretical frameworks for talking about the structure and dynamics of social groups.

And the overall picture can help fill in pieces that are arguably missing from the intellectual landscape of each of these disciplines. Economics has developed rich theories for the strategic interaction among small numbers of parties, as well as for the cumulative behavior of large, homogeneous populations. The challenge is that much of economic life takes place in the complex spectrum between these extremes, with macroscopic effects that arise from an intricate pattern of localized interactions. Sociology has developed some of the fundamental insights into the structure of social networks, but its network methodology has been refined in the domains and scales where data collection has traditionally been possible – primarily, well-defined groups with tens to hundreds of people. The explosion of new contexts in which we find network data and network applications – including enormous, digitally mediated ones – leads to new opportunities for how we can pose questions, formulate theories, and evaluate predictions about social networks. Computer science, with the rise of the Web and social media, has had to deal with a world in which the design constraints on large computing systems are not just technological but also human – imposed by the complex feedback effects that human audiences create when they collectively use the Web for communication, self-expression, and the creation of knowledge. A fully satisfactory theory of network structure and behavior has the potential to address the simultaneous challenges encountered by all these fields.

central themes and topics 7

A recurring theme underlying these challenges is the way in which networks span many different levels of scale and resolution. There are interesting questions that reach from the scale of small groups, such as the thirty-four–person social network in Figure 1.1, all the way up to the level of whole societies or economies, or to the body of global knowledge represented by the Web. In this book we examine networks both at the level of explicit structures, like those in Figures 1.1–1.4, and at the level of aggregate effects, like the popularity curves in Figures 1.5 and 1.6. As we look at networks of increasing scales, it becomes correspondingly more appropriate to take aggregate models into account. But the ability to work with massive network data sets has also enriched the picture, making it possible to study networks with billions of interacting items at a level of resolution where each connection is recorded. When an Internet search engine identifies the most useful pages from an index of the entire Web, for example, it is doing precisely this in the context of a specific task. Ultimately, it is an ongoing and challenging scientific problem to bridge these vastly different levels of scale so that predictions and principles from one level can be reconciled with those of others.

1.2 Central Themes and Topics

With this set of ideas in mind, we now introduce some of the main topics considered in this book and the ways in which these topics reinforce the underlying principles of networks. We begin with the two main bodies of theory that we will be building on: graph theory and game theory. These are theories of structure and behavior, respectively. Graph theory is the study of network structure, while game theory provides models of individual behavior in settings where outcomes depend on the behavior of others.

Graph Theory. In our discussion of graph theory, we focus particularly on some of the fundamental ideas from social network analysis, framing a number of graph-theoretic concepts in these terms. The networks in Figures 1.1 and 1.2 hint at some of these ideas. In the corporate e-mail communication network from Figure 1.2, for example, the communication is balanced between staying within small organizational units and cutting across organizational boundaries. This is an example of a much more general principle in social networks – that strong ties, representing close and frequent social contacts, tend to be embedded in tightly-linked regions of the network, whereas weak ties, representing more casual and distinct social contacts, tend to cross between these regions. Such a dichotomy suggests a way of thinking about social networks in terms of their dense pockets of strong ties and the ways in which they interact with each other through weaker ties. In a professional setting, it suggests a strategy for navigating one’s way through the social landscape of a large organization by finding the structural holes between parts of the network that interact very little with each other. At a global scale, it suggests some of the ways in which weak ties can act as “shortcuts” that link together distant parts of the world, resulting in the phenomenon colloquially known as six degrees of separation.

Social networks can also capture the sources of conflict within a group. For example, latent conflicts are at work in the karate club social network from Figure 1.1. The people labeled 1 and 34 (the darker circles) are particularly central in the network of

8 overview

27 15

23

10 20

4 13

16

34 31

14

12

18

17

30

33

32

9

2

1

5

6

21

24

25

3

8

22

11

7

19 28

29

26

Figure 1.7. From the social network of friendships in the karate club from Figure 1.1, we can find clues to the latent schism that eventually split the group into two separate clubs (indicated by the two different shadings of individuals in the drawing).

friendships, with many connections to other people. On the other hand, they are not friends with each other, and in fact most people are only friends with one or the other of them. These two central people were, respectively, the instructor and the student founder of the club, and this pattern of noninteracting clusters was the most visible symptom of a conflict between them and their factions that ultimately splintered the group into two rival karate clubs, as shown in Figure 1.7. Later we will see how the theory of structural balance can be used to reason about how fissures in a network may arise from the dynamics of conflict and antagonism at a purely local level.

Game Theory. Our discussion of game theory starts from the observation that there are numerous settings in which a group of people must simultaneously choose how to act, knowing that the outcome will depend on the decisions made by all of them. One natural example is the problem of choosing a driving route through a network of highways at a time when traffic is heavy. For a driver in such a situation, the delays experienced depend on the pattern of traffic congestion arising not just from the driver’s choice of route, but also from the choices made by all other drivers. In this example, the network plays the role of a shared resource, and the combined actions of its users can either congest this resource or use it more efficiently. In fact, the interactions among people’s behavior can lead to counterintuitive effects; for example, adding resources to a transportation network can in fact create incentives that seriously undermine its efficiency, in a phenomenon known as Braess’s Paradox [76].

Another example that will recur in several settings throughout the book is the problem of bidding in an auction. If a seller is trying to sell a single item using an auction, then the success of any one bidder in the auction (whether she gets the item, and how much she pays) depends not just on how she bids but also on how everyone else bids; an optimal bidding strategy should take this into account. Here too, counterintuitive effects

central themes and topics 9

are at work: for example, if the seller introduces more aggressive pricing rules into the auction, he can make the strategic behavior of the bidders much more complex, and in particular induce optimal bidding that offsets whatever gains he might have expected to make from the new rules. Auctions represent a basic kind of economic interaction that we will generalize to more complex patterns of interactions in networks.

As a general part of our investigation of game theory, we abstract such situations with interdependent behavior into a common framework, wherein a collection of individuals must each commit to a strategy, thereby receiving a payoff that depends on the strategies chosen by everyone. Interpreting our preceding examples in this light, we see that the strategies available to a driver on a set of highways consist of the different options for routes he can take, and the payoff to this driver is based on his resulting travel time. In an auction, the strategies are the different choices for how to bid, and the payoff to a bidder is the difference between the value of the goods she receives and the price she pays. This general framework allows us to make predictions about how people will behave in a range of such situations. A fundamental part of this framework is the notion of equilibrium – a state that is “self-reinforcing” in that it provides no individual with an incentive to unilaterally change his or her strategy, even if that individual knows how others will behave.

Markets and Strategic Interaction in Networks. Once we have developed graph theory and game theory, we can combine them to produce richer models of behavior in networks. One natural setting for this exploration is in models of trade and other forms of economic activity. The interactions among buyers and sellers, or pairs of counterparties to a trade or loan, naturally forms a network. In Figure 1.3 we saw an example of such a network, with links between banks engaging in a loan. Figure 1.8 shows another example: a network representation of international trade among twenty- eight countries [262], in which the size of each country depicts its total amount of trade, and the thickness of each link connecting two countries indicates the amount of trade between them.

Where do these networks come from? In some cases, they are the traces of what hap- pens when each participant seeks out the best trading partner it can find guided by how highly it values different trading opportunities. In other cases, they also reflect funda- mental underlying constraints in the market that limit the access of certain participants to each other. In modern markets, these constraints could be institutional restrictions based on regulations; in other settings, they could be based on physical constraints like geography. For example, Figure 1.9 shows a map of trade routes in medieval Europe: when the physical movement of goods is costly and difficult, the economic outcome for different cities can depend significantly on where they are located in the underlying transportation network.

In all these settings, the network structure encodes a lot about the pattern of trade, and the success levels of different participants are affected by their positions in the network. Having a powerful position, however, depends not just on having many connections providing different options, but also on more subtle features – such as the power of the other individuals to which one is connected. Later we will see that this idea of network positions conferring power has been extended much more broadly and reaches beyond

10 overview ©

L ot

ha r

K re

m pe

l, M

ax P

la nc

k In

st itu

te fo

r th

e S

tu dy

o f S

oc ie

tie s,

C ol

og ne

SAU

THA

ESP

BRA

FRA

USA

ITA

SWE CHN

HKG

MYS

NLD

CAN

IDN

DNK

FIN

JPN

SGP

GBR

KOR

NOR

AUS

AUT

MEX

CHE

IRL

Figure 1.8. In a network representing international trade, one can look for countries that occupy powerful positions and derive economic benefits from these positions [262]. (Image from Carnegie Mellon University; http://www.cmu.edu/joss/content/articles/volume4/ KrempelPlumper.html.)

just economic exchange to suggest how power imbalances in many forms of social relationships may have their roots in the network patterns formed by the relationships.

Information Networks. The information we deal with online has a fundamental net- work structure. Links among Web pages, for example, can help us understand how these pages are related, how they are grouped into different communities, and which pages are the most prominent or important. Figure 1.4 illustrates some of these issues: it shows a network of links among political blogs constructed by Lada Adamic and Natalie Glance in the period leading up to the 2004 U.S. presidential election [5]. Although the network in the figure is too large to be able to see clearly the detailed structure around individual blogs, the image and its layout do convey the clear separa- tion of the blogging network into two large clusters, which turn out to closely correspond to the sets of liberal and conservative blogs, respectively. From more detailed analysis of the raw linkage data underlying the image, it is possible to pick out the prominent blogs within each of these clusters.

Current Web search engines such as Google make extensive use of network structure in evaluating the quality and relevance of Web pages. To produce search results, these sites evaluate the prominence of a Web page based not just on the number of links it receives but on more subtle aspects of its position in the network. For example, a page

central themes and topics 11

20

50

45

40

35

30

15 10 5 0 5 10 15 20 25 30 Bergen Oslo

HamburgL¸beck Danzig

Leipzig

Crakow Prague

ErfurtFrankfurt Bruges

London

York

Chester

Berwick

Santiago

Lisbon Toledo

Cordova Cadiz

Valencia

Barcelona Marseilles

Bordeaux Lyon

Basel

Genoa

Milan

Augsburg

Venice

Vienna Budapest

Lvov

Akkerman

Beograd

Ragusa

Naples

Rome

Florence

Palma

Algiers Tunis

Canea

RigaVisby

Corfu

Messina

Paris

Cologne

Southampton

Reval

Figure 1.9. In some settings, such as this map of medieval trade routes, physical networks constrain the patterns of interaction, giving certain participants an intrinsic economic advan- tage based on their individual network positions. (Image from http://upload.wikimedia.org/ wikipedia/commons/e/e1/Late Medieval Trade Routes.jpg.)

can be viewed as more prominent if it receives links from pages that are themselves prominent; this is a circular notion in which prominence is defined in terms of itself, but we will see later that this circularity can be resolved through careful definitions that are based on a kind of equilibrium in the link structure.

The interaction between search engines and the authors of Web pages is also a compelling example of a system where connectedness at the level of behavior produces interesting effects. Whenever a search engine introduces a new method for evaluating Web pages and deciding which pages to rank highly in its results, the creators of Web content react: they optimize what they put on the Web to try to achieve a high rank under the new method. As a result, changes to a search engine can never be designed under the assumption that the Web will remain static; rather, the Web inevitably adapts to the ways in which search engines evaluate content, and search methods must be developed with these feedback effects in mind.

12 overview

Search Volume Index

2.00

1.00

2004 2005 2006 2007 2008 0

Google Trends

Figure 1.10. Cascading adoption of a new technology or service (in this case, the social networking site MySpace in 2005–2008) can be the result of individual incentives to use the most widespread technology – either based on the informational effects of seeing many other people adopt the technology or based on the direct benefits of adopting what many others are already using. (Image from Google Trends, http://www.google.com/trends?q=myspace.)

This inherently game-theoretic interaction existed in latent form even in the early days of the Web. Over time it became more explicit and formalized through the design of markets for advertising based on search, with advertising space allocated by auction mechanisms. Today such markets are a principal source of revenue for the main search engines.

Network Dynamics: Population Effects. If we observe a large population over time, we see a recurring pattern by which new ideas, beliefs, opinions, innovations, technolo- gies, products, and social conventions are constantly emerging and evolving. Collec- tively, we can refer to these as social practices [382] (e.g., holding opinions, purchasing products, or behaving according to certain principles) that people can choose to adopt or not. As we watch a group or society over time, we see that new practices can be introduced that either become popular or remain obscure; meanwhile, established prac- tices can persist or potentially fade over time. Thinking back to Figures 1.5 and 1.6, recall that they show the adoption of particular practices over time – the use of two very popular social media sites (taking the total number of Google queries for these sites over time as proxies for their popularity). Figure 1.10 depicts an analogous curve for the social networking site MySpace, where we see a life cycle of rapid adoption followed by a slower period of decline, as MySpace’s dominance was challenged by newer competitors, including Facebook.

The way in which new practices spread through a population depends in large part on the fact that people influence each other’s behavior. In short, as you see more and more people doing something, you generally become more likely to do it, too. Understanding this process, and what its consequences are, is a central issue for our understanding of networks and aggregate behavior.

At a surface level, one could hypothesize that people imitate the decisions of others simply because of an underlying human tendency to conform: we have a fundamental inclination to behave as we see others behaving. This observation is clearly important, but as an explanation it leaves some crucial questions unresolved. In particular, by taking imitation as a given, we miss the opportunity to ask why people are influenced

central themes and topics 13

by the behavior of others. This is a broad and difficult question, but in fact it is possible to identify multiple reasons why even purely rational agents – individuals with no a priori desire to conform to what others are doing – nonetheless copy the behavior of others.

One class of reasons is based on the fact that the behavior of others conveys infor- mation. You may have some private information on which to base a decision between alternatives, but if you see many people making a particular choice, it is natural to assume that they too have their own information, and to try to infer how other people are evaluating different choices from how they are behaving. In the case of a Web site like YouTube or Flickr, the observation that a lot of people use it can suggest that these people know something about its quality. Similarly, seeing that a certain restaurant is extremely crowded every weekend can suggest that many people think highly of it. But this sort of reasoning raises surprisingly subtle issues: as many people make decisions sequentially over time, the later decisions can be based in complex ways on a mixture of private information and inferences from what has already happened, so that the actions of a large set of people can in fact be based on surprisingly little genuine information. In an extreme form of this phenomenon we may get information cascades, where even rational individuals can choose to abandon their private information and follow a crowd.

There is a completely different but equally important class of reasons why people may imitate the behavior of others – when a direct benefit can be gained from aligning one’s behavior with that of others, regardless of whether they are making the best decision. Let’s go back to our examples of social networking and media-sharing sites. If the value of such sites is in the potential to interact with others, to have access to a wide range of content, and to have a large audience for the content you post, then these types of sites become more and more valuable as people join them. In other words, regardless of whether YouTube had better features than its competitors, once it became the most popular video-sharing site, there was by definition an added value in using it. Such network effects amplify the success of products and technologies that are already doing well; in a market where network effects are at work, the leader can be difficult to displace. Still, this type of dominance is not necessarily permanent; as we will see later, it is possible for a new technology to displace an old one if it offers something markedly different or when it starts in a part of the network where there is room for the new technology to take hold.

These considerations show how popularity as a general phenomenon is governed by a “rich get richer” feedback process in which popularity tends to build on itself. It is possible to build mathematical models for this process that include predictions for the distribution of popularity that are borne out by empirical data – a picture in which society’s attention is divided between a small number of prominent items and a “long tail” of more obscure ones.