Search Results

Percolation and Random Graphs

Remco van der Hofstad

in New Perspectives in Stochastic Geometry

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

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

Factor graphs and graph ensembles

Marc Mézard and Andrea Montanari

in Information, Physics, and Computation

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

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

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

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

EQUILIBRIUM NETWORKS

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

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

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

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

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

Ising models on random graph

Marc Mézard and Andrea Montanari

in Information, Physics, and Computation

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

When Formulas Freeze: Phase Transitions in Computation

Cristopher Moore and Stephan Mertens

in The Nature of Computation

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

Outlook

Sergey N. Dorogovtsev

in Lectures on Complex Networks

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

Analysis of Crossword Puzzle Difficulty Using a Random Graph Process

John K. McSweeney

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

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

Exponential Random Graph Models, P* and Actor Oriented Models

Thomas W. Valente

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

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

Network economy

František Slanina

in Essentials of Econophysics Modelling

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

Random graphs

Mark Newman

in Networks

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

Classifying Networks with dk-Series

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

in Multiplex and Multilevel Networks

“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

Random graph ensembles

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

in Generating Random Networks and Graphs

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

Soft constraints: exponential random graph models

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

in Generating Random Networks and Graphs

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

Random models of networks

Ernesto Estrada

in The Structure of Complex Networks: Theory and Applications

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