ID: 1103.4875

Constructing and Sampling Graphs with a Prescribed Joint Degree Distribution

March 24, 2011

View on ArXiv

Similar papers 2

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

December 3, 2009

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

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

Fast generation of random connected graphs with prescribed degrees

February 22, 2005

89% 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 maximally disassortative graphs with given degree distribution

July 6, 2016

89% Match
der Hoorn Pim van, Liudmila Ostroumova Prokhorenkova, Egor Samosvat
Probability

In this paper we consider the optimization problem of generating graphs with a prescribed degree distribution, such that the correlation between the degrees of connected nodes, as measured by Spearman's rho, is minimal. We provide an algorithm for solving this problem and obtain a complete characterization of the joint degree distribution in these maximally disassortative graphs, in terms of the size-biased degree distribution. As a result we get a lower bound for Spearman's ...

Find SimilarView on arXiv

Random Networks with Tunable Degree Distribution and Clustering

May 17, 2004

89% Match
Erik Volz
Statistical Mechanics
Disordered Systems and Neura...

We present an algorithm for generating random networks with arbitrary degree distribution and Clustering (frequency of triadic closure). We use this algorithm to generate networks with exponential, power law, and poisson degree distributions with variable levels of clustering. Such networks may be used as models of social networks and as a testable null hypothesis about network structure. Finally, we explore the effects of clustering on the point of the phase transition where...

Find SimilarView on arXiv

Random graphs with arbitrary degree distributions and their applications

July 13, 2000

89% Match
M. E. J. Newman, S. H. Strogatz, D. J. Watts
Statistical Mechanics
Disordered Systems and Neura...

Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results...

Find SimilarView on arXiv

Generation of arbitrarily two-point correlated random networks

August 30, 2007

89% Match
Sebastian Weber, Markus Porto
Statistical Mechanics
Disordered Systems and Neura...

Random networks are intensively used as null models to investigate properties of complex networks. We describe an efficient and accurate algorithm to generate arbitrarily two-point correlated undirected random networks without self- or multiple-edges among vertices. With the goal to systematically investigate the influence of two-point correlations, we furthermore develop a formalism to construct a joint degree distribution $P(j,k)$ which allows to fix an arbitrary degree dis...

Find SimilarView on arXiv

Bipartite Graphs as Models of Complex Networks

July 4, 2003

89% Match
Jean-Loup Guillaume, Matthieu Latapy
Statistical Mechanics

It appeared recently that the classical random graph model used to represent real-world complex networks does not capture their main properties. Since then, various attempts have been made to provide accurate models. We study here a model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some real-world observations, and it is sufficiently simple to make i...

Find SimilarView on arXiv

Degree-based network models

November 28, 2012

89% Match
Sofia C. Olhede, Patrick J. Wolfe
Statistics Theory
Social and Information Netwo...
Combinatorics
Methodology
Statistics Theory

We derive the sampling properties of random networks based on weights whose pairwise products parameterize independent Bernoulli trials. This enables an understanding of many degree-based network models, in which the structure of realized networks is governed by properties of their degree sequences. We provide exact results and large-sample approximations for power-law networks and other more general forms. This enables us to quantify sampling variability both within and acro...

Find SimilarView on arXiv

Constructing and sampling directed graphs with given degree sequences

September 21, 2011

89% Match
H. Kim, Genio C. I. Del, ... , Toroczkai Z.
Physics and Society
Statistical Mechanics
Data Structures and Algorith...
Social and Information Netwo...

The interactions between the components of complex networks are often directed. Proper modeling of such systems frequently requires the construction of ensembles of digraphs with a given sequence of in- and out-degrees. As the number of simple labeled graphs with a given degree sequence is typically very large even for short sequences, sampling methods are needed for statistical studies. Currently, there are two main classes of methods that generate samples. One of the existi...

Find SimilarView on arXiv