ID: 1109.4590

Constructing and sampling directed graphs with given degree sequences

September 21, 2011

View on ArXiv

Similar papers 2

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 Scalable Null Model for Directed Graphs Matching All Degree Distributions: In, Out, and Reciprocal

October 19, 2012

86% Match
Nurcan Durak, Tamara G. Kolda, ... , Seshadhri C.
Social and Information Netwo...
Physics and Society

Degree distributions are arguably the most important property of real world networks. The classic edge configuration model or Chung-Lu model can generate an undirected graph with any desired degree distribution. This serves as a good null model to compare algorithms or perform experimental studies. Furthermore, there are scalable algorithms that implement these models and they are invaluable in the study of graphs. However, networks in the real-world are often directed, and h...

Find SimilarView on arXiv

Fast uniform generation of random graphs with given degree sequences

May 9, 2019

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

On the uniform generation of random graphs with prescribed degree sequences

December 1, 2003

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

Configuring Random Graph Models with Fixed Degree Sequences

August 1, 2016

86% Match
Bailey K. Fosdick, Daniel B. Larremore, ... , Ugander Johan
Methodology
Social and Information Netwo...
Data Analysis, Statistics an...
Physics and Society
Quantitative Methods

Random graph null models have found widespread application in diverse research communities analyzing network datasets, including social, information, and economic networks, as well as food webs, protein-protein interactions, and neuronal networks. The most popular family of random graph null models, called configuration models, are defined as uniform distributions over a space of graphs with a fixed degree sequence. Commonly, properties of an empirical network are compared to...

Find SimilarView on arXiv

Expand and Contract: Sampling graphs with given degrees and other combinatorial families

August 30, 2013

86% Match
James Y. Zhao
Data Structures and Algorith...
Probability

Sampling from combinatorial families can be difficult. However, complicated families can often be embedded within larger, simpler ones, for which easy sampling algorithms are known. We take advantage of such a relationship to describe a sampling algorithm for the smaller family, via a Markov chain started at a random sample of the larger family. The utility of the method is demonstrated via several examples, with particular emphasis on sampling labelled graphs with given degr...

Find SimilarView on arXiv

On uniform sampling simple directed graph realizations of degree sequences

December 21, 2009

86% Match
M. Drew Lamar
Discrete Mathematics

Choosing a uniformly sampled simple directed graph realization of a degree sequence has many applications, in particular in social networks where self-loops are commonly not allowed. It has been shown in the past that one can perform a Markov chain arc-switching algorithm to sample a simple directed graph uniformly by performing two types of switches: a 2-switch and a directed 3-cycle reorientation. This paper discusses under what circumstances a directed 3-cycle reorientatio...

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

Generating simple random graphs with prescribed degree distribution

September 23, 2015

86% Match
Tom Britton, Maria Deijfen, Anders Martin-Löf
Probability

Let $F$ be a probability distribution with support on the non-negative integers. Four methods for generating a simple undirected graph with (approximate) degree distribution $F$ are described and compared. Two methods are based on the so called configuration model with modifications ensuring a simple graph, one method is an extension of the classical Erd\H{o}s-R\'{e}nyi graph where the edge probabilities are random variables, and the last method starts with a directed random ...

Find SimilarView on arXiv

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

October 28, 2021

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