## Percolation and Random Graphs

*Remco van der Hofstad*

### in New Perspectives in Stochastic Geometry

- 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.

## Random graphs: An introduction to the most basic of network models, the random graph

*M. E. J. Newman*

### in Networks: An Introduction

- 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

## Factor graphs and graph ensembles

*Marc Mézard and Andrea Montanari*

### in Information, Physics, and Computation

- 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

## Other network models: A brief introduction to two specialized network models, the small-world model and the exponential random graph

*M. E. J. Newman*

### in Networks: An Introduction

- 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.

## Random Directed and on‐Line Networks

*Mathew D. Penrose and Andrew R. Wade*

### in New Perspectives in Stochastic Geometry

- 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

## EQUILIBRIUM NETWORKS

*S. N. Dorogovtsev and J. F. F. Mendes*

### in Evolution of Networks: From Biological Nets to the Internet and WWW

- 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

## Random graphs with general degree distributions: This chapter describes more sophisticated random graph models that mimic networks with arbitrary degree distributions

*M. E. J. Newman*

### in Networks: An Introduction

- 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

## Networks: An Introduction

*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

## Ising models on random graph

*Marc Mézard and Andrea Montanari*

### in Information, Physics, and Computation

- 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

## When Formulas Freeze: Phase Transitions in Computation

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- 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

## Outlook

*Sergey N. Dorogovtsev*

### in Lectures on Complex Networks

- 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

## Analysis of Crossword Puzzle Difficulty Using a Random Graph Process

*John K. McSweeney*

### in The Mathematics of Various Entertaining Subjects: Research in Recreational Math

- 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

## Exponential Random Graph Models, P* and Actor Oriented Models

*Thomas W. Valente*

### in Social Networks and Health: Models, Methods, and Applications

- 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

## Network economy

*František Slanina*

### in Essentials of Econophysics Modelling

- 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

## Random graphs

*Mark Newman*

### in Networks

- 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

##
Classifying Networks with *dk*-Series

*Marija Mitrović Dankulov, Guido Caldarelli, Santo Fortunato, and Dmitri Krioukov*

### in Multiplex and Multilevel Networks

- 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

## Random graph ensembles

*A.C.C. Coolen, A. Annibale, and E.S. Roberts*

### in Generating Random Networks and Graphs

- 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

## Soft constraints: exponential random graph models

*A.C.C. Coolen, A. Annibale, and E.S. Roberts*

### in Generating Random Networks and Graphs

- 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

## Generating Random Networks and Graphs

*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

## Random models of networks

*Ernesto Estrada*

### in The Structure of Complex Networks: Theory and Applications

- 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