Networks, Crowds, and Markets – Reasoning About A Highly Connected World – by David Easley and Jon Kleinberg
http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book.pdf
-
Contents
- 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 Balanced Networks and the Cartwright-Harary Theorem
- 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
