ID: 1112.4677

Unbiased degree-preserving randomisation of directed binary networks

December 20, 2011

View on ArXiv

Similar papers 2

A stopping criterion for Markov chains when generating independent random graphs

October 30, 2012

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

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

February 15, 2010

85% 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
A. Annibale, A. C. C. Coolen
Quantitative Methods
Disordered Systems and Neura...

We use mathematical methods from the theory of tailored random graphs to study systematically the effects of sampling on topological features of large biological signalling networks. Our aim in doing so is to increase our quantitative understanding of the relation between true biological networks and the imperfect and often biased samples of these networks that are reported in public data repositories and used by biomedical scientists. We derive exact explicit formulae for de...

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

September 16, 2016

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

Random graph models for directed acyclic networks

July 24, 2009

85% Match
Brian Karrer, M. E. J. Newman
Physics and Society
Statistical Mechanics
Data Analysis, Statistics an...

We study random graph models for directed acyclic graphs, an important class of networks that includes citation networks, food webs, and feed-forward neural networks among others. We propose two specific models, roughly analogous to the fixed edge number and fixed edge probability variants of traditional undirected random graphs. We calculate a number of properties of these models, including particularly the probability of connection between a given pair of vertices, and comp...

Find SimilarView on arXiv

Random graphs with arbitrary degree distributions and their applications

July 13, 2000

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

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

March 7, 2018

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

Degree correlations in directed scale-free networks

September 17, 2014

84% Match
Oliver Williams, Genio Charo I. Del
Physics and Society
Statistical Mechanics

Scale-free networks, in which the distribution of the degrees obeys a power-law, are ubiquitous in the study of complex systems. One basic network property that relates to the structure of the links found is the degree assortativity, which is a measure of the correlation between the degrees of the nodes at the end of the links. Degree correlations are known to affect both the structure of a network and the dynamics of the processes supported thereon, including the resilience ...

Find SimilarView on arXiv

Principles of statistical mechanics of random networks

April 4, 2002

84% Match
S. N. Dorogovtsev, J. F. F. Mendes, A. N. Samukhin
Statistical Mechanics
Networking and Internet Arch...
Mathematical Physics
Adaptation and Self-Organizi...

We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting...

Find SimilarView on arXiv

On the uniform generation of random graphs with prescribed degree sequences

December 1, 2003

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