Generating random networks and graphs

This book supports researchers who need to generate random networks, or who are interested in the theoretical study of random graphs. The coverage includes exponential random graphs (where the targeted probability of each network appearing in the ensemble is specified), growth algorithms (i.e. preferential attachment and the stub-joining configuration model), special constructions (e.g. geometric graphs and Watts Strogatz models) and graphs on structured spaces (e.g. multiplex networks). The presentation aims to be a complete starting point, including details of both theory and implementation, as well as discussions of the main strengths and weaknesses of each approach. It includes extensive references for readers wishing to go further. The material is carefully structured to be accessible to researchers from all disciplines while also containing rigorous mathematical analysis (largely based on the techniques of statistical mechanics) to support those wishing to further develop or implement the theory of random graph generation. This book is aimed at the graduate student or advanced undergraduate. It includes many worked examples, numerical simulations and exercises making it suitable for use in teaching. Explicit pseudocode algorithms are included to make the ideas easy to apply. Datasets are becoming increasingly large and network applications wider and more sophisticated. Testing hypotheses against properly specified control cases (null models) is at the heart of the ‘scientific method’. Knowledge on how to generate controlled and unbiased random graph ensembles is vital for anybody wishing to apply network science in their research. Cover 1 Preface 6 Acknowledgements 7 Contents 8 Part I The basics 12 1 Introduction 14 2 Definitions and concepts 20 2.1 Definitions of graphs and their local characteristics 20 2.2 Macroscopic characterizations of graphs 22 2.3 Solutions of exercises 28 3 Random graph ensembles 30 3.1 The Erdös–Rényi graph ensemble 31 3.2 Graph ensembles with hard or soft topological constraints 33 3.3 The link between ensembles and algorithms 36 3.4 Solutions of exercises 39 Part II Random graph ensembles 42 4 Soft constraints: exponential random graph models 44 4.1 Definitions and basic properties of ERGMs 44 4.2 ERGMs that can be solved exactly 47 4.3 ERGMs with phase transitions: the two-star model 51 4.4 ERGMs with phase transitions: the Strauss (triangle) model 58 4.5 Stochastic block models for graphs with community structure 68 4.6 Strengths and weaknesses of ERGMs as null models 70 4.7 Solutions of exercises 73 5 Ensembles with hard constraints 75 5.1 Basic properties and tools 75 5.2 Nondirected graphs with hard-constrained number of links 79 5.3 Prescribed degree statistics and hard-constrained number of links 81 5.4 Ensembles with prescribed numbers of links and two-stars 84 5.5 Ensembles with constrained degrees and short loops 86 5.6 Solutions of exercises 90 Part III Generating graphs from graph ensembles 92 6 Markov Chain Monte Carlo sampling of graphs 94 6.1 The Markov Chain Monte Carlo sampling method 94 6.2 MCMC sampling for exponential random graph models 100 6.3 MCMC sampling for graph ensembles with hard constraints 105 6.4 Properties of move families – hinge flips and edge swaps 108 6.5 Solutions of exercises 113 7 Graphs with hard constraints: further applications and extensions 116 7.1 Uniform versus non-uniform sampling of candidate moves 116 7.2 Graphs with a prescribed degree distribution and number of links 123 7.3 Ensembles with controlled degrees and degree correlations 128 7.4 Generating graphs with prescribed degrees and correlations 132 7.5 Edge swaps revisited 139 7.6 Non-uniform sampling of allowed edge swaps 142 7.7 Non-uniform sampling from a restricted set of moves: a hybrid MCMC algorithm 146 7.8 Extensions to directed graphs 150 7.9 Solutions of exercises 152 Part IV Graphs defined by algorithms 162 8 Network growth algorithms 164 8.1 Configuration model 164 8.2 Preferential attachment and scale-free networks 168 8.3 Analyzing growth algorithms 174 8.4 Solutions of exercises 177 9 Specific constructions 180 9.1 Watts–Strogatz model and the 'small world' property 180 9.2 Geometric graphs 184 9.3 Planar graphs 188 9.4 Weighted graphs 190 9.5 Solutions of exercises 192 Part V Further topics 196 10 Graphs on structured spaces 198 10.1 Temporal networks 198 10.2 Multiplex graphs 204 10.3 Networks with labelled nodes 208 10.4 Relations and connections between models 213 10.5 Solutions of exercises 215 11 Applications of random graphs 218 11.1 Power grids 218 11.2 Social networks 219 11.3 Food webs 223 11.4 World Wide Web 226 11.5 Protein–protein interaction networks 227 Key symbols and terminology 232 Appendix A The delta distribution 240 Appendix B Clustering and correlations in Erdös–Rényi graphs 242 B.1 Clustering coefficients 242 B.2 Degree correlations in the sparse regime 244 Appendix C Solution of the two-star exponential random graph model (ERGM) in the sparse regime 247 Appendix D Steepest descent integration 251 Appendix E Number of sparse graphs with prescribed average degree and degree variance 253 Appendix F Evolution of graph mobilities for edge-swap dynamics 255 Appendix G Number of graphs with prescribed degree sequence 258 Appendix H Degree correlations in ensembles with constrained degrees 260 Appendix I Evolution of triangle and square counters due to ordered edge swaps 264 Appendix J Algorithms 267 J.1 Algorithms based on link flips 270 J.2 MCMC algorithms sampling from graphs with hard constraints 279 J.3 Algorithms based on hinge flips 282 J.4 Algorithms based on edge swaps 288 J.5 Growth Algorithms 293 J.6 Auxiliary routines 300 References 308 Index 320 Generating Random Networks Efficiently And Accurately Is An Important Challenge For Practical Applications, And An Interesting Question For Theoretical Study. This Book Presents And Discusses Common Methods Of Generating Random Graphs. It Begins With Approaches Such As Exponential Random Graph Models, Where The Targeted Probability Of Each Network Appearing In The Ensemble Is Specified. This Section Also Includes Degree-preserving Randomisation Algorithms, Where The Aim Is To Generate Networks With The Correct Number Of Links At Each Node, And Care Must Be Taken To Avoid Introducing A Bias. Separately, It Looks At Growth Style Algorithms (e.g. Preferential Attachment) Which Aim To Model A Real Process And Then To Analyse The Resulting Ensemble Of Graphs. It Also Covers How To Generate Special Types Of Graphs Including Modular Graphs, Graphs With Community Structure And Temporal Graphs. The Book Is Aimed At The Graduate Student Or Advanced Undergraduate. It Includes Many Worked Examples And Open Questions Making It Suitable For Use In Teaching. Explicit Pseudocode Algorithms Are Included Throughout The Book To Make The Ideas Straightforward To Apply. With Larger And Larger Datasets, It Is Crucial To Have Practical And Well-understood Tools. Being Able To Test A Hypothesis Against A Properly Specified Control Case Is At The Heart Of The 'scientific Method'. Hence, Knowledge On How To Generate Controlled And Unbiased Random Graph Ensembles Is Vital For Anybody Wishing To Apply Network Science In Their Research. This book describes how to correctly and efficiently generate random networks based on certain constraints. Being able to test a hypothesis against a properly specified control case is at the heart of the 'scientific method' This book aims to understand human cognition and psychology through a comprehensive computational theory of the mind, namely, a "cognitive architecture."