Generating random networks and graphs / Ton Coolen, Alessia Annibale, and Ekaterina Roberts
- Author:
- Coolen, A. C. C. (Anthony C. C.), 1960-
- Published:
- Oxford : Oxford University Press, 2017.
- Edition:
- First edition.
- Physical Description:
- 1 online resource : illustrations (black and white)
- Additional Creators:
- Annibale, Alessia and Roberts, Ekaterina
Access Online
- Oxford scholarship online: ezaccess.libraries.psu.edu
- Contents:
- Machine generated contents note: pt. I THE BASICS -- 1.Introduction -- 2.Definitions and concepts -- 2.1.Definitions of graphs and their local characteristics -- 2.2.Macroscopic characterizations of graphs -- 2.3.Solutions of exercises -- 3.Random graph ensembles -- 3.1.The Erdos--Renyi graph ensemble -- 3.2.Graph ensembles with hard or soft topological constraints -- 3.3.The link between ensembles and algorithms -- 3.4.Solutions of exercises -- pt. II RANDOM GRAPH ENSEMBLES -- 4.Soft constraints: exponential random graph models -- 4.1.Definitions and basic properties of ERGMs -- 4.2.ERGMs that can be solved exactly -- 4.3.ERGMs with phase transitions: the two-star model -- 4.4.ERGMs with phase transitions: the Strauss (triangle) model -- 4.5.Stochastic block models for graphs with community structure -- 4.6.Strengths and weaknesses of ERGMs as null models -- 4.7.Solutions of exercises -- 5.Ensembles with hard constraints -- 5.1.Basic properties and tools -- 5.2.Nondirected graphs with hard-constrained number of links -- 5.3.Prescribed degree statistics and hard-constrained number of links -- 5.4.Ensembles with prescribed numbers of links and two-stars -- 5.5.Ensembles with constrained degrees and short loops -- 5.6.Solutions of exercises -- pt. III GENERATING GRAPHS FROM GRAPH ENSEMBLES -- 6.Markov Chain Monte Carlo sampling of graphs -- 6.1.The Markov Chain Monte Carlo sampling method -- 6.2.MCMC sampling for exponential random graph models -- 6.3.MCMC sampling for graph ensembles with hard constraints -- 6.4.Properties of move families -- hinge flips and edge swaps -- 6.5.Solutions of exercises -- 7.Graphs with hard constraints: further applications and extensions -- 7.1.Uniform versus non-uniform sampling of candidate moves -- 7.2.Graphs with a prescribed degree distribution and number of links -- 7.3.Ensembles with controlled degrees and degree correlations -- 7.4.Generating graphs with prescribed degrees and correlations -- 7.5.Edge swaps revisited -- 7.6.Non-uniform sampling of allowed edge swaps -- 7.7.Non-uniform sampling from a restricted set of moves: a hybrid MCMC algorithm -- 7.8.Extensions to directed graphs -- 7.9.Solutions of exercises -- pt. IV GRAPHS DEFINED BY ALGORITHMS -- 8.Network growth algorithms -- 8.1.Configuration model -- 8.2.Preferential attachment and scale-free networks -- 8.3.Analyzing growth algorithms -- 8.4.Solutions of exercises -- 9.Specific constructions -- 9.1.Watts-Strogatz model and the `small world' property -- 9.2.Geometric graphs -- 9.3.Planar graphs -- 9.4.Weighted graphs -- 9.5.Solutions of exercises -- pt. V FURTHER TOPICS -- 10.Graphs on structured spaces -- 10.1.Temporal networks -- 10.2.Multiplex graphs -- 10.3.Networks with labelled nodes -- 10.4.Relations and connections between models -- 10.5.Solutions of exercises -- 11.Applications of random graphs -- 11.1.Power grids -- 11.2.Social networks -- 11.3.Food webs -- 11.4.World Wide Web -- 11.5.Protein-protein interaction networks -- Key symbols and terminology -- Appendix A The delta distribution -- Appendix B Clustering and correlations in Erdos-Rnyi graphs -- B.1.Clustering coefficients -- B.2.Degree correlations in the sparse regime -- Appendix C Solution of the two-star exponential random graph model (ERGM) in the sparse regime -- Appendix D Steepest descent integration -- Appendix E Number of sparse graphs with prescribed average degree and degree variance -- Appendix F Evolution of graph mobilities for edge-swap dynamics -- Appendix G Number of graphs with prescribed degree sequence -- Appendix H Degree correlations in ensembles with constrained degrees -- Appendix I Evolution of triangle and square counters due to ordered edge swaps -- Appendix J Algorithms -- J.1.Algorithms based on link flips -- J.2.MCMC algorithms sampling from graphs with hard constraints -- J.3.Algorithms based on hinge flips -- J.4.Algorithms based on edge swaps -- J.5.Growth Algorithms -- J.6.Auxiliary routines.
- Summary:
- 'Generating Random Networks and Graphs' 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'.
- Subject(s):
- ISBN:
- 9780191780172 (ebook)
- Audience Notes:
- Specialized.
- Note:
- This edition previously issued in print: 2017.
- Bibliography Note:
- Includes bibliographical references and index.
View MARC record | catkey: 28938115