The Mathematics of Finite Networks: An Introduction to Operator Graph Theory

Description

Since the early eighteenth century, the theory of networks and graphs has matured into an indispensable tool for describing countless real-world phenomena. However, the study of large-scale features of a network often requires unrealistic limits, such as taking the network size to infinity or assuming a continuum. These asymptotic and analytic approaches can significantly diverge from real or simulated networks when applied at the finite scales of real-world applications. This book offers an approach to overcoming these limitations by introducing operator graph theory, an exact, non-asymptotic set of tools combining graph theory with operator calculus. The book is intended for mathematicians, physicists, and other scientists interested in discrete finite systems and their graph-theoretical description, and in delineating the abstract algebraic structures that characterise such systems. All the necessary background on graph theory and operator calculus is included for readers to understand the potential applications of operator graph theory. Preface page ix 1 Introduction 1 PART I OPERATOR GRAPH THEORY 2 Classical Graph Theory: The Mathematical Description of Networks 13 2.1 Graphs and Networks 13 2.2 Graph Measures 26 2.3 Graph Models 60 2.4 Finite Graph Theory 81 3 Operator Calculus: The Mapping between Vector Spaces 88 3.1 Vector Spaces 88 3.2 Operations on Vector Spaces 93 3.3 Mappings between Vector Spaces 101 3.4 Algebras of Operators 105 3.5 Special Operators 113 4 Operator Graph Theory: The Mathematics of Finite Networks 117 4.1 From Operations on Graphs to Operator Graphs 117 4.2 Operator Graph Theory 139 4.3 Transforming Operator Graphs 152 4.4 Measuring Operator Graphs 163 4.5 Generating Operator Graphs 169 PART II APPLICATIONS 5 Generating Graphs 181 5.1 Erd ̋os–R ́enyi Random Graphs 181 5.2 Gilbert Random Graphs 200 5.3 Watts–Strogatz Random Graphs 205 5.4 Barab ́asi–Albert Random Graphs 216 5.5 Random Graphs with Arbitrary Degree Distribution 226 5.6 Randomised Square Grid Graphs 231 6 Measuring Graphs 238 6.1 Total Adjacency of Random Graphs and Digraphs 238 6.2 Asymmetry Index of Random Digraphs 243 6.3 Clustering Coefficient of Random Digraphs 249 6.4 Walks in Gilbert Random Digraphs 264 6.5 Node Degrees of Barab ́asi–Albert Random Graphs 276 6.6 Paths in Randomised Square Grid Graphs 280 6.7 Challenges and Limitations 285 7 Transforming Graphs 291 7.1 Positional Chess Graphs 291 7.2 Generation of Positional Chess Graphs 297 7.3 Transformation of Positional Chess Graphs 321 Afterthought 325 Bibliography 327 Index of Notations 333 Subject Index 336