ID: 1202.3473

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

February 15, 2012

View on ArXiv

Similar papers 2

A Markov Chain-Based Numerical Method for Calculating Network Degree Distributions

September 30, 2004

87% Match
Dinghua Shi, Qinghua Chen, Liming Liu
Mathematical Physics

This paper establishes a relation between scale-free networks and Markov chains, and proposes a computation framework for degree distributions of scale-free networks. We first find that, under the BA model, the degree evolution of individual nodes in a scale-free network follows some non-homogeneous Markov chains. Exploring the special structure of these Markov chains, we are able to develop an efficient algorithm to compute the degree distribution numerically. The complexity...

Find SimilarView on arXiv

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

March 5, 2012

87% Match
E. S. Roberts, A. Annibale, A. C. C. Coolen
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 (r...

Find SimilarView on arXiv

Sampling random graphs with specified degree sequences

May 25, 2021

87% Match
Upasana Dutta, Bailey K. Fosdick, Aaron Clauset
Social and Information Netwo...
Data Analysis, Statistics an...
Methodology

The configuration model is a standard tool for uniformly generating random graphs with a specified degree sequence, and is often used as a null model to evaluate how much of an observed network's structure can be explained by its degree structure alone. A Markov chain Monte Carlo (MCMC) algorithm, based on a degree-preserving double-edge swap, provides an asymptotic solution to sample from the configuration model. However, accurately and efficiently detecting this Markov chai...

Find SimilarView on arXiv

Tracking the Empirical Distribution of a Markov-modulated Duplication-Deletion Random Graph

February 28, 2013

86% Match
Maziyar Hamdi, Vikram Krishnamurthy, George Yin
Information Theory
Information Theory

This paper considers a Markov-modulated duplication-deletion random graph where at each time instant, one node can either join or leave the network; the probabilities of joining or leaving evolve according to the realization of a finite state Markov chain. The paper comprises of 2 results. First, motivated by social network applications, we analyze the asymptotic behavior of the degree distribution of the Markov-modulated random graph. Using the asymptotic degree distribution...

Find SimilarView on arXiv

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

March 7, 2018

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

Network interpolation

May 3, 2019

86% Match
Thomas Reeves, Anil Damle, Austin R. Benson
Social and Information Netwo...
Physics and Society

Given a set of snapshots from a temporal network we develop, analyze, and experimentally validate a so-called network interpolation scheme. Our method allows us to build a plausible, albeit random, sequence of graphs that transition between any two given graphs. Importantly, our model is well characterized by a Markov chain, and we leverage this representation to analytically estimate the hitting time (to a predefined distance to the target graph) and long term behavior of ou...

Find SimilarView on arXiv

Efficient Generation \epsilon-close to G(n,p) and Generalizations

April 26, 2012

86% Match
Antonio Blanca, Milena Mihail
Data Structures and Algorith...

We give an efficient algorithm to generate a graph from a distribution $\epsilon$-close to $G(n,p)$, in the sense of total variation distance. In particular, if $p$ is represented with $O(\log n)$-bit accuracy, then, with high probability, the running time is linear in the expected number of edges of the output graph (up to poly-logarithmic factors). All our running times include the complexity of the arithmetic involved in the corresponding algorithms. Previous standard meth...

Find SimilarView on arXiv

Stochastic Process-based Method for Degree-Degree Correlation of Evolving Networks

June 12, 2024

86% Match
Yue Xiao, Xiaojun Zhang
Computation
Methodology

Existing studies on the degree correlation of evolving networks typically rely on differential equations and statistical analysis, resulting in only approximate solutions due to inherent randomness. To address this limitation, we propose an improved Markov chain method for modeling degree correlation in evolving networks. By redesigning the network evolution rules to reflect actual network dynamics more accurately, we achieve a topological structure that closely matches real-...

Find SimilarView on arXiv

Generating Connected Random Graphs

June 29, 2018

86% Match
Caitlin Gray, Lewis Mitchell, Matthew Roughan
Social and Information Netwo...
Data Structures and Algorith...
Computation

Sampling random graphs is essential in many applications, and often algorithms use Markov chain Monte Carlo methods to sample uniformly from the space of graphs. However, often there is a need to sample graphs with some property that we are unable, or it is too inefficient, to sample using standard approaches. In this paper, we are interested in sampling graphs from a conditional ensemble of the underlying graph model. We present an algorithm to generate samples from an ensem...

Find SimilarView on arXiv

Random Walk Models of Network Formation and Sequential Monte Carlo Methods for Graphs

December 19, 2016

86% Match
Benjamin Bloem-Reddy, Peter Orbanz
Methodology
Machine Learning

We introduce a class of generative network models that insert edges by connecting the starting and terminal vertices of a random walk on the network graph. Within the taxonomy of statistical network models, this class is distinguished by permitting the location of a new edge to explicitly depend on the structure of the graph, but being nonetheless statistically and computationally tractable. In the limit of infinite walk length, the model converges to an extension of the pref...

Find SimilarView on arXiv