High School Dating
(Bearman, Moody, and Stovel, 2004)
(Image by Mark Newman)
|
|
Corporate E-Mail Communication
(Adamic and Adar, 2005)
.
|
|
Trails of Flickr Users
in Manhattan
(Crandall et al. 2009)
|
|
Prediction Market for the
2008 U.S. Presidential Election
(Iowa Electonic Markets, 2008)
|
Networks, Crowds, and Markets:
Reasoning About a Highly Connected World
In recent years 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 communication 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.
Networks, Crowds, and Markets
combines different scientific perspectives in its approach
to understanding networks and behavior. Drawing on ideas from
economics, sociology, computing and information science, and
applied mathematics, it describes the emerging field of study that
is growing at the interface of all these areas, addressing fundamental
questions about how the social, economic, and technological worlds
are connected.
The book is based on an inter-disciplinary course
that we teach at Cornell.
The book, like the course, is designed at the introductory undergraduate level
with no formal prerequisites.
To support deeper explorations, most of
the chapters are supplemented with optional advanced sections.
The book is published by Cambridge University Press (2010);
for more information, please see
Cambridge's page for the book.
You can download a complete pre-publication draft of
Networks, Crowds, and Markets
here.
We welcome your feedback on the manuscript.
Contents (with links to individual chapters)
- Chapter 1. Overview
- 1.1 Aspects of Networks
- 1.2 Central Themes and Topics
Part I Graph Theory and Social Networks
- Chapter 2. Graphs
- 2.1 Basic Definitions
- 2.2 Paths and Connectivity
- 2.3 Distance and Breadth-First Search
- 2.4 Network Datasets: An Overview
- Chapter 3. Strong and Weak Ties
- 3.1 Triadic Closure
- 3.2 The Strength of Weak Ties
- 3.3 Tie Strength and Network Structure in Large-Scale Data
- 3.4 Tie Strength, Social Media, and Passive Engagement
- 3.5 Closure, Structural Holes, and Social Capital
- 3.6 Advanced Material: Betweenness Measures and Graph Partitioning
- Chapter 4. Networks in Their Surrounding Contexts
- 4.1 Homophily
- 4.2 Mechanisms Underlying Homophily: Selection and Social Influence
- 4.3 Affiliation
- 4.4 Tracking Link Formation in On-Line Data
- 4.5 A Spatial Model of Segregation
- Chapter 5. Positive and Negative Relationships
- 5.1 Structural Balance
- 5.2 Characterizing the Structure of Balanced Networks
- 5.3 Applications of Structural Balance
- 5.4 A Weaker Form of Structural Balance
- 5.5 Advanced Material: Generalizing the Definition of Structural Balance
Part II Game Theory
- Chapter 6. Games
- 6.1 What is a Game?
- 6.2 Reasoning about Behavior in a Game
- 6.3 Best Responses and Dominant Strategies
- 6.4 Nash Equilibrium
- 6.5 Multiple Equilibria: Coordination Games
- 6.6 Multiple Equilibria: The Hawk-Dove Game
- 6.7 Mixed Strategies
- 6.8 Mixed Strategies: Examples and Empirical Analysis
- 6.9 Pareto-Optimality and Social Optimality
- 6.10 Advanced Material: Dominated Strategies and Dynamic Games
- Chapter 7. Evolutionary Game Theory
- 7.1 Fitness as a Result of Interaction
- 7.2 Evolutionarily Stable Strategies
- 7.3 A General Description of Evolutionarily Stable Strategies
- 7.4 Relationship Between Evolutionary and Nash Equilibria
- 7.5 Evolutionarily Stable Mixed Strategies
- Chapter 8. Modeling Network Traffic using Game Theory
- 8.1 Traffic at Equilibrium
- 8.2 Braess's Paradox
- 8.3 Advanced Material: The Social Cost of Traffic at Equilibrium
- Chapter 9. Auctions
- 9.1 Types of Auctions
- 9.2 When are Auctions Appropriate?
- 9.3 Relationships between Different Auction Formats
- 9.4 Second-Price Auctions
- 9.5 First-Price Auctions and Other Formats
- 9.6 Common Values and The Winner's Curse
- 9.7 Advanced Material: Bidding Strategies in First-Price and All-Pay Auctions
Part III Markets and Strategic Interaction in Networks
- Chapter 10. Matching Markets
- 10.1 Bipartite Graphs and Perfect Matchings
- 10.2 Valuations and Optimal Assignments
- 10.3 Prices and the Market-Clearing Property
- 10.4 Constructing a Set of Market-Clearing Prices
- 10.5 How Does this Relate to Single-Item Auctions?
- 10.6 Advanced Material: A Proof of the Matching Theorem
- Chapter 11. Network Models of Markets with Intermediaries
- 11.1 Price-Setting in Markets
- 11.2 A Model of Trade on Networks
- 11.3 Equilibria in Trading Networks
- 11.4 Further Equilibrium Phenomena: Auctions and Ripple Effects
- 11.5 Social Welfare in Trading Networks
- 11.6 Trader Profits
- 11.7 Reflections on Trade with Intermediaries
- Chapter 12. Bargaining and Power in Networks
- 12.1 Power in Social Networks
- 12.2 Experimental Studies of Power and Exchange
- 12.3 Results of Network Exchange Experiments
- 12.4 A Connection to Buyer-Seller Networks
- 12.5 Modeling Two-Person Interaction: The Nash Bargaining Solution
- 12.6 Modeling Two-Person Interaction: The Ultimatum Game
- 12.7 Modeling Network Exchange: Stable Outcomes
- 12.8 Modeling Network Exchange: Balanced Outcomes
- 12.9 Advanced Material: A Game-Theoretic Approach to Bargaining
Part IV Information Networks and the World Wide Web
- Chapter 13. The Structure of the Web
- 13.1 The World Wide Web
- 13.2 Information Networks, Hypertext, and Associative Memory
- 13.3 The Web as a Directed Graph
- 13.4 The Bow-Tie Structure of the Web
- 13.5 The Emergence of Web 2.0
- Chapter 14. Link Analysis and Web Search
- 14.1 Searching the Web: The Problem of Ranking
- 14.2 Link Analysis using Hubs and Authorities
- 14.3 PageRank
- 14.4 Applying Link Analysis in Modern Web Search
- 14.5 Applications beyond the Web
- 14.6 Advanced Material: Spectral Analysis, Random Walks, and Web Search
- Chapter 15. Sponsored Search Markets
- 15.1 Advertising Tied to Search Behavior
- 15.2 Advertising as a Matching Market
- 15.3 Encouraging Truthful Bidding in Matching Markets: The VCG Principle
- 15.4 Analyzing the VCG Procedure: Truth-Telling as a Dominant Strategy
- 15.5 The Generalized Second Price Auction
- 15.6 Equilibria of the Generalized Second Price Auction
- 15.7 Ad Quality
- 15.8 Complex Queries and Interactions Among Keywords
- 15.9 Advanced Material: VCG Prices and the Market-Clearing Property
Part V Network Dynamics: Population Models
- Chapter 16. Information Cascades
- 16.1 Following the Crowd
- 16.2 A Simple Herding Experiment
- 16.3 Bayes' Rule: A Model of Decision-Making Under Uncertainty
- 16.4 Bayes' Rule in the Herding Experiment
- 16.5 A Simple, General Cascade Model
- 16.6 Sequential Decision-Making and Cascades
- 16.7 Lessons from Cascades
- Chapter 17. Network Effects
- 17.1 The Economy Without Network Effects
- 17.2 The Economy with Network Effects
- 17.3 Stability, Instability, and Tipping Points
- 17.4 A Dynamic View of the Market
- 17.5 Industries with Network Goods
- 17.6 Mixing Individual Effects with Population-Level Effects
- 17.7 Advanced Material: Negative Externalities and The El Farol Bar Problem
- Chapter 18. Power Laws and Rich-Get-Richer Phenomena
- 18.1 Popularity as a Network Phenomenon
- 18.2 Power Laws
- 18.3 Rich-Get-Richer Models
- 18.4 The Unpredictability of Rich-Get-Richer Effects
- 18.5 The Long Tail
- 18.6 The Effect of Search Tools and Recommendation Systems
- 18.7 Advanced Material: Analysis of Rich-Get-Richer Processes
Part VI Network Dynamics: Structural Models
- Chapter 19. Cascading Behavior in Networks
- 19.1 Diffusion in Networks
- 19.2 Modeling Diffusion through a Network
- 19.3 Cascades and Clusters
- 19.4 Diffusion, Thresholds, and the Role of Weak Ties
- 19.5 Extensions of the Basic Cascade Model
- 19.6 Knowledge, Thresholds, and Collective Action
- 19.7 Advanced Material: The Cascade Capacity
- Chapter 20. The Small-World Phenomenon
- 20.1 Six Degrees of Separation
- 20.2 Structure and Randomness
- 20.3 Decentralized Search
- 20.4 Empirical Analysis and Generalized Models
- 20.5 Core-Periphery Structures and Difficulties in Decentralized Search
- 20.6 Advanced Material: Analysis of Decentralized Search
- Chapter 21. Epidemics
- 21.1 Diseases and the Networks that Transmit Them
- 21.2 Branching Processes
- 21.3 The SIR Epidemic Model
- 21.4 The SIS Epidemic Model
- 21.5 Synchronization
- 21.6 Transient Contacts and the Dangers of Concurrency
- 21.7 Genealogy, Genetic Inheritance, and Mitochondrial Eve
- 21.8 Advanced Material: Analysis of Branching and Coalescent Processes
Part VII Institutions and Aggregate Behavior
- Chapter 22. Markets and Information
- 22.1 Markets with Exogenous Events
- 22.2 Horse Races, Betting, and Beliefs
- 22.3 Aggregate Beliefs and the ``Wisdom of Crowds''
- 22.4 Prediction Markets and Stock Markets
- 22.5 Markets with Endogenous Events
- 22.6 The Market for Lemons
- 22.7 Asymmetric Information in Other Markets
- 22.8 Signaling Quality
- 22.9 Quality Uncertainty On-Line: Reputation Systems and Other Mechanisms
- 22.10 Advanced Material: Wealth Dynamics in Markets
- Chapter 23. Voting
- 23.1 Voting for Group Decision-Making
- 23.2 Individual Preferences
- 23.3 Voting Systems: Majority Rule
- 23.4 Voting Systems: Positional Voting
- 23.5 Arrow's Impossibility Theorem
- 23.6 Single-Peaked Preferences and the Median Voter Theorem
- 23.7 Voting as a Form of Information Aggregation
- 23.8 Insincere Voting for Information Aggregation
- 23.9 Jury Decisions and the Unanimity Rule
- 23.10 Sequential Voting and the Relation to Information Cascades
- 23.11 Advanced Material: A Proof of Arrow's Impossibility Theorem
- Chapter 24. Property Rights
- 24.1 Externalities and the Coase Theorem
- 24.2 The Tragedy of the Commons
- 24.3 Intellectual Property
Bibliography