Remco van der Hofstad
- Published in print:
- 2009
- Published Online:
- February 2010
- ISBN:
- 9780199232574
- eISBN:
- 9780191716393
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199232574.003.0006
- Subject:
- Mathematics, Geometry / Topology
In this chapter, we define percolation and random graph models, and survey the features of these models.
In this chapter, we define percolation and random graph models, and survey the features of these models.
M. E. J. Newman
- Published in print:
- 2010
- Published Online:
- September 2010
- ISBN:
- 9780199206650
- eISBN:
- 9780191594175
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199206650.003.0012
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter discusses the basic mathematics of the random graph G(n, p), focusing particularly on the degree distribution and component sizes, which are two of the model's most illuminating ...
More
This chapter discusses the basic mathematics of the random graph G(n, p), focusing particularly on the degree distribution and component sizes, which are two of the model's most illuminating characteristics. The techniques developed in this chapter prove useful for some of the more complex models examined later in the book. Exercises are provided at the end of the chapter.Less
This chapter discusses the basic mathematics of the random graph G(n, p), focusing particularly on the degree distribution and component sizes, which are two of the model's most illuminating characteristics. The techniques developed in this chapter prove useful for some of the more complex models examined later in the book. Exercises are provided at the end of the chapter.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Probabilistic systems involving a large number of simple variables with mutual dependencies appear recurrently in several fields of science. It is often the case that such dependencies can be ...
More
Probabilistic systems involving a large number of simple variables with mutual dependencies appear recurrently in several fields of science. It is often the case that such dependencies can be factorized in a non-trivial way, and distinct variables interact only ‘locally’. This important structural property plays a crucial role. It is described here in a graphical language — the one of factor graphs. Ensembles of probability distributions naturally map to ensemble of random graphs, or hypergraphs. Several basic properties of these ensembles are discussed, from the appearance of a giant component to the motifs appearing in their local structure. The graph description is a necessary background for the understanding of message passing algorithms.Less
Probabilistic systems involving a large number of simple variables with mutual dependencies appear recurrently in several fields of science. It is often the case that such dependencies can be factorized in a non-trivial way, and distinct variables interact only ‘locally’. This important structural property plays a crucial role. It is described here in a graphical language — the one of factor graphs. Ensembles of probability distributions naturally map to ensemble of random graphs, or hypergraphs. Several basic properties of these ensembles are discussed, from the appearance of a giant component to the motifs appearing in their local structure. The graph description is a necessary background for the understanding of message passing algorithms.
M. E. J. Newman
- Published in print:
- 2010
- Published Online:
- September 2010
- ISBN:
- 9780199206650
- eISBN:
- 9780191594175
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199206650.003.0015
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter describes two of the best-known additional types of network models: the small-world model and exponential random graphs. Exercises are provided at the end of the chapter.
This chapter describes two of the best-known additional types of network models: the small-world model and exponential random graphs. Exercises are provided at the end of the chapter.
Mathew D. Penrose and Andrew R. Wade
- Published in print:
- 2009
- Published Online:
- February 2010
- ISBN:
- 9780199232574
- eISBN:
- 9780191716393
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199232574.003.0007
- Subject:
- Mathematics, Geometry / Topology
Various random spatial graphs defined on partially ordered point sets have been treated recently in the literature: these are discussed in the framework of the minimal directed spanning forest. ...
More
Various random spatial graphs defined on partially ordered point sets have been treated recently in the literature: these are discussed in the framework of the minimal directed spanning forest. Global distributional limits are discussed, and examples given both of Gaussian and non‐Gaussian limiting cases.Less
Various random spatial graphs defined on partially ordered point sets have been treated recently in the literature: these are discussed in the framework of the minimal directed spanning forest. Global distributional limits are discussed, and examples given both of Gaussian and non‐Gaussian limiting cases.
S. N. Dorogovtsev and J. F. F. Mendes
- Published in print:
- 2003
- Published Online:
- January 2010
- ISBN:
- 9780198515906
- eISBN:
- 9780191705670
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198515906.003.0005
- Subject:
- Physics, Soft Matter / Biological Physics
This chapter discusses the organization of equilibrium networks. These include the classical random graphs, uncorrelated and correlated networks, and the Watts–Strogatz model (small-world networks). ...
More
This chapter discusses the organization of equilibrium networks. These include the classical random graphs, uncorrelated and correlated networks, and the Watts–Strogatz model (small-world networks). The chapter starts with a general discussion of equilibrium network models and then explains how to build a number of specific equilibrium networks.Less
This chapter discusses the organization of equilibrium networks. These include the classical random graphs, uncorrelated and correlated networks, and the Watts–Strogatz model (small-world networks). The chapter starts with a general discussion of equilibrium network models and then explains how to build a number of specific equilibrium networks.
M. E. J. Newman
- Published in print:
- 2010
- Published Online:
- September 2010
- ISBN:
- 9780199206650
- eISBN:
- 9780191594175
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199206650.003.0013
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
The previous chapter looked at the classic random graph model, in which pairs of vertices are connected at random with uniform probabilities. Although this model has proved tremendously useful as a ...
More
The previous chapter looked at the classic random graph model, in which pairs of vertices are connected at random with uniform probabilities. Although this model has proved tremendously useful as a source of insight into the structure of networks, it also has a number of serious shortcomings. Chief among these is its degree distribution, which follows the Poisson distribution which is quite different from the degree distributions seen in most real-world networks. This chapter shows how to create more sophisticated random graph models, which incorporate arbitrary degree distributions and yet are still exactly solvable for many of their properties in the limit of large network size. The fundamental mathematical tool used to derive the results of this chapter is the probability generating function. Exercises are provided at the end of the chapter.Less
The previous chapter looked at the classic random graph model, in which pairs of vertices are connected at random with uniform probabilities. Although this model has proved tremendously useful as a source of insight into the structure of networks, it also has a number of serious shortcomings. Chief among these is its degree distribution, which follows the Poisson distribution which is quite different from the degree distributions seen in most real-world networks. This chapter shows how to create more sophisticated random graph models, which incorporate arbitrary degree distributions and yet are still exactly solvable for many of their properties in the limit of large network size. The fundamental mathematical tool used to derive the results of this chapter is the probability generating function. Exercises are provided at the end of the chapter.
Mark Newman
- Published in print:
- 2010
- Published Online:
- September 2010
- ISBN:
- 9780199206650
- eISBN:
- 9780191594175
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199206650.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet ...
More
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet and the wide availability of inexpensive computers have made it possible to gather and analyze network data on a large scale, and the development of a variety of new theoretical tools has allowed us to extract new knowledge from many different kinds of networks. The study of networks is broadly interdisciplinary and important developments have occurred in many fields, including mathematics, physics, computer and information sciences, biology, and the social sciences. This book brings together the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas. Subjects covered include the measurement and structure of networks in many branches of science, methods for analyzing network data, including methods developed in physics, statistics, and sociology, the fundamentals of graph theory, computer algorithms, and spectral methods, mathematical models of networks, including random graph models and generative models, and theories of dynamical processes taking place on networks.Less
The scientific study of networks, including computer networks, social networks, and biological networks, has received an enormous amount of interest in the last few years. The rise of the Internet and the wide availability of inexpensive computers have made it possible to gather and analyze network data on a large scale, and the development of a variety of new theoretical tools has allowed us to extract new knowledge from many different kinds of networks. The study of networks is broadly interdisciplinary and important developments have occurred in many fields, including mathematics, physics, computer and information sciences, biology, and the social sciences. This book brings together the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas. Subjects covered include the measurement and structure of networks in many branches of science, methods for analyzing network data, including methods developed in physics, statistics, and sociology, the fundamentals of graph theory, computer algorithms, and spectral methods, mathematical models of networks, including random graph models and generative models, and theories of dynamical processes taking place on networks.
Cristopher Moore and Stephan Mertens
- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0014
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Certain formulas, such as the 3-SAT formula, undergo a phase transition from almost certain satisfiability to almost certain unsatisfiability when the number of constraints per variable reaches a ...
More
Certain formulas, such as the 3-SAT formula, undergo a phase transition from almost certain satisfiability to almost certain unsatisfiability when the number of constraints per variable reaches a critical threshold. This transition is comparable to the freezing of water and also occurs in many other NP-complete problems such as graph coloring and integer partitioning. This chapter first considers some experimental results on random 3-SAT and assumes that a phase transition exists. It then explores some simple phase transitions in random graphs and shows how to compute the size of k-cores, along with the degrees at which they first appear. It also looks at random k-SAT formulas and demonstrates how to prove upper and lower bounds on the critical density of clauses. Furthermore, it describes simple search algorithms as flows through state space before concluding with a discussion of recent advances inspired by techniques in statistical physics.Less
Certain formulas, such as the 3-SAT formula, undergo a phase transition from almost certain satisfiability to almost certain unsatisfiability when the number of constraints per variable reaches a critical threshold. This transition is comparable to the freezing of water and also occurs in many other NP-complete problems such as graph coloring and integer partitioning. This chapter first considers some experimental results on random 3-SAT and assumes that a phase transition exists. It then explores some simple phase transitions in random graphs and shows how to compute the size of k-cores, along with the degrees at which they first appear. It also looks at random k-SAT formulas and demonstrates how to prove upper and lower bounds on the critical density of clauses. Furthermore, it describes simple search algorithms as flows through state space before concluding with a discussion of recent advances inspired by techniques in statistical physics.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0017
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter studies two problems of statistical physics: the ferromagnet and the spin glass, on large random graphs with fixed degree profile. It describes the use of the replica symmetric cavity ...
More
This chapter studies two problems of statistical physics: the ferromagnet and the spin glass, on large random graphs with fixed degree profile. It describes the use of the replica symmetric cavity method in this context, and studies its stability. The analysis relies on physicists methods, without any attempt at being rigorous. It provides a complete solution of the ferromagnetic problem at all temperatures. In the spin glass case, the replica symmetric solution is asymptotically correct in the high temperature ‘paramagnetic’ phase, but it turns out to be wrong in the spin glass phase. The phase transition temperature can be computed exactly.Less
This chapter studies two problems of statistical physics: the ferromagnet and the spin glass, on large random graphs with fixed degree profile. It describes the use of the replica symmetric cavity method in this context, and studies its stability. The analysis relies on physicists methods, without any attempt at being rigorous. It provides a complete solution of the ferromagnetic problem at all temperatures. In the spin glass case, the replica symmetric solution is asymptotically correct in the high temperature ‘paramagnetic’ phase, but it turns out to be wrong in the spin glass phase. The phase transition temperature can be computed exactly.
Sergey N. Dorogovtsev
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780199548927
- eISBN:
- 9780191720574
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199548927.003.0015
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
In this concluding section of the text, the three major milestones marking the history of the exploration of networks are indicated. These are: Leonhard Euler's work (1735), the introduction of ...
More
In this concluding section of the text, the three major milestones marking the history of the exploration of networks are indicated. These are: Leonhard Euler's work (1735), the introduction of random graphs (1950s), and the launch of the large-scale study of complex networks (the end of the 1990s). A list of a few particularly hot and prospective topics in complex networks is presented.Less
In this concluding section of the text, the three major milestones marking the history of the exploration of networks are indicated. These are: Leonhard Euler's work (1735), the introduction of random graphs (1950s), and the launch of the large-scale study of complex networks (the end of the 1990s). A list of a few particularly hot and prospective topics in complex networks is presented.
John K. McSweeney
- Published in print:
- 2015
- Published Online:
- October 2017
- ISBN:
- 9780691164038
- eISBN:
- 9781400881338
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691164038.003.0008
- Subject:
- Mathematics, History of Mathematics
This chapter quantifies the dynamics of a crossword puzzle by using a network structure to model it. Specifically, the chapter determines how the interaction between the structure of cells in the ...
More
This chapter quantifies the dynamics of a crossword puzzle by using a network structure to model it. Specifically, the chapter determines how the interaction between the structure of cells in the puzzle and the difficulty of the clues affects the puzzle's solvability. It first builds an iterative stochastic process that exactly describes the solution and obtains its deterministic approximation, which gives a very simple fixed-point equation to solve for the final solution proportion. The chapter then shows via simulation on actual crosswords from the Sunday edition of The New York Times that certain network properties inherent to actual crossword networks are important predictors of the final solution size of the puzzle.Less
This chapter quantifies the dynamics of a crossword puzzle by using a network structure to model it. Specifically, the chapter determines how the interaction between the structure of cells in the puzzle and the difficulty of the clues affects the puzzle's solvability. It first builds an iterative stochastic process that exactly describes the solution and obtains its deterministic approximation, which gives a very simple fixed-point equation to solve for the final solution proportion. The chapter then shows via simulation on actual crosswords from the Sunday edition of The New York Times that certain network properties inherent to actual crossword networks are important predictors of the final solution size of the puzzle.
Thomas W. Valente
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780195301014
- eISBN:
- 9780199777051
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195301014.003.0009
- Subject:
- Public Health and Epidemiology, Epidemiology
This chapter describes in non-technical terms how researchers can determine whether empirical networks exhibit certain structural properties (centrality, triadic transitivity, etc.) using a ...
More
This chapter describes in non-technical terms how researchers can determine whether empirical networks exhibit certain structural properties (centrality, triadic transitivity, etc.) using a statistical test. These models are referred to as exponential random graph models (ERGM), named after the technique used to generate simulated networks, which can then be compared to the observed network in order to statistically assess network properties. The chapter provides an exposition of the actor oriented co-evolution model, which extends the cross-sectional ERGM framework to model longitudinal processes. These models can be used to determine what behaviors drive social network evolution, and whether social relationships influence behavioral changes. Public health examples are used throughout to illustrate concepts.Less
This chapter describes in non-technical terms how researchers can determine whether empirical networks exhibit certain structural properties (centrality, triadic transitivity, etc.) using a statistical test. These models are referred to as exponential random graph models (ERGM), named after the technique used to generate simulated networks, which can then be compared to the observed network in order to statistically assess network properties. The chapter provides an exposition of the actor oriented co-evolution model, which extends the cross-sectional ERGM framework to model longitudinal processes. These models can be used to determine what behaviors drive social network evolution, and whether social relationships influence behavioral changes. Public health examples are used throughout to illustrate concepts.
František Slanina
- Published in print:
- 2013
- Published Online:
- January 2014
- ISBN:
- 9780199299683
- eISBN:
- 9780191747038
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199299683.003.0007
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter is devoted to structural modelling of economic phenomena, based on the theory of complex networks. Its mathematical basis is the graph theory, which is briefly introduced. Then, we ...
More
This chapter is devoted to structural modelling of economic phenomena, based on the theory of complex networks. Its mathematical basis is the graph theory, which is briefly introduced. Then, we proceed to the properties of random graph ensembles, the prominent representatives being the Erdős-Rényi graphs; and to the graph processes, where the Barabási-Albert graphs are the most important example. The abstract models are compared to empirical data, where we stress the small-world phenomenon and the ubiquitous scale-free networks. As a specific example, we present the empirical findings for the networks of electronic commerce, namely the on-line auctions and combined products-reviewers networks.Less
This chapter is devoted to structural modelling of economic phenomena, based on the theory of complex networks. Its mathematical basis is the graph theory, which is briefly introduced. Then, we proceed to the properties of random graph ensembles, the prominent representatives being the Erdős-Rényi graphs; and to the graph processes, where the Barabási-Albert graphs are the most important example. The abstract models are compared to empirical data, where we stress the small-world phenomenon and the ubiquitous scale-free networks. As a specific example, we present the empirical findings for the networks of electronic commerce, namely the on-line auctions and combined products-reviewers networks.
Mark Newman
- Published in print:
- 2018
- Published Online:
- October 2018
- ISBN:
- 9780198805090
- eISBN:
- 9780191843235
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198805090.003.0011
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
An introduction to the mathematics of the Poisson random graph, the simplest model of a random network. The chapter starts with a definition of the model, followed by derivations of basic properties ...
More
An introduction to the mathematics of the Poisson random graph, the simplest model of a random network. The chapter starts with a definition of the model, followed by derivations of basic properties like the mean degree, degree distribution, and clustering coefficient. This is followed with a detailed derivation of the large-scale structural properties of random graphs, including the position of the phase transition at which a giant component appears, the size of the giant component, the average size of the small components, and the expected diameter of the network. The chapter ends with a discussion of some of the shortcomings of the random graph model.Less
An introduction to the mathematics of the Poisson random graph, the simplest model of a random network. The chapter starts with a definition of the model, followed by derivations of basic properties like the mean degree, degree distribution, and clustering coefficient. This is followed with a detailed derivation of the large-scale structural properties of random graphs, including the position of the phase transition at which a giant component appears, the size of the giant component, the average size of the small components, and the expected diameter of the network. The chapter ends with a discussion of some of the shortcomings of the random graph model.
Marija Mitrović Dankulov, Guido Caldarelli, Santo Fortunato, and Dmitri Krioukov
- Published in print:
- 2018
- Published Online:
- December 2018
- ISBN:
- 9780198809456
- eISBN:
- 9780191847073
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198809456.003.0003
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
“Classifying Networks with dk-Series” discusses the dk-series and how it can be extended to describe the structure of multiplex networks. One way to address the problem of interdependence among ...
More
“Classifying Networks with dk-Series” discusses the dk-series and how it can be extended to describe the structure of multiplex networks. One way to address the problem of interdependence among network properties is to find which of them are significant for a given network, and thus for its function. The standard procedure for identifying a significant property X and its dependence on some other property Y is to generate a set of random graphs that have property Y but are random in all other respects, and then to check whether the property X is also characteristic of these graphs. It has been proposed that these properties can be identified by using dk-series. This chapter applies this approach to three networks, finding that they differ in the randomness of their structure. Furthermore, it shows that this approach can be extended to describe in a systematic way the structure of multiplex networks.Less
“Classifying Networks with dk-Series” discusses the dk-series and how it can be extended to describe the structure of multiplex networks. One way to address the problem of interdependence among network properties is to find which of them are significant for a given network, and thus for its function. The standard procedure for identifying a significant property X and its dependence on some other property Y is to generate a set of random graphs that have property Y but are random in all other respects, and then to check whether the property X is also characteristic of these graphs. It has been proposed that these properties can be identified by using dk-series. This chapter applies this approach to three networks, finding that they differ in the randomness of their structure. Furthermore, it shows that this approach can be extended to describe in a systematic way the structure of multiplex networks.
A.C.C. Coolen, A. Annibale, and E.S. Roberts
- Published in print:
- 2017
- Published Online:
- May 2017
- ISBN:
- 9780198709893
- eISBN:
- 9780191780172
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198709893.003.0003
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter presents some theoretical tools for defining random graph ensembles systematically via soft or hard topological constraints including working through some properties of the Erdös-Rényi ...
More
This chapter presents some theoretical tools for defining random graph ensembles systematically via soft or hard topological constraints including working through some properties of the Erdös-Rényi random graph ensemble, which is the simplest non-trivial random graph ensemble where links appear between two nodes with a fixed probability p. The chapter sets out the central representation of graph generation as the result of a discrete-time Markovian stochastic process. This unites the two flavours of graph generation approaches – because they can be viewed as simply moving forwards or backwards through this representation. It is possible to define a random graph by an algorithm, and then calculate the associated stationary probability. The alternative approach is to specify sampling weights and then to construct an algorithm that will have these weights as the stationary probabilities upon convergence.Less
This chapter presents some theoretical tools for defining random graph ensembles systematically via soft or hard topological constraints including working through some properties of the Erdös-Rényi random graph ensemble, which is the simplest non-trivial random graph ensemble where links appear between two nodes with a fixed probability p. The chapter sets out the central representation of graph generation as the result of a discrete-time Markovian stochastic process. This unites the two flavours of graph generation approaches – because they can be viewed as simply moving forwards or backwards through this representation. It is possible to define a random graph by an algorithm, and then calculate the associated stationary probability. The alternative approach is to specify sampling weights and then to construct an algorithm that will have these weights as the stationary probabilities upon convergence.
A.C.C. Coolen, A. Annibale, and E.S. Roberts
- Published in print:
- 2017
- Published Online:
- May 2017
- ISBN:
- 9780198709893
- eISBN:
- 9780191780172
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198709893.003.0004
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Exponential random graph models (ERGMs) provide conceptually elegant recipes for generating soft-constrained random graphs. This chapter begins by explaining the theory and describing how to properly ...
More
Exponential random graph models (ERGMs) provide conceptually elegant recipes for generating soft-constrained random graphs. This chapter begins by explaining the theory and describing how to properly specify an ERGM, including demonstrating Lagrange’s method to derive the values of the model parameters that correspond to the desired constraints. Three ERGMs, all with constraints depending linearly on the adjacency matrix, are solved exactly: the targeted total number of links, targeted individual node degrees and targeted number of two-way links in a directed graph. However, when the controlled features become more complicated, ERGMs have a tendency to produce graphs in extreme phases (very dense or very sparse). The two-star model and the Strauss model are worked through in detail using advanced techniques from statistical mechanics in order to analyze the phase transitions. The chapter closes with a discussion of the strengths and weaknesses of ERGMs as null models.Less
Exponential random graph models (ERGMs) provide conceptually elegant recipes for generating soft-constrained random graphs. This chapter begins by explaining the theory and describing how to properly specify an ERGM, including demonstrating Lagrange’s method to derive the values of the model parameters that correspond to the desired constraints. Three ERGMs, all with constraints depending linearly on the adjacency matrix, are solved exactly: the targeted total number of links, targeted individual node degrees and targeted number of two-way links in a directed graph. However, when the controlled features become more complicated, ERGMs have a tendency to produce graphs in extreme phases (very dense or very sparse). The two-star model and the Strauss model are worked through in detail using advanced techniques from statistical mechanics in order to analyze the phase transitions. The chapter closes with a discussion of the strengths and weaknesses of ERGMs as null models.
Ton Coolen, Alessia Annibale, and Ekaterina Roberts
- Published in print:
- 2017
- Published Online:
- May 2017
- ISBN:
- 9780198709893
- eISBN:
- 9780191780172
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198709893.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
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 ...
More
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.Less
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.
Ernesto Estrada
- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199591756
- eISBN:
- 9780191774959
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199591756.003.0012
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter describes random models frequently used for studying complex networks. These include the Erdös-Rényi, Barabási-Albert and its variations, small-world models of Watts-Strogatz and ...
More
This chapter describes random models frequently used for studying complex networks. These include the Erdös-Rényi, Barabási-Albert and its variations, small-world models of Watts-Strogatz and Kleinberg, and random geometric, range-dependent, lock-and-key, and stickiness models. It also discusses the topological properties of the networks generated with these modes, including clustering, metric, and spectral properties.Less
This chapter describes random models frequently used for studying complex networks. These include the Erdös-Rényi, Barabási-Albert and its variations, small-world models of Watts-Strogatz and Kleinberg, and random geometric, range-dependent, lock-and-key, and stickiness models. It also discusses the topological properties of the networks generated with these modes, including clustering, metric, and spectral properties.
