Social and Economic Networks

Contents
Preface 11
1 Introduction 17
1.1 Why Model Networks? . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 A Set of Examples: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Florentine Marriages . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.2 Friendships Among High School Students . . . . . . . . . . . . . 21
1.2.3 Random Graphs and Networks . . . . . . . . . . . . . . . . . . 25
1.2.4 The Symmetric Connections Model . . . . . . . . . . . . . . . . 31
1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 Representing and Measuring Networks 39
2.1 Representing Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1.1 Nodes and Players . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1.2 Graphs and Networks . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1.3 Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.1.4 Directed Paths, Walks, and Cycles . . . . . . . . . . . . . . . . 45
2.1.5 Components and Connected subgraphs . . . . . . . . . . . . . . 47
2.1.6 Trees, Stars, Circles, and Complete Networks . . . . . . . . . . 49
2.1.7 Neighborhood . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.1.8 Degree and Network Density . . . . . . . . . . . . . . . . . . . . 51
2.2 Some Summary Statistics and Characteristics of Networks . . . . . . . 52
2.2.1 Degree Distributions . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2.2 Diameter and Average Path Length . . . . . . . . . . . . . . . . 54
2.2.3 Cliquishness, Cohesiveness, and Clustering . . . . . . . . . . . . 57
2.2.4 Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3 Appendix: Some Basic Graph Theory . . . . . . . . . . . . . . . . . . . 69
2.3.1 Hall’ theorem and Bipartite Graphs
s . . . . . . . . . . . . . . . 69
2.3.2 Set Coverings and Independent Sets . . . . . . . . . . . . . . . . 71
2.3.3 Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.3.4 Eulerian Tours and Hamilton Cycles . . . . . . . . . . . . . . . 74
2.4 Appendix: Eigenvectors and Eigenvalues . . . . . . . . . . . . . . . . . 77
2.4.1 Diagonal Decompositions . . . . . . . . . . . . . . . . . . . . . . 79
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3 Empirical Background on Social and Economic Networks 83
3.1 The Prevalence of Social Networks . . . . . . . . . . . . . . . . . . . . 84
3.2 Observations about the Structure of Networks . . . . . . . . . . . . . . 85
3.2.1 Diameter and Small Worlds . . . . . . . . . . . . . . . . . . . . 85
3.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.2.3 Degree Distributions . . . . . . . . . . . . . . . . . . . . . . . . 90
3.2.4 Correlations and Assortativity . . . . . . . . . . . . . . . . . . . 96
3.2.5 Patterns of Clustering . . . . . . . . . . . . . . . . . . . . . . . 98
3.2.6 Homophily . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.2.7 The Strength of Weak Ties . . . . . . . . . . . . . . . . . . . . . 101
3.2.8 Structural Holes . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.2.9 Social Capital . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.2.10 Di¤usion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4 Random Graph-Based Models of Networks 107
4.1 Static Random-Graph Models of Random Networks . . . . . . . . . . . 109
4.1.1 Poisson and Related Random Network Models . . . . . . . . . . 109
4.1.2 “Small World”Networks . . . . . . . . . . . . . . . . . . . . . . 110
4.1.3 Markov Graphs and p networks . . . . . . . . . . . . . . . . . . 113
4.1.4 The Con...guration Model . . . . . . . . . . . . . . . . . . . . . . 115
4.1.5 An Expected Degree Model . . . . . . . . . . . . . . . . . . . . 120
4.1.6 Some Thoughts about Static Random Network Models . . . . . 121
4.2 Properties of Random Networks . . . . . . . . . . . . . . . . . . . . . . 121
4.2.1 The Distribution of the Degree of a Neighboring Node . . . . . 122
4.2.2 Thresholds and Phase Transitions . . . . . . . . . . . . . . . . . 125
4.2.3 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.2.4 Giant Components . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.2.5 Size of the Giant Component in Poisson Random Networks . . . 137
4.2.6 Giant Components in the Con...guration Model . . . . . . . . . . 139
4.2.7 Diameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . 143
4.3 An Application: Contagion and Di¤usion . . . . . . . . . . . . . . . . . 146
4.3.1 Distribution of Component Sizes . . . . . . . . . . . . . . . . . 149
4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.5 Appendix: Useful Facts, Tools, and Theorems . . . . . . . . . . . . . . 155
4.5.1 Sums of Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.5.2 e and Stirling’ Formula . . . . . . . . . . . . . . . . . . . . . . 156
s
4.5.3 Chebyshev’ Inequality and the Law of Large Numbers . . . . . 156
s
4.5.4 The Binomial Distribution . . . . . . . . . . . . . . . . . . . . . 157
4.5.5 Stochastic Dominance and Mean-Preserving Spreads . . . . . . 158
4.5.6 Domination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.5.7 Association . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.5.8 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.5.9 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . 163
5 Growing Random Networks 167
5.1 Uniform Randomness: an Exponential Degree Distribution . . . . . . . 169
5.1.1 Mean-Field Approximations . . . . . . . . . . . . . . . . . . . . 171
5.1.2 Continuous Time Approximations of Degree Distributions . . . 173
5.2 Preferential Attachment . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.3 Hybrid Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.3.1 Mean-Field Analyses of Growing Network Processes . . . . . . . 180
5.3.2 Mixing Random and Preferential Attachment . . . . . . . . . . 181
5.3.3 Simulations as a Check on the Degree Distribution . . . . . . . 182
5.3.4 Fitting Hybrid Degree Distributions to Data . . . . . . . . . . . 183
5.4 Small Worlds, Clustering, and Assortativity . . . . . . . . . . . . . . . 187
5.4.1 Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.4.2 Positive Assortativity and Degree Correlation . . . . . . . . . . 188
5.4.3 Clustering in Growing Random Networks . . . . . . . . . . . . . 190
5.4.4 A Meetings-Based Network Formation Model . . . . . . . . . . 191
5.4.5 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
6 Strategic Network Formation 201
6.1 Pairwise Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
6.2 E¢ cient Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.2.1 E¢ ciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.2.2 Pareto E¢ ciency . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.3 Distance-Based Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
6.3.1 Externalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.3.2 Growing Networks and Ine¢ ciency . . . . . . . . . . . . . . . . 213
6.3.3 The Price of Anarchy and the Price of Stability . . . . . . . . . 215
6.4 A Co-Author Model and Negative Externalities . . . . . . . . . . . . . 218
6.5 Small Worlds in an Islands-Connections Model . . . . . . . . . . . . . . 221
6.5.1 The Islands-Connections Model . . . . . . . . . . . . . . . . . . 222
6.6 A General Tension Between Stability and E¢ ciency . . . . . . . . . . . 226
6.6.1 Transfers: Taxing and Subsidizing Links . . . . . . . . . . . . . 226
6.6.2 Component Balance . . . . . . . . . . . . . . . . . . . . . . . . 228
6.6.3 Equal Treatment of Equals . . . . . . . . . . . . . . . . . . . . . 229
6.6.4 Incompatibility of Pairwise Stability and E¢ ciency . . . . . . . 230
6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7 Di¤usion through Networks 239
7.1 Background: The Bass Model . . . . . . . . . . . . . . . . . . . . . . . 241
7.2 Spread of Information and Disease . . . . . . . . . . . . . . . . . . . . 243
7.2.1 Percolation, Component Size, Immunity, and Di¤usion . . . . . 243
7.2.2 Breakdown, Attack and Failure of Networks, and Immunization 249
7.2.3 The SIR and SIS Models of Di¤usion . . . . . . . . . . . . . . . 251
7.2.4 The SIR Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
7.2.5 The SIS Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
7.2.6 Remarks on Models of Di¤usion . . . . . . . . . . . . . . . . . . 266
7.3 Search and Navigation on Networks . . . . . . . . . . . . . . . . . . . . 268
7.3.1 Navigating Random Networks . . . . . . . . . . . . . . . . . . . 268
7.3.2 Navigating Structured Networks: Taking Advantage of Homophily274
Social Structure and Navigation Speed . . . . . . . . . . . . . . 278
7.3.3
7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
8 Learning and Networks 287
8.1 Early Theory and Opinion Leaders . . . . . . . . . . . . . . . . . . . . 288
8.2 Bayesian and Observational Learning . . . . . . . . . . . . . . . . . . . 289
8.3 Imitation and Social In‡ uence Models: The DeGroot Model . . . . . . 293
8.3.1 Incorporating Media and Opinion Leaders . . . . . . . . . . . . 296
8.3.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
8.3.3 Consensus in Beliefs . . . . . . . . . . . . . . . . . . . . . . . . 302
8.3.4 Consensus and Non-Constant Updating Rules . . . . . . . . . . 303
8.3.5 Social In‡ uence . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
8.3.6 Segregation and Time to a Consensus . . . . . . . . . . . . . . 314
8.3.7 When a Consensus is Correct: Wise Crowds . . . . . . . . . . . 321
8.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
9 Decisions, Behavior, and Games on Networks 333
9.1 Decisions and Social Interaction . . . . . . . . . . . . . . . . . . . . . . 334
9.1.1 A Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 335
9.1.2 Individual by Individual Updating . . . . . . . . . . . . . . . . . 336
9.1.3 An Interaction Model with Network Structure . . . . . . . . . . 342
9.2 Graphical Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
9.2.1 Examples of Graphical Games . . . . . . . . . . . . . . . . . . . 349
9.2.2 Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
9.3 Semi-Anonymous Graphical Games . . . . . . . . . . . . . . . . . . . . 353
9.3.1 Payo¤s and Examples . . . . . . . . . . . . . . . . . . . . . . . 354
9.3.2 Complements and Substitutes . . . . . . . . . . . . . . . . . . . 356
9.3.3 Equilibria and Thresholds . . . . . . . . . . . . . . . . . . . . . 357
9.3.4 Comparing Behavior as the Network is Varied . . . . . . . . . . 359
9.4 Randomly Chosen Neighbors and Network Games . . . . . . . . . . . . 362
9.4.1 Degree and Behavior . . . . . . . . . . . . . . . . . . . . . . . . 364
9.4.2 Changes in Networks and Changes in Behavior . . . . . . . . . . 368
9.5 Richer Action Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
9.5.1 A Local Public Goods Model . . . . . . . . . . . . . . . . . . . 370
9.5.2 Quadratic Payo¤s and Strategic Complementarities . . . . . . . 376
9.6 Dynamic Behavior and Contagion . . . . . . . . . . . . . . . . . . . . . 380
9.7 Multiple Equilibria and Di¤usion in Network Games . . . . . . . . . . 385
9.7.1 Best Response Dynamics and Equilibria . . . . . . . . . . . . . 386
9.7.2 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
9.7.3 Equilibrium Behavior and Changes in the Environment . . . . . 389
9.8 Computing Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
9.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
9.10 Appendix: A Primer on Non-cooperative Game Theory . . . . . . . . . 405
9.10.1 Games in Normal Form . . . . . . . . . . . . . . . . . . . . . . . 405
9.10.2 Dominant Strategies . . . . . . . . . . . . . . . . . . . . . . . . 407
9.10.3 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . 408
9.10.4 Randomization and Mixed Strategies . . . . . . . . . . . . . . . 412
9.10.5 Sequentiality, Extensive-Form Games and Backward Induction . 415
9.10.6 Exercises on Games . . . . . . . . . . . . . . . . . . . . . . . . . 418
423
10 Networked Markets
10.1 The Social Embeddedness of Markets and Exchange . . . . . . . . . . . 424
10.1.1 The Use of Job-Contacts in Labor Markets . . . . . . . . . . . . 424
10.1.2 The Features of some Networked Markets . . . . . . . . . . . . . 425
10.1.3 Which Markets Should be Networked? . . . . . . . . . . . . . . 429
10.2 Networks in Labor Markets . . . . . . . . . . . . . . . . . . . . . . . . 432
10.2.1 Strong and Weak Ties . . . . . . . . . . . . . . . . . . . . . . . 432
10.2.2 A Networked Model of Employment . . . . . . . . . . . . . . . . 434
10.2.3 Duration Dependence . . . . . . . . . . . . . . . . . . . . . . . . 445
10.2.4 Education and Drop-Out Decisions . . . . . . . . . . . . . . . . 448
10.2.5 A Labor Market in a Homophilous Network . . . . . . . . . . . 450
10.2.6 Evidence and E¤ects of Networked Labor Markets . . . . . . . . 453
10.3 Models of Networked Markets . . . . . . . . . . . . . . . . . . . . . . . 456
10.3.1 Exchange Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 456
10.3.2 Bilateral Trading Models . . . . . . . . . . . . . . . . . . . . . . 460
10.3.3 Price Dispersion on Networks . . . . . . . . . . . . . . . . . . . 468
10.3.4 Collaboration Networks Among Firms . . . . . . . . . . . . . . 470
10.4 Some Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . 472
10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
479
11 Game-Theoretic Modeling of Network Formation
11.1 De...ning Stability and Equilibrium . . . . . . . . . . . . . . . . . . . . 480
11.1.1 An Extensive Form Game of Network Formation . . . . . . . . . 480
11.1.2 A Simultaneous Link-Announcement Game . . . . . . . . . . . . 481
11.1.3 Pairwise Nash Stability . . . . . . . . . . . . . . . . . . . . . . . 484
11.1.4 Strong Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
11.2 The Existence of Stable Networks . . . . . . . . . . . . . . . . . . . . . 488
11.2.1 Improving Paths, Dynamics, and Cycles . . . . . . . . . . . . . 488
11.2.2 The Existence of Strongly Stable Networks . . . . . . . . . . . . 494
11.3 Directed Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
11.3.1 Two-Way Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
11.3.2 Distance-Based Utility . . . . . . . . . . . . . . . . . . . . . . . 496
11.3.3 One-Way Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
11.4 Stochastic Strategic Models of Network Formation . . . . . . . . . . . . 502
11.4.1 Random Improving Paths and Stochastic Stability . . . . . . . 503
11.4.2 Stochastically Stable Networks . . . . . . . . . . . . . . . . . . 506
11.4.3 Stochastic Stability Coupled with Behavior . . . . . . . . . . . . 511
11.5 Farsighted Network Formation . . . . . . . . . . . . . . . . . . . . . . . 511
11.6 Transfers and Network Formation . . . . . . . . . . . . . . . . . . . . . 516
11.6.1 Forming Network Relationships and Bargaining . . . . . . . . . 516
11.6.2 A Network Formation Game with Transfers . . . . . . . . . . . 518
11.7 Weighted Network Formation . . . . . . . . . . . . . . . . . . . . . . . 520
11.8 Agent-Based Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
11.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
12 Allocation Rules, Networks, and Cooperative Games 531
12.1 Cooperative Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . 532
12.1.1 Transferable Utility (TU) Cooperative Games . . . . . . . . . . 533
12.1.2 Allocating the Value . . . . . . . . . . . . . . . . . . . . . . . . 534
12.1.3 The Shapley Value . . . . . . . . . . . . . . . . . . . . . . . . . 535
12.1.4 The Core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
12.2 Communication Games . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
12.2.1 The Myerson Value . . . . . . . . . . . . . . . . . . . . . . . . . 539
12.3 Networks and Allocation Rules . . . . . . . . . . . . . . . . . . . . . . 540
12.3.1 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
12.3.2 Allocation Rules . . . . . . . . . . . . . . . . . . . . . . . . . . 541
12.3.3 Some Properties of Allocation Rules . . . . . . . . . . . . . . . 542
12.3.4 Egalitarian Allocation Rules . . . . . . . . . . . . . . . . . . . . 543
12.3.5 The Myerson Value in Network Settings . . . . . . . . . . . . . 544
12.3.6 Equal Bargaining Power, Fairness, and the Myerson Value . . . 545
12.3.7 Pairwise Stable Networks under the Myerson Value . . . . . . . 547
12.4 Allocations Rules when Networks are Formed . . . . . . . . . . . . . . 549
12.4.1 De...ning Allocation Rules from Network Formation Possibilities 553
12.4.2 The Core in Network Settings . . . . . . . . . . . . . . . . . . . 554
12.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
12.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
13 Observing and Measuring Social Interaction 561
13.1 Speci...cation and Identi...cation . . . . . . . . . . . . . . . . . . . . . . 562
13.1.1 Speci...cation and Omitted Variables . . . . . . . . . . . . . . . . 562
13.1.2 The Re‡ ection Problem and Identi...cation . . . . . . . . . . . . 566
13.1.3 Laboratory and Field Experiments . . . . . . . . . . . . . . . . 571
13.2 Community Structures, Block Models, and Latent Spaces . . . . . . . . 573
13.2.1 Communities and Blocks . . . . . . . . . . . . . . . . . . . . . . 574
13.2.2 Methods for Identifying Community Structures . . . . . . . . . 576
13.2.3 Stochastic Block Models and Communities . . . . . . . . . . . . 585
13.2.4 Maximum-Likelihood Estimation of Communities . . . . . . . . 587
13.2.5 Latent Space Estimation . . . . . . . . . . . . . . . . . . . . . . 589
13.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
14 Afterword 593
Bibliography 595


Another Social Networks Books
Download