You are previewing Networks, Crowds, and Markets.
O'Reilly logo
Networks, Crowds, and Markets

Book Description

Are all film stars linked to Kevin Bacon? Why do the stock markets rise and fall sharply on the strength of a vague rumour? How does gossip spread so quickly? Are we all related through six degrees of separation? There is a growing awareness of the complex networks that pervade modern society. We see them in the rapid growth of the Internet, the ease of global communication, the swift spread of news and information, and in the way epidemics and financial crises develop with startling speed and intensity. This introductory book on the new science of networks takes an interdisciplinary approach, using economics, sociology, computing, information science and applied mathematics to address fundamental questions about the links that connect us, and the ways that our decisions can have consequences for others.

Table of Contents

  1. Coverpage
  2. Half title page
  3. Title page
  4. Copyright page
  5. Contents
  6. Preface
  7. 1 Overview
    1. 1.1 Aspects of Networks
    2. 1.2 Central Themes and Topics
  8. Part I Graph Theory and Social Networks
    1. 2 Graphs
      1. 2.1 Basic Definitions
      2. 2.2 Paths and Connectivity
      3. 2.3 Distance and Breadth-First Search
      4. 2.4 Network Data Sets: An Overview
      5. 2.5 Exercises
    2. 3 Strong and Weak Ties
      1. 3.1 Triadic Closure
      2. 3.2 The Strength of Weak Ties
      3. 3.3 Tie Strength and Network Structure in Large-Scale Data
      4. 3.4 Tie Strength, Social Media, and Passive Engagement
      5. 3.5 Closure, Structural Holes, and Social Capital
      6. 3.6 Advanced Material: Betweenness Measures and Graph Partitioning
      7. 3.7 Exercises
    3. 4 Networks in Their Surrounding Contexts
      1. 4.1 Homophily
      2. 4.2 Mechanisms Underlying Homophily: Selection and Social Influence
      3. 4.3 Affiliation
      4. 4.4 Tracking Link Formation in Online Data
      5. 4.5 A Spatial Model of Segregation
      6. 4.6 Exercises
    4. 5 Positive and Negative Relationships
      1. 5.1 Structural Balance
      2. 5.2 Characterizing the Structure of Balanced Networks
      3. 5.3 Applications of Structural Balance
      4. 5.4 A Weaker Form of Structural Balance
      5. 5.5 Advanced Material: Generalizing the Definition of Structural Balance
      6. 5.6 Exercises
  9. Part II Game Theory
    1. 6 Games
      1. 6.1 What Is a Game?
      2. 6.2 Reasoning about Behavior in a Game
      3. 6.3 Best Responses and Dominant Strategies
      4. 6.4 Nash Equilibrium
      5. 6.5 Multiple Equilibria: Coordination Games
      6. 6.6 Multiple Equilibria: The Hawk--Dove Game
      7. 6.7 Mixed Strategies
      8. 6.8 Mixed Strategies: Examples and Empirical Analysis
      9. 6.9 Pareto Optimality and Social Optimality
      10. 6.10 Advanced Material: Dominated Strategies and Dynamic Games
      11. 6.11 Exercises
    2. 7 Evolutionary Game Theory
      1. 7.1 Fitness as a Result of Interaction
      2. 7.2 Evolutionarily Stable Strategies
      3. 7.3 A General Description of Evolutionarily Stable Strategies
      4. 7.4 Relationship between Evolutionary and Nash Equilibria
      5. 7.5 Evolutionarily Stable Mixed Strategies
      6. 7.6 Exercises
    3. 8 Modeling Network Traffic Using Game Theory
      1. 8.1 Traffic at Equilibrium
      2. 8.2 Braess's Paradox
      3. 8.3 Advanced Material: The Social Cost of Traffic at Equilibrium
      4. 8.4 Exercises
    4. 9 Auctions
      1. 9.1 Types of Auctions
      2. 9.2 When Are Auctions Appropriate?
      3. 9.3 Relationships between Different Auction Formats
      4. 9.4 Second-Price Auctions
      5. 9.5 First-Price Auctions and Other Formats
      6. 9.6 Common Values and the Winner's Curse
      7. 9.7 Advanced Material: Bidding Strategies in First-Price and All-Pay Auctions
      8. 9.8 Exercises
  10. Part III Markets and Strategic Interaction in Networks
    1. 10 Matching Markets
      1. 10.1 Bipartite Graphs and Perfect Matchings
      2. 10.2 Valuations and Optimal Assignments
      3. 10.3 Prices and the Market-Clearing Property
      4. 10.4 Constructing a Set of Market-Clearing Prices
      5. 10.5 How Does This Relate to Single-Item Auctions?
      6. 10.6 Advanced Material: A Proof of the Matching Theorem
      7. 10.7 Exercises
    2. 11 Network Models of Markets with Intermediaries
      1. 11.1 Price Setting in Markets
      2. 11.2 A Model of Trade on Networks
      3. 11.3 Equilibria in Trading Networks
      4. 11.4 Further Equilibrium Phenomena: Auctions and Ripple Effects
      5. 11.5 Social Welfare in Trading Networks
      6. 11.6 Trader Profits
      7. 11.7 Reflections on Trade with Intermediaries
      8. 11.8 Exercises
    3. 12 Bargaining and Power in Networks
      1. 12.1 Power in Social Networks
      2. 12.2 Experimental Studies of Power and Exchange
      3. 12.3 Results of Network Exchange Experiments
      4. 12.4 A Connection to Buyer--Seller Networks
      5. 12.5 Modeling Two-Person Interaction: The Nash Bargaining Solution
      6. 12.6 Modeling Two-Person Interaction: The Ultimatum Game
      7. 12.7 Modeling Network Exchange: Stable Outcomes
      8. 12.8 Modeling Network Exchange: Balanced Outcomes
      9. 12.9 Advanced Material: A Game-Theoretic Approach to Bargaining
      10. 12.10 Exercises
  11. Part IV Information Networks and the World Wide Web
    1. 13 The Structure of the Web
      1. 13.1 The World Wide Web
      2. 13.2 Information Networks, Hypertext, and Associative Memory
      3. 13.3 The Web as a Directed Graph
      4. 13.4 The Bow-Tie Structure of the Web
      5. 13.5 The Emergence of Web 2.0
      6. 13.6 Exercises
    2. 14 Link Analysis and Web Search
      1. 14.1 Searching the Web: The Problem of Ranking
      2. 14.2 Link Analysis Using Hubs and Authorities
      3. 14.3 PageRank
      4. 14.4 Applying Link Analysis in Modern Web Search
      5. 14.5 Applications beyond the Web
      6. 14.6 Advanced Material: Spectral Analysis, Random Walks, and Web Search
      7. 14.7 Exercises
    3. 15 Sponsored Search Markets
      1. 15.1 Advertising Tied to Search Behavior
      2. 15.2 Advertising as a Matching Market
      3. 15.3 Encouraging Truthful Bidding in Matching Markets: The VCG Principle
      4. 15.4 Analyzing the VCG Mechanism: Truth-Telling as a Dominant Strategy
      5. 15.5 The Generalized Second-Price Auction
      6. 15.6 Equilibria of the Generalized Second-Price Auction
      7. 15.7 Ad Quality
      8. 15.8 Complex Queries and Interactions among Keywords
      9. 15.9 Advanced Material: VCG Prices and the Market-Clearing Property
      10. 15.10 Exercises
  12. Part V Network Dynamics: Population Models
    1. 16 Information Cascades
      1. 16.1 Following the Crowd
      2. 16.2 A Simple Herding Experiment
      3. 16.3 Bayes' Rule: A Model of Decision Making under Uncertainty
      4. 16.4 Bayes' Rule in the Herding Experiment
      5. 16.5 A Simple, General Cascade Model
      6. 16.6 Sequential Decision Making and Cascades
      7. 16.7 Lessons from Cascades
      8. 16.8 Exercises
    2. 17 Network Effects
      1. 17.1 The Economy without Network Effects
      2. 17.2 The Economy with Network Effects
      3. 17.3 Stability, Instability, and Tipping Points
      4. 17.4 A Dynamic View of the Market
      5. 17.5 Industries with Network Goods
      6. 17.6 Mixing Individual Effects with Population-Level Effects
      7. 17.7 Advanced Material: Negative Externalities and the El Farol Bar Problem
      8. 17.8 Exercises
    3. 18 Power Laws and Rich-Get-Richer Phenomena
      1. 18.1 Popularity as a Network Phenomenon
      2. 18.2 Power Laws
      3. 18.3 Rich-Get-Richer Models
      4. 18.4 The Unpredictability of Rich-Get-Richer Effects
      5. 18.5 The Long Tail
      6. 18.6 The Effect of Search Tools and Recommendation Systems
      7. 18.7 Advanced Material: Analysis of Rich-Get-Richer Processes
      8. 18.8 Exercises
  13. Part VI Network Dynamics: Structural Models
    1. 19 Cascading Behavior in Networks
      1. 19.1 Diffusion in Networks
      2. 19.2 Modeling Diffusion through a Network
      3. 19.3 Cascades and Clusters
      4. 19.4 Diffusion, Thresholds, and the Role of Weak Ties
      5. 19.5 Extensions of the Basic Cascade Model
      6. 19.6 Knowledge, Thresholds, and Collective Action
      7. 19.7 Advanced Material: The Cascade Capacity
      8. 19.8 Exercises
    2. 20 The Small-World Phenomenon
      1. 20.1 Six Degrees of Separation
      2. 20.2 Structure and Randomness
      3. 20.3 Decentralized Search
      4. 20.4 Modeling the Process of Decentralized Search
      5. 20.5 Empirical Analysis and Generalized Models
      6. 20.6 Core--Periphery Structures and Difficulties in Decentralized Search
      7. 20.7 Advanced Material: Analysis of Decentralized Search
      8. 20.8 Exercises
    3. 21 Epidemics
      1. 21.1 Diseases and the Networks That Transmit Them
      2. 21.2 Branching Processes
      3. 21.3 The SIR Epidemic Model
      4. 21.4 The SIS Epidemic Model
      5. 21.5 Synchronization
      6. 21.6 Transient Contacts and the Dangers of Concurrency
      7. 21.7 Genealogy, Genetic Inheritance, and Mitochondrial Eve
      8. 21.8 Advanced Material: Analysis of Branching and Coalescent Processes
      9. 21.9 Exercises
  14. Part VII Institutions and Aggregate Behavior
    1. 22 Markets and Information
      1. 22.1 Markets with Exogenous Events
      2. 22.2 Horse Races, Betting, and Beliefs
      3. 22.3 Aggregate Beliefs and the “Wisdom of Crowds”
      4. 22.4 Prediction Markets and Stock Markets
      5. 22.5 Markets with Endogenous Events
      6. 22.6 The Market for Lemons
      7. 22.7 Asymmetric Information in Other Markets
      8. 22.8 Signaling Quality
      9. 22.9 Quality Uncertainty Online: Reputation Systems and Other Mechanisms
      10. 22.10 Advanced Material: Wealth Dynamics in Markets
      11. 22.11 Exercises
    2. 23 Voting
      1. 23.1 Voting for Group Decision Making
      2. 23.2 Individual Preferences
      3. 23.3 Voting Systems: Majority Rule
      4. 23.4 Voting Systems: Positional Voting
      5. 23.5 Arrow's Impossibility Theorem
      6. 23.6 Single-Peaked Preferences and the Median Voter Theorem
      7. 23.7 Voting as a Form of Information Aggregation
      8. 23.8 Insincere Voting for Information Aggregation
      9. 23.9 Jury Decisions and the Unanimity Rule
      10. 23.10 Sequential Voting and the Relation to Information Cascades
      11. 23.11 Advanced Material: A Proof of Arrow's Impossibility Theorem
      12. 23.12 Exercises
    3. 24 Property Rights
      1. 24.1 Externalities and the Coase Theorem
      2. 24.2 The Tragedy of the Commons
      3. 24.3 Intellectual Property
      4. 24.4 Exercises
  15. Bibliography
  16. Index