High School Dating
(Bearman, Moody, and Stovel, 2004)
(Image by Mark Newman)


Corporate EMail 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 interdisciplinary 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 prepublication 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 BreadthFirst 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 LargeScale 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 OnLine 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 HawkDove Game
 6.7 Mixed Strategies
 6.8 Mixed Strategies: Examples and Empirical Analysis
 6.9 ParetoOptimality 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 SecondPrice Auctions
 9.5 FirstPrice Auctions and Other Formats
 9.6 Common Values and The Winner's Curse
 9.7 Advanced Material: Bidding Strategies in FirstPrice and AllPay 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 MarketClearing Property
 10.4 Constructing a Set of MarketClearing Prices
 10.5 How Does this Relate to SingleItem Auctions?
 10.6 Advanced Material: A Proof of the Matching Theorem
 Chapter 11. Network Models of Markets with Intermediaries
 11.1 PriceSetting 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 BuyerSeller Networks
 12.5 Modeling TwoPerson Interaction: The Nash Bargaining Solution
 12.6 Modeling TwoPerson Interaction: The Ultimatum Game
 12.7 Modeling Network Exchange: Stable Outcomes
 12.8 Modeling Network Exchange: Balanced Outcomes
 12.9 Advanced Material: A GameTheoretic 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 BowTie 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: TruthTelling 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 MarketClearing 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 DecisionMaking Under Uncertainty
 16.4 Bayes' Rule in the Herding Experiment
 16.5 A Simple, General Cascade Model
 16.6 Sequential DecisionMaking 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 PopulationLevel Effects
 17.7 Advanced Material: Negative Externalities and The El Farol Bar Problem
 Chapter 18. Power Laws and RichGetRicher Phenomena
 18.1 Popularity as a Network Phenomenon
 18.2 Power Laws
 18.3 RichGetRicher Models
 18.4 The Unpredictability of RichGetRicher Effects
 18.5 The Long Tail
 18.6 The Effect of Search Tools and Recommendation Systems
 18.7 Advanced Material: Analysis of RichGetRicher 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 SmallWorld 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 CorePeriphery 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 OnLine: Reputation Systems and Other Mechanisms
 22.10 Advanced Material: Wealth Dynamics in Markets
 Chapter 23. Voting
 23.1 Voting for Group DecisionMaking
 23.2 Individual Preferences
 23.3 Voting Systems: Majority Rule
 23.4 Voting Systems: Positional Voting
 23.5 Arrow's Impossibility Theorem
 23.6 SinglePeaked 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