Network Science offers comprehensive insight on network analysis and network optimization algorithms, with simple step-by-step guides and examples throughout, and a thorough introduction and history of network science, explaining the key concepts and the type of data needed for network analysis, ensuring a smooth learning experience for readers. It also includes a detailed introduction to multiple network optimization algorithms, including linear assignment, network flow and routing problems.
The text is comprised of five chapters, focusing on subgraphs, network analysis, network optimization, and includes a list of case studies, those of which include influence factors in telecommunications, fraud detection in taxpayers, identifying the viral effect in purchasing, finding optimal routes considering public transportation systems, among many others. This insightful book shows how to apply algorithms to solve complex problems in real-life scenarios and shows the math behind these algorithms, enabling readers to learn how to develop them and scrutinize the results.
Written by a highly qualified author with significant experience in the field, Network Science also includes information on: - Sub-networks, covering connected components, bi-connected components, community detection, k-core decomposition, reach network, projection, nodes similarity and pattern matching - Network centrality measures, covering degree, influence, clustering coefficient, closeness, betweenness, eigenvector, PageRank, hub and authority - Network optimization, covering clique, cycle, linear assignment, minimum-cost network flow, maximum network flow problem, minimum cut, minimum spanning tree, path, shortest path, transitive closure, traveling salesman problem, vehicle routing problem and topological sort
With in-depth and authoritative coverage of the subject and many case studies to convey concepts clearly, Network Science is a helpful training resource for professional and industry workers in, telecommunications, insurance, retail, banking, healthcare, public sector, among others, plus as a supplementary reading for an introductory Network Science course for undergraduate students.
Table of Contents
Preface x
Acknowledgments xiii
About the Author xiv
About the Book xv
1 Concepts in Network Science 1
1.1 Introduction 1
1.2 The Connector 2
1.3 History 3
1.3.1 A History in Social Studies 4
1.4 Concepts 5
1.4.1 Characteristics of Networks 7
1.4.2 Properties of Networks 7
1.4.3 Small World 8
1.4.4 Random Graphs 11
1.5 Network Analytics 12
1.5.1 Data Structure for Network Analysis and Network Optimization 13
1.5.1.1 Multilink and Self-Link 14
1.5.1.2 Loading and Unloading the Graph 15
1.5.2 Options for Network Analysis and Network Optimization Procedures 15
1.5.3 Summary Statistics 16
1.5.3.1 Analyzing the Summary Statistics for the Les Misérables Network 17
1.6 Summary 21
2 Subnetwork Analysis 23
2.1 Introduction 23
2.1.1 Isomorphism 25
2.2 Connected Components 26
2.2.1 Finding the Connected Components 27
2.3 Biconnected Components 35
2.3.1 Finding the Biconnected Components 36
2.4 Community 38
2.4.1 Finding Communities 45
2.5 Core 58
2.5.1 Finding k-Cores 59
2.6 Reach Network 62
2.6.1 Finding the Reach Network 65
2.7 Network Projection 70
2.7.1 Finding the Network Projection 72
2.8 Node Similarity 77
2.8.1 Computing Node Similarity 82
2.9 Pattern Matching 88
2.9.1 Searching for Subgraphs Matches 91
2.10 Summary 98
3 Network Centralities 101
3.1 Introduction 101
3.2 Network Metrics of Power and Influence 102
3.3 Degree Centrality 103
3.3.1 Computing Degree Centrality 103
3.3.2 Visualizing a Network 110
3.4 Influence Centrality 114
3.4.1 Computing the Influence Centrality 115
3.5 Clustering Coefficient 121
3.5.1 Computing the Clustering Coefficient Centrality 121
3.6 Closeness Centrality 124
3.6.1 Computing the Closeness Centrality 124
3.7 Betweenness Centrality 129
3.7.1 Computing the Between Centrality 130
3.8 Eigenvector Centrality 136
3.8.1 Computing the Eigenvector Centrality 137
3.9 PageRank Centrality 144
3.9.1 Computing the PageRank Centrality 144
3.10 Hub and Authority 151
3.10.1 Computing the Hub and Authority Centralities 152
3.11 Network Centralities Calculation by Group 157
3.11.1 By Group Network Centralities 158
3.12 Summary 164
4 Network Optimization 167
4.1 Introduction 167
4.1.1 History 167
4.1.2 Network Optimization in SAS Viya 170
4.2 Clique 170
4.2.1 Finding Cliques 172
4.3 Cycle 176
4.3.1 Finding Cycles 177
4.4 Linear Assignment 179
4.4.1 Finding the Minimum Weight Matching in a Worker-Task Problem 181
4.5 Minimum-Cost Network Flow 185
4.5.1 Finding the Minimum-Cost Network Flow in a Demand-Supply Problem 188
4.6 Maximum Network Flow Problem 194
4.6.1 Finding the Maximum Network Flow in a Distribution Problem 195
4.7 Minimum Cut 199
4.7.1 Finding the Minimum Cuts 201
4.8 Minimum Spanning Tree 205
4.8.1 Finding the Minimum Spanning Tree 206
4.9 Path 208
4.9.1 Finding Paths 211
4.10 Shortest Path 220
4.10.1 Finding Shortest Paths 223
4.11 Transitive Closure 235
4.11.1 Finding the Transitive Closure 236
4.12 Traveling Salesman Problem 239
4.12.1 Finding the Optimal Tour 243
4.13 Vehicle Routing Problem 249
4.13.1 Finding the Optimal Vehicle Routes for a Delivery Problem 253
4.14 Topological Sort 265
4.14.1 Finding the Topological Sort in a Directed Graph 266
4.15 Summary 268
5 Real-World Applications in Network Science 271
5.1 Introduction 271
5.2 An Optimal Tour Considering a Multimodal Transportation System - The Traveling Salesman Problem Example in Paris 272
5.3 An Optimal Beer Kegs Distribution - The Vehicle Routing Problem Example in Asheville 285
5.4 Network Analysis and Supervised Machine Learning Models to Predict COVID-19 Outbreaks 298
5.5 Urban Mobility in Metropolitan Cities 306
5.6 Fraud Detection in Auto Insurance Based on Network Analysis 312
5.7 Customer Influence to Reduce Churn and Increase Product Adoption 320
5.8 Community Detection to Identify Fraud Events in Telecommunications 324
5.9 Summary 328
Index 329
