Networks, Crowds, and Markets - Cornell Computer Science

3.4 Tie Strength, Social Media, and Passive Engagement . .... 10 Matching Markets. 277 ..... more fine-grained level of network structure, beginning with the question of ..... which show the growth in popularity of the social media sites YouTube ...
19MB Sizes 0 Downloads 161 Views
Networks, Crowds, and Markets: Reasoning about a Highly Connected World

David Easley

Jon Kleinberg

Dept. of Economics Cornell University

Dept. of Computer Science Cornell University

Cambridge University Press, 2010 Draft version: June 10, 2010.

2

Contents Preface

i

1 Overview 1.1 Aspects of Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Central Themes and Topics . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 8

I

Graph Theory and Social Networks

2 Graphs 2.1 Basic Definitions . . . . . . . . . . 2.2 Paths and Connectivity . . . . . . . 2.3 Distance and Breadth-First Search 2.4 Network Datasets: An Overview . . 2.5 Exercises . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

21 . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

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 3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Networks in Their Surrounding Contexts 4.1 Homophily . . . . . . . . . . . . . . . . . . . . . . 4.2 Mechanisms Underlying Homophily: Selection and 4.3 Affiliation . . . . . . . . . . . . . . . . . . . . . . 4.4 Tracking Link Formation in On-Line Data . . . . 4.5 A Spatial Model of Segregation . . . . . . . . . . 4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . 3

. . . . . . . . . . Social Influence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . . . .

. . . . . .

. . . . .

. . . . . . .

. . . . . .

. . . . .

. . . . . . .

. . . . . .

. . . . .

. . . . . . .

. . . . . .

. . . . .

23 23 25 32 40 44

. . . . . . .

47 48 50 56 60 64 69 83

. . . . . .

85 86 90 93 97 107 116

4

CONTENTS

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 5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

II

. . . . . . . . . . . . . . . . . . . . Balance . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Game Theory

119 120 123 126 129 132 148

153

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 . . . . . . . . . . . . . . . . . . . . .