Understanding Large Temporal Networks and Spatial Networks

Vladimir Batagelj, Department of Mathematics, Faculty of Mathematics and Physics, University of Ljubljana, Slovenia Patrick Doreian, Faculty of Social Sciences, University of Ljubljana, Slovenia andDepartment of Sociology, University of Pittsburgh, USA Anuška Ferligoj, Faculty of Social Sciences, University of Ljubljana, Slovenia Nataša Kejžar, Faculty of Medicine, Institute for Biostatistics and Medical Informatics, University of Ljubljana, Slovenia

Preface xiii

1 Temporal and Spatial Networks 1

1.1 Modern Social Network Analysis 1

1.2 Network Sizes 3

1.3 Substantive Concerns 3

1.3.1 Citation Networks 3

1.3.2 Other Types of Large Networks 7

1.4 Computational Methods 10

1.5 Data for Large Temporal Networks 12

1.5.1 The Main Datasets 12

1.5.2 Secondary Datasets 14

1.6 Induction and Deduction 16

2 Foundations of Methods for Large Networks 18

2.1 Networks 18

2.1.1 Descriptions of Networks 20

2.1.2 Degrees 21

2.1.3 Descriptions of Properties 21

2.1.4 Visualizations of Properties 22

2.2 Types of Networks 22

2.2.1 Temporal Networks 23

2.2.2 Multirelational Networks 25

2.2.3 Two-mode Networks 28

2.3 Large Networks 28

2.3.1 Small and Middle Sized Networks 29

2.3.2 Large Networks 30

2.3.3 Complexity of Algorithms 30

2.4 Strategies for Analyzing Large Networks 32

2.5 Statistical Network Measures 33

2.5.1 Using Pajek and R Together 35

2.5.2 Fitting Distributions 35

2.6 Subnetworks 37

2.6.1 Clusters, Clusterings, Partitions, Hierarchies 37

2.6.2 Contractions of Clusters 38

2.6.3 Subgraphs 40

2.6.4 Cuts 42

2.7 Connectivity Properties of Networks 46

2.7.1 Walks 46

2.7.2 Equivalence Relations and Partitions 47

2.7.3 Connectivity 48

2.7.4 Condensation 49

2.7.5 Bow-tie Structure of the Web Graph 50

2.7.6 The Internal Structure of Strong Components 51

2.7.7 Bi-connectivity and -connectivity 51

2.8 Triangular and Short Cycle Connectivities 53

2.9 Islands 54

2.9.1 Defining Islands 55

2.9.2 Some Properties of Islands 56

2.10 Cores and Generalized Cores 57

2.10.1 Cores 58

2.10.2 Generalized Cores 59

2.11 Important Vertices in Networks 61

2.11.1 Degrees, Closeness, Betweenness and Other Indices 63

2.11.2 Clustering 65

2.11.3 Computing Further Indices Through Functions 66

2.12 Transition to Methods for Large Networks 68

3 Methods for Large Networks 69

3.1 Acyclic Networks 71

3.1.1 Some Basic Properties of Acyclic Networks 71

3.1.2 Compatible Numberings: Depth and Topological Order 72

3.1.3 Topological Orderings and Functions on Acyclic Networks 74

3.2 SPC Weights in Acyclic Networks 75

3.2.1 Citation Networks 75

3.2.2 Analysis of Citation Networks 76

3.2.3 Search Path Count Method 77

3.2.4 Computing SPLC and SPNP Weights 77

3.2.5 Implementation Details 78

3.2.6 Vertex Weights 78

3.2.7 General Properties of Weights 79

3.2.8 SPC Weights 80

3.3 Probabilistic Flow in Acyclic Network 81

3.4 Nonacyclic Citation Networks 82

3.5 Two-mode Networks from Data Tables 84

3.5.1 Multiplication of Two-mode Networks 85

3.6 Bibliographic Networks 88

3.6.1 Co-authorship Networks 88

3.6.2 Collaboration Networks 89

3.6.3 Other Derived Networks 92

3.7 Weights 94

3.7.1 Normalizations of Weights 94

3.7.2 -Rings 94

3.7.3 4-Rings and Analysis of Two-mode Networks 95

3.7.4 Two-mode Cores 96

3.8 Pathfinder 96

3.8.1 Pathfinder Algorithms 100

3.8.2 Computing the Closure Over the Pathfinder Semiring 101

3.8.3 Spanish Algorithms 101

3.8.4 A Sparse Network Algorithm 102

3.9 Clustering, Blockmodeling, and Community Detection 102

3.9.1 The Louvain Method and VOS 102

3.10 Clustering Symbolic Data 103

3.10.1 Symbolic Objects Described with Distributions 103

3.10.2 The Leaders Method 105

3.10.3 An AgglomerativeMethod 107

3.11 Approaches to Temporal Networks 107

3.11.1 Journeys -- Walks in Temporal Networks 108

3.11.2 Measures 110

3.11.3 Problems and Algorithms 111

3.11.4 Evolution 114

3.12 Levels of Analysis 114

3.13 Transition to Substantive Topics 116

4 Scientific Citation and Other Bibliographic Networks 117

4.1 The Centrality Citation Network 117

4.2 Preliminary Data Analyses 118

4.2.1 Temporal Distribution of Publications 119

4.2.2 Degree Distributions of the Centrality Literature 121

4.2.3 Types of Works 124

4.2.4 The Boundary Problem 126

4.3 Transforming a Citation Network into an Acyclic Network 128

4.3.1 Checking for the Presence of Cycles 128

4.3.2 Dealing with Cycles in Citation Networks 133

4.4 The Most ImportantWorks 134

4.5 SPC Weights 134

4.5.1 Obtaining SPC Weights and Drawing Main Paths 135

4.5.2 The Main Path of the Centrality Citation Network 135

4.6 Line Cuts 139

4.7 Line Islands 141

4.7.1 The Main Island 143

4.7.2 A Geophysics and Meteorology Line Island 145

4.7.3 An Optical Network Line Island 150

4.7.4 A Partial Summary of Main Path and Line Island Results 154

4.8 Other Relevant Subnetworks for a Bounded Network 155

4.9 Collaboration Networks 157

4.9.1 Macros for Collaboration Networks 158

4.9.2 An Initial Attempt of Analyses of Collaboration Networks 159

4.10 A Brief Look at the SNA Literature SN5 Networks 160

4.11 On the Centrality and SNA Collaboration Networks 173

References 173

5 Citation Patterns in Temporal United States Patent Data 175

5.1 Patents 175

5.2 Supreme Court Decisions Regarding Patents 179

5.2.1 Co-cited Decisions 179

5.2.2 Citations Between Co-cited Decisions 182

5.3 The 1976--2006 Patent Data 183

5.4 Structural Variables Through Time 184

5.4.1 Temporally Specific Networks 184

5.4.2 Shrinking Specific Patent Citation Networks 186

5.4.3 Structural Properties 187

5.5 Some Patterns of Technological Development 188

5.5.1 Structural Properties of Temporally Specific Networks 190

5.6 Important Subnetworks 193

5.6.1 Line Islands 194

5.6.2 Line Islands with Patents Tagged by Keywords 196

5.6.3 Vertex Islands 201

5.7 Citation Patterns 202

5.7.1 Patents from 1976, Cited Through to 2006 204

5.7.2 Patents from 1987, Cited Through to 2006 209

5.8 Comparing Citation Patterns for Two Time Intervals 211

5.9 Summary and Conclusions 214

6 The US Supreme Court Citation Network 216

6.1 Introduction 217

6.2 Co-cited Islands of Supreme Court Decisions 219

6.3 A Native American Line Island 222

6.3.1 Forced Removal of Native American Populations 222

6.3.2 RegulatingWhites on Native American Lands 224

6.3.3 Curtailing the Authority of Native American Courts 224

6.3.4 Taxing Native Americans and Enforcing External Laws 225

6.3.5 The Presence of Non-Native Americans on Native American Lands 226

6.3.6 Some Later Developments 227

6.3.7 A Partial Summary 227

6.4 A ‘Perceived Threats to Social Order’ Line Island 228

6.4.1 Perceived Threats to Social Order 228

6.4.2 The Structures of the Threats to Social Order Line Island 230

6.4.3 Decisions Involving Communists and Socialists 230

6.4.4 Restrictions of Labor Groups Organizing 236

6.4.5 Restrictions of African Americans Organizing 237

6.4.6 Jehovah’sWitnesses as a Perceived Threat 239

6.4.7 Obscenity as a Threat to Social Order 243

6.5 Other Perceived Threats 246

6.6 The Dred Scott Decision 250

6.6.1 Citations from Dred Scott 251

6.6.2 Citations to Dred Scott 253

6.6.3 Methodological Implications of Dred Scott 260

6.7 Further Reflections on the Supreme Court Citation Network 261

7 Football as the World’s Game 263

7.1 A Brief Historical Overview 264

7.2 Football Clubs 264

7.3 Football Players 266

7.4 Football in England 267

7.5 Player Migrations 268

7.6 Institutional Arrangements and the Organization of Football 269

7.7 Court Rulings 271

7.8 Specific Factors Impacting Football Migration 272

7.9 Some Arguments and Propositions 272

7.10 Some Preliminary Results 278

7.10.1 The Non-English Presence in the EPL 279

7.10.2 Player Fitness 289

7.10.3 Starting Clubs for English Players 292

7.10.4 General Features of the Top Five European Leagues 295

7.10.5 Flows of Footballers into the Top European Leagues 301

7.11 Player Ages When Recruited to the EPL 303

7.12 A Partial Summary of Results 305

8 Networks of Player Movements to the EPL 308

8.1 Success in the EPL 308

8.2 The Overall Presence of Other Countries in the EPL 311

8.3 Network Flows of Footballers Between Clubs to Reach the EPL 312

8.3.1 Moving Directly into the EPL from Local and Non-local Clubs 313

8.3.2 Direct Moves of Players to the EPL from Non-EPL Clubs 315

8.4 Moves from EPL Clubs 318

8.4.1 The 1992--1996 Time Slice Flows with at Least Three Moves 318

8.4.2 The 1997--2001 Time Slice Flows with at Least Three Moves 322

8.4.3 The 2002--2006 Time Slice Flows with at Least Three Moves 323

8.5 Moves Solely Within the EPL 324

8.5.1 Loans 324

8.5.2 Transfers 326

8.6 All Trails of Footballers to the EPL 330

8.6.1 Counted Features of Trails to the EPL 331

8.6.2 Clustering Player Trails 335

8.6.3 Interpreting the Clusters of Player Careers 350

8.7 Summary and Conclusions 350

9 Mapping Spatial Diversity in the United States of America 353

9.1 Mapping Nations as Spatial Units of the United States 354

9.1.1 The Counties of the United States 357

9.2 Representing Networks in Space 359

9.3 Clustering with a Relational Constraint 360

9.3.1 Conditions for Hierarchical Clustering Methods 361

9.3.2 Clustering with a Relational Constraint 363

9.3.3 An AgglomerativeMethod for Relational Constraints 365

9.3.4 Hierarchies 367

9.3.5 Fast Agglomerative Clustering Algorithms 368

9.4 Data for Constrained Spatial Clustering 369

9.4.1 Discriminant Analysis for Garreau’s Nations 369

9.5 Clustering the US Counties with a Spatial Relational Constraint 374

9.5.1 The Eight Garreau Nations in the USA 375

9.5.2 The Ten Woodard Nations in the USA 379

9.6 Summary 381

10 On Studying Large Networks 382

10.1 Substance 382

10.2 Methods, Techniques, and Algorithms 384

10.3 Network Data 385

10.4 Surprises and Issues Triggered by Them 388

10.5 FutureWork 390

10.6 Two Final Comments 393

Appendix: Data Documentation 395

A.1 Bibliographic Networks 395

A.1.1 Centrality Literature Networks 397

A.1.2 SNA Literature 399

A.2 Patent Data 400

A.3 Supreme Court Data 401

A.4 Football Data 403

A.4.1 Core Data 403

A.4.2 Ancillary Data 413

A.5 The USA Spatial County Network 415

References 419

Person Index 428

Subject Index 432