ID: 1203.0877

Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties

March 5, 2012

View on ArXiv
E. S. Roberts, A. Annibale, A. C. C. Coolen
Condensed Matter
Disordered Systems and Neura...

We analyze the properties of degree-preserving Markov chains based on elementary edge switchings in undirected and directed graphs. We give exact yet simple formulas for the mobility of a graph (the number of possible moves) in terms of its adjacency matrix. This formula allows us to define acceptance probabilities for edge switchings, such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process).

Similar papers 1

Constrained Markovian dynamics of random graphs

May 26, 2009

96% Match
A. C. C. Coolen, Martino A. De, A. Annibale
Disordered Systems and Neura...

We introduce a statistical mechanics formalism for the study of constrained graph evolution as a Markovian stochastic process, in analogy with that available for spin systems, deriving its basic properties and highlighting the role of the `mobility' (the number of allowed moves for any given graph). As an application of the general theory we analyze the properties of degree-preserving Markov chains based on elementary edge switchings. We give an exact yet simple formula for t...

Find SimilarView on arXiv
E. S. Roberts, A. C. C. Coolen
Quantitative Methods

Randomising networks using a naive `accept-all' edge-swap algorithm is generally biased. Building on recent results for nondirected graphs, we construct an ergodic detailed balance Markov chain with non-trivial acceptance probabilities for directed graphs, which converges to a strictly uniform measure and is based on edge swaps that conserve all in- and out-degrees. The acceptance probabilities can also be generalized to define Markov chains that target any alternative desire...

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

December 29, 2005

89% Match
Alexandre O. Stauffer, Valmir C. Barbosa
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 distribu...

Find SimilarView on arXiv

Constructing and Sampling Graphs with a Prescribed Joint Degree Distribution

March 24, 2011

89% 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

Generating constrained random graphs using multiple edge switches

December 14, 2010

88% 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

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

December 3, 2009

87% 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

Random Networks Tossing Biased Coins

April 2, 2006

87% Match
F. Bassetti, M. Cosentino Lagomarsino, ... , Jona P.
Statistical Mechanics
Quantitative Methods

In statistical mechanical investigations on complex networks, it is useful to employ random graphs ensembles as null models, to compare with experimental realizations. Motivated by transcription networks, we present here a simple way to generate an ensemble of random directed graphs with, asymptotically, scale-free outdegree and compact indegree. Entries in each row of the adjacency matrix are set to be zero or one according to the toss of a biased coin, with a chosen probabi...

Find SimilarView on arXiv

A stopping criterion for Markov chains when generating independent random graphs

October 30, 2012

87% Match
J. Ray, A. Pinar, C. Seshadhri
Social and Information Netwo...
Discrete Mathematics
Physics and Society

Markov chains are convenient means of generating realizations of networks with a given (joint or otherwise) degree distribution, since they simply require a procedure for rewiring edges. The major challenge is to find the right number of steps to run such a chain, so that we generate truly independent samples. Theoretical bounds for mixing times of these Markov chains are too large to be practically useful. Practitioners have no useful guide for choosing the length, and tend ...

Find SimilarView on arXiv

Smaller Universes for Uniform Sampling of 0,1-matrices with fixed row and column sums

March 7, 2018

87% Match
Annabell Berger, Corrie Jacobien Carstens
Combinatorics

An important problem arising in the study of complex networks, for instance in community detection and motif finding, is the sampling of graphs with fixed degree sequence. The equivalent problem of generating random 0,1 matrices with fixed row and column sums is frequently used as a quantitative tool in ecology. It has however proven very challenging to design sampling algorithms that are both fast and unbiased. This article focusses on Markov chain approaches for sampling,...

Find SimilarView on arXiv

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

November 4, 2021

87% 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