ID: 1203.0877

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

March 5, 2012

View on ArXiv

Similar papers 2

On the uniform generation of random graphs with prescribed degree sequences

December 1, 2003

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

Are we there yet? When to stop a Markov chain while generating random graphs

February 15, 2012

87% Match
Jaideep Ray, Ali Pinar, C. Seshadhri
Social and Information Netwo...
Data Analysis, Statistics an...
Physics and Society

Markov chains are a convenient means of generating realizations of networks, since they require little more than a procedure for rewiring edges. If a rewiring procedure exists for generating new graphs with specified statistical properties, then a Markov chain sampler can generate an ensemble of graphs with prescribed characteristics. However, successive graphs in a Markov chain cannot be used when one desires independent draws from the distribution of graphs; the realization...

Find SimilarView on arXiv

A unifying framework for fast randomization of ecological networks with fixed (node) degrees

September 16, 2016

87% Match
Corrie Jacobien Carstens, Annabell Berger, Giovanni Strona
Combinatorics
Data Structures and Algorith...

The switching model is a Markov chain approach to sample graphs with fixed degree sequence uniformly at random. The recently invented Curveball algorithm for bipartite graphs applies several switches simultaneously (`trades'). Here, we introduce Curveball algorithms for simple (un)directed graphs which use single or simultaneous trades. We show experimentally that these algorithms converge magnitudes faster than the corresponding switching models.

Find SimilarView on arXiv

Evolving Clustered Random Networks

August 4, 2008

86% Match
Shweta Bansal, Shashank Khandelwal, Lauren Ancel Meyers
Discrete Mathematics
Physics and Society

We propose a Markov chain simulation method to generate simple connected random graphs with a specified degree sequence and level of clustering. The networks generated by our algorithm are random in all other respects and can thus serve as generic models for studying the impacts of degree distributions and clustering on dynamical processes as well as null models for detecting other structural properties in empirical networks.

Find SimilarView on arXiv

Stochastic Evolution of Graphs using Local Moves

January 21, 2006

86% Match
Hal Finkel
High Energy Physics - Theory

Inspired by theories such as Loop Quantum Gravity, a class of stochastic graph dynamics was studied in an attempt to gain a better understanding of discrete relational systems under the influence of local dynamics. Unlabeled graphs in a variety of initial configurations were evolved using local rules, similar to Pachner moves, until they reached a size of tens of thousands of vertices. The effect of using different combinations of local moves was studied and a clear relations...

Find SimilarView on arXiv

Random graphs with given vertex degrees and switchings

January 28, 2019

86% Match
Svante Janson
Probability
Combinatorics

Random graphs with a given degree sequence are often constructed using the configuration model, which yields a random multigraph. We may adjust this multigraph by a sequence of switchings, eventually yielding a simple graph. We show that, assuming essentially a bounded second moment of the degree distribution, this construction with the simplest types of switchings yields a simple random graph with an almost uniform distribution, in the sense that the total variation distance...

Find SimilarView on arXiv

Statistical mechanics of random graphs

December 18, 2003

86% Match
Zdzislaw Burda, Jerzy Jurkiewicz, Andre Krzywicki
Statistical Mechanics

We discuss various aspects of the statistical formulation of the theory of random graphs, with emphasis on results obtained in a series of our recent publications.

Find SimilarView on arXiv

Connectedness matters: Construction and exact random sampling of connected graphs

September 8, 2020

86% Match
Szabolcs Horvát, Carl D. Modes
Physics and Society
Discrete Mathematics
Combinatorics

We describe a new method for the random sampling of connected networks with a specified degree sequence. We consider both the case of simple graphs and that of loopless multigraphs. The constraints of fixed degrees and of connectedness are two of the most commonly needed ones when constructing null models for the practical analysis of physical or biological networks. Yet handling these constraints, let alone combining them, is non-trivial. Our method builds on a recently intr...

Find SimilarView on arXiv

Moments of Uniform Random Multigraphs with Fixed Degree Sequences

September 19, 2019

85% Match
Philip S. Chodrow
Social and Information Netwo...
Probability
Data Analysis, Statistics an...
Physics and Society

We study the expected adjacency matrix of a uniformly random multigraph with fixed degree sequence $\mathbf{d} \in \mathbb{Z}_+^n$. This matrix arises in a variety of analyses of networked data sets, including modularity-maximization and mean-field theories of spreading processes. Its structure is well-understood for large, sparse, simple graphs: the expected number of edges between nodes $i$ and $j$ is roughly $\frac{d_id_j}{\sum_\ell{d_\ell}}$. Many network data sets are ne...

Find SimilarView on arXiv

Generating graphs randomly

January 13, 2022

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