ID: cs/0512105

A study of the edge-switching Markov-chain method for the generation of random graphs

December 29, 2005

View on ArXiv
Alexandre O. Stauffer, Valmir C. Barbosa
Computer Science
Discrete Mathematics

We study the problem of generating connected random graphs with no self-loops or multiple edges and that, in addition, have a given degree sequence. The generation method we focus on is the edge-switching Markov-chain method, whose functioning depends on a parameter w related to the method's core operation of an edge switch. We analyze two existing heuristics for adjusting w during the generation of a graph and show that they result in a Markov chain whose stationary distribution is uniform, thus ensuring that generation occurs uniformly at random. We also introduce a novel w-adjusting heuristic which, even though it does not always lead to a Markov chain, is still guaranteed to converge to the uniform distribution under relatively mild conditions. We report on extensive computer experiments comparing the three heuristics' performance at generating random graphs whose node degrees are distributed as power laws.

Similar papers 1

Uniform sampling of undirected and directed graphs with a fixed degree sequence

December 3, 2009

92% Match
Annabell Berger, Matthias Müller-Hannemann
Discrete Mathematics
Data Structures and Algorith...

Many applications in network analysis require algorithms to sample uniformly at random from the set of all graphs with a prescribed degree sequence. We present a Markov chain based approach which converges to the uniform distribution of all realizations for both the directed and undirected case. It remains an open challenge whether these Markov chains are rapidly mixing. For the case of directed graphs, we also explain in this paper that a popular switching algorithm fails ...

Find SimilarView on arXiv

On the uniform generation of random graphs with prescribed degree sequences

December 1, 2003

92% Match
R. Milo, N. Kashtan, S. Itzkovitz, ... , Alon U.
Statistical Mechanics
Molecular Networks

Random graphs with prescribed degree sequences have been widely used as a model of complex networks. Comparing an observed network to an ensemble of such graphs allows one to detect deviations from randomness in network properties. Here we briefly review two existing methods for the generation of random graphs with arbitrary degree sequences, which we call the ``switching'' and ``matching'' methods, and present a new method based on the ``go with the winners'' Monte Carlo met...

Find SimilarView on arXiv

Constructing and Sampling Graphs with a Prescribed Joint Degree Distribution

March 24, 2011

91% Match
Isabelle Stanton, Ali Pinar
Data Structures and Algorith...

One of the most influential recent results in network analysis is that many natural networks exhibit a power-law or log-normal degree distribution. This has inspired numerous generative models that match this property. However, more recent work has shown that while these generative models do have the right degree distribution, they are not good models for real life networks due to their differences on other important metrics like conductance. We believe this is, in part, beca...

Find SimilarView on arXiv

Fast generation of random connected graphs with prescribed degrees

February 22, 2005

91% Match
Fabien LIAFA, Regal Ur-R Lip6 Viger, Matthieu LIAFA Latapy
Networking and Internet Arch...
Disordered Systems and Neura...
Discrete Mathematics

We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm designed for practical use both because of its ability to generate very large graphs (efficiency) and because it is easy to implement (simplicity). We focus on a family of heuristics for which we prove optimality conditions, and show how this optimality can be reached in practice. We then propose a d...

Find SimilarView on arXiv

Generating graphs randomly

January 13, 2022

91% Match
Catherine Greenhill
Combinatorics

Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system. Researchers may wish to compare a network of interest to a "typical" graph from a family (or ensemble) of graphs which are similar in some way. One way to do this is to take a sample of several random graphs from the family, to gather information about what is "typical". Hence there is a need for algorithms which can generate graphs uniformly (or approximate...

Find SimilarView on arXiv

Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees

November 4, 2021

90% Match
Daniel Allendorf, Ulrich Meyer, ... , Tran Hung
Data Structures and Algorith...

The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g. to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes, called edge switches, to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate un...

Find SimilarView on arXiv

Engineering Uniform Sampling of Graphs with a Prescribed Power-law Degree Sequence

October 28, 2021

90% Match
Daniel Allendorf, Ulrich Meyer, Manuel Penschuck, ... , Wormald Nick
Data Structures and Algorith...

We consider the following common network analysis problem: given a degree sequence $\mathbf{d} = (d_1, \dots, d_n) \in \mathbb N^n$ return a uniform sample from the ensemble of all simple graphs with matching degrees. In practice, the problem is typically solved using Markov Chain Monte Carlo approaches, such as Edge-Switching or Curveball, even if no practical useful rigorous bounds are known on their mixing times. In contrast, Arman et al. sketch Inc-Powerlaw, a novel and m...

Find SimilarView on arXiv

Fast uniform generation of random graphs with given degree sequences

May 9, 2019

90% Match
Andrii Arman, Pu Gao, Nicholas Wormald
Combinatorics
Data Structures and Algorith...
Probability

In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that $\Delta^4=O(m)$, where $\Delta$ is the maximal degree and $m$ is the number of edges,the algorithm runs in expected time $O(m)$. Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected time $O(m^2\Delta^2)$ for the same family of degree sequences. Our method uses a novel ingredient which progressively rel...

Find SimilarView on arXiv

Generating constrained random graphs using multiple edge switches

December 14, 2010

90% Match
Lionel Tabourier, Camille Roth, Jean-Philippe Cointet
Social and Information Netwo...
Physics and Society

The generation of random graphs using edge swaps provides a reliable method to draw uniformly random samples of sets of graphs respecting some simple constraints, e.g. degree distributions. However, in general, it is not necessarily possible to access all graphs obeying some given con- straints through a classical switching procedure calling on pairs of edges. We therefore propose to get round this issue by generalizing this classical approach through the use of higher-order ...

Find SimilarView on arXiv

Efficient and exact sampling of simple graphs with given arbitrary degree sequence

February 15, 2010

89% Match
Genio Charo I. Del, Hyunju Kim, ... , Bassler Kevin E.
Physics and Society
Statistical Mechanics
Data Structures and Algorith...

Uniform sampling from graphical realizations of a given degree sequence is a fundamental component in simulation-based measurements of network observables, with applications ranging from epidemics, through social networks to Internet modeling. Existing graph sampling methods are either link-swap based (Markov-Chain Monte Carlo algorithms) or stub-matching based (the Configuration Model). Both types are ill-controlled, with typically unknown mixing times for link-swap methods ...

Find SimilarView on arXiv