Understanding Large Temporal Networks and Spatial Networks

Vladimir Batagelj, Department of Mathematics, Faculty of Mathematics and Physics, University of Ljubljana, SloveniaPatrick 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 xiii1 Temporal and Spatial Networks 11.1 Modern Social Network Analysis 11.2 Network Sizes 31.3 Substantive Concerns 31.3.1 Citation Networks 31.3.2 Other Types of Large Networks 71.4 Computational Methods 101.5 Data for Large Temporal Networks 121.5.1 The Main Datasets 121.5.2 Secondary Datasets 141.6 Induction and Deduction 162 Foundations of Methods for Large Networks 182.1 Networks 182.1.1 Descriptions of Networks 202.1.2 Degrees 212.1.3 Descriptions of Properties 212.1.4 Visualizations of Properties 222.2 Types of Networks 222.2.1 Temporal Networks 232.2.2 Multirelational Networks 252.2.3 Two-mode Networks 282.3 Large Networks 282.3.1 Small and Middle Sized Networks 292.3.2 Large Networks 302.3.3 Complexity of Algorithms 302.4 Strategies for Analyzing Large Networks 322.5 Statistical Network Measures 332.5.1 Using Pajek and R Together 352.5.2 Fitting Distributions 352.6 Subnetworks 372.6.1 Clusters, Clusterings, Partitions, Hierarchies 372.6.2 Contractions of Clusters 382.6.3 Subgraphs 402.6.4 Cuts 422.7 Connectivity Properties of Networks 462.7.1 Walks 462.7.2 Equivalence Relations and Partitions 472.7.3 Connectivity 482.7.4 Condensation 492.7.5 Bow-tie Structure of the Web Graph 502.7.6 The Internal Structure of Strong Components 512.7.7 Bi-connectivity and -connectivity 512.8 Triangular and Short Cycle Connectivities 532.9 Islands 542.9.1 Defining Islands 552.9.2 Some Properties of Islands 562.10 Cores and Generalized Cores 572.10.1 Cores 582.10.2 Generalized Cores 592.11 Important Vertices in Networks 612.11.1 Degrees, Closeness, Betweenness and Other Indices 632.11.2 Clustering 652.11.3 Computing Further Indices Through Functions 662.12 Transition to Methods for Large Networks 683 Methods for Large Networks 693.1 Acyclic Networks 713.1.1 Some Basic Properties of Acyclic Networks 713.1.2 Compatible Numberings: Depth and Topological Order 723.1.3 Topological Orderings and Functions on Acyclic Networks 743.2 SPC Weights in Acyclic Networks 753.2.1 Citation Networks 753.2.2 Analysis of Citation Networks 763.2.3 Search Path Count Method 773.2.4 Computing SPLC and SPNP Weights 773.2.5 Implementation Details 783.2.6 Vertex Weights 783.2.7 General Properties of Weights 793.2.8 SPC Weights 803.3 Probabilistic Flow in Acyclic Network 813.4 Nonacyclic Citation Networks 823.5 Two-mode Networks from Data Tables 843.5.1 Multiplication of Two-mode Networks 853.6 Bibliographic Networks 883.6.1 Co-authorship Networks 883.6.2 Collaboration Networks 893.6.3 Other Derived Networks 923.7 Weights 943.7.1 Normalizations of Weights 943.7.2 -Rings 943.7.3 4-Rings and Analysis of Two-mode Networks 953.7.4 Two-mode Cores 963.8 Pathfinder 963.8.1 Pathfinder Algorithms 1003.8.2 Computing the Closure Over the Pathfinder Semiring 1013.8.3 Spanish Algorithms 1013.8.4 A Sparse Network Algorithm 1023.9 Clustering, Blockmodeling, and Community Detection 1023.9.1 The Louvain Method and VOS 1023.10 Clustering Symbolic Data 1033.10.1 Symbolic Objects Described with Distributions 1033.10.2 The Leaders Method 1053.10.3 An AgglomerativeMethod 1073.11 Approaches to Temporal Networks 1073.11.1 Journeys -- Walks in Temporal Networks 1083.11.2 Measures 1103.11.3 Problems and Algorithms 1113.11.4 Evolution 1143.12 Levels of Analysis 1143.13 Transition to Substantive Topics 1164 Scientific Citation and Other Bibliographic Networks 1174.1 The Centrality Citation Network 1174.2 Preliminary Data Analyses 1184.2.1 Temporal Distribution of Publications 1194.2.2 Degree Distributions of the Centrality Literature 1214.2.3 Types of Works 1244.2.4 The Boundary Problem 1264.3 Transforming a Citation Network into an Acyclic Network 1284.3.1 Checking for the Presence of Cycles 1284.3.2 Dealing with Cycles in Citation Networks 1334.4 The Most ImportantWorks 1344.5 SPC Weights 1344.5.1 Obtaining SPC Weights and Drawing Main Paths 1354.5.2 The Main Path of the Centrality Citation Network 1354.6 Line Cuts 1394.7 Line Islands 1414.7.1 The Main Island 1434.7.2 A Geophysics and Meteorology Line Island 1454.7.3 An Optical Network Line Island 1504.7.4 A Partial Summary of Main Path and Line Island Results 1544.8 Other Relevant Subnetworks for a Bounded Network 1554.9 Collaboration Networks 1574.9.1 Macros for Collaboration Networks 1584.9.2 An Initial Attempt of Analyses of Collaboration Networks 1594.10 A Brief Look at the SNA Literature SN5 Networks 1604.11 On the Centrality and SNA Collaboration Networks 173References 1735 Citation Patterns in Temporal United States Patent Data 1755.1 Patents 1755.2 Supreme Court Decisions Regarding Patents 1795.2.1 Co-cited Decisions 1795.2.2 Citations Between Co-cited Decisions 1825.3 The 1976--2006 Patent Data 1835.4 Structural Variables Through Time 1845.4.1 Temporally Specific Networks 1845.4.2 Shrinking Specific Patent Citation Networks 1865.4.3 Structural Properties 1875.5 Some Patterns of Technological Development 1885.5.1 Structural Properties of Temporally Specific Networks 1905.6 Important Subnetworks 1935.6.1 Line Islands 1945.6.2 Line Islands with Patents Tagged by Keywords 1965.6.3 Vertex Islands 2015.7 Citation Patterns 2025.7.1 Patents from 1976, Cited Through to 2006 2045.7.2 Patents from 1987, Cited Through to 2006 2095.8 Comparing Citation Patterns for Two Time Intervals 2115.9 Summary and Conclusions 2146 The US Supreme Court Citation Network 2166.1 Introduction 2176.2 Co-cited Islands of Supreme Court Decisions 2196.3 A Native American Line Island 2226.3.1 Forced Removal of Native American Populations 2226.3.2 RegulatingWhites on Native American Lands 2246.3.3 Curtailing the Authority of Native American Courts 2246.3.4 Taxing Native Americans and Enforcing External Laws 2256.3.5 The Presence of Non-Native Americans on Native American Lands 2266.3.6 Some Later Developments 2276.3.7 A Partial Summary 2276.4 A ‘Perceived Threats to Social Order’ Line Island 2286.4.1 Perceived Threats to Social Order 2286.4.2 The Structures of the Threats to Social Order Line Island 2306.4.3 Decisions Involving Communists and Socialists 2306.4.4 Restrictions of Labor Groups Organizing 2366.4.5 Restrictions of African Americans Organizing 2376.4.6 Jehovah’sWitnesses as a Perceived Threat 2396.4.7 Obscenity as a Threat to Social Order 2436.5 Other Perceived Threats 2466.6 The Dred Scott Decision 2506.6.1 Citations from Dred Scott 2516.6.2 Citations to Dred Scott 2536.6.3 Methodological Implications of Dred Scott 2606.7 Further Reflections on the Supreme Court Citation Network 2617 Football as the World’s Game 2637.1 A Brief Historical Overview 2647.2 Football Clubs 2647.3 Football Players 2667.4 Football in England 2677.5 Player Migrations 2687.6 Institutional Arrangements and the Organization of Football 2697.7 Court Rulings 2717.8 Specific Factors Impacting Football Migration 2727.9 Some Arguments and Propositions 2727.10 Some Preliminary Results 2787.10.1 The Non-English Presence in the EPL 2797.10.2 Player Fitness 2897.10.3 Starting Clubs for English Players 2927.10.4 General Features of the Top Five European Leagues 2957.10.5 Flows of Footballers into the Top European Leagues 3017.11 Player Ages When Recruited to the EPL 3037.12 A Partial Summary of Results 3058 Networks of Player Movements to the EPL 3088.1 Success in the EPL 3088.2 The Overall Presence of Other Countries in the EPL 3118.3 Network Flows of Footballers Between Clubs to Reach the EPL 3128.3.1 Moving Directly into the EPL from Local and Non-local Clubs 3138.3.2 Direct Moves of Players to the EPL from Non-EPL Clubs 3158.4 Moves from EPL Clubs 3188.4.1 The 1992--1996 Time Slice Flows with at Least Three Moves 3188.4.2 The 1997--2001 Time Slice Flows with at Least Three Moves 3228.4.3 The 2002--2006 Time Slice Flows with at Least Three Moves 3238.5 Moves Solely Within the EPL 3248.5.1 Loans 3248.5.2 Transfers 3268.6 All Trails of Footballers to the EPL 3308.6.1 Counted Features of Trails to the EPL 3318.6.2 Clustering Player Trails 3358.6.3 Interpreting the Clusters of Player Careers 3508.7 Summary and Conclusions 3509 Mapping Spatial Diversity in the United States of America 3539.1 Mapping Nations as Spatial Units of the United States 3549.1.1 The Counties of the United States 3579.2 Representing Networks in Space 3599.3 Clustering with a Relational Constraint 3609.3.1 Conditions for Hierarchical Clustering Methods 3619.3.2 Clustering with a Relational Constraint 3639.3.3 An AgglomerativeMethod for Relational Constraints 3659.3.4 Hierarchies 3679.3.5 Fast Agglomerative Clustering Algorithms 3689.4 Data for Constrained Spatial Clustering 3699.4.1 Discriminant Analysis for Garreau’s Nations 3699.5 Clustering the US Counties with a Spatial Relational Constraint 3749.5.1 The Eight Garreau Nations in the USA 3759.5.2 The Ten Woodard Nations in the USA 3799.6 Summary 38110 On Studying Large Networks 38210.1 Substance 38210.2 Methods, Techniques, and Algorithms 38410.3 Network Data 38510.4 Surprises and Issues Triggered by Them 38810.5 FutureWork 39010.6 Two Final Comments 393Appendix: Data Documentation 395A.1 Bibliographic Networks 395A.1.1 Centrality Literature Networks 397A.1.2 SNA Literature 399A.2 Patent Data 400A.3 Supreme Court Data 401A.4 Football Data 403A.4.1 Core Data 403A.4.2 Ancillary Data 413A.5 The USA Spatial County Network 415References 419Person Index 428Subject Index 432