Paper Info
Title
A study of the edge-switching Markov-chain method for the generation of random graphs
Abstract
We study the problem of generating connected random graphs with no self-loops or multiple edges and that, in addition, have a given de- gree sequence. The generation method we focus on is the edge-switching Markov-chain method, whose functioning depends on a parameter w re- lated to the method's core operation of an edge switch. We analyze two existing heuristics for adjusting w during the generation of a graph and show that they result in a Markov chain whose stationary distribution is uniform, thus ensuring that generation occurs uniformly at random. We also introduce a novel w-adjusting heuristic which, even though it does not always lead to a Markov chain, is still guaranteed to converge to the uniform distribution under relatively mild conditions. We report on extensive computer experiments comparing the three heuristics' perfor- mance at generating random graphs whose node degrees are distributed as power laws.
Year
Venue
Keywords
2005
Clinical Orthopaedics and Related Research
markov chain.,edge switch,random-graph generation,power law,uniform distribution,functional dependency,markov chain,computer experiment,stationary distribution,random graph
Field
DocType
Volume
Discrete mathematics,Random regular graph,Random variate,Combinatorics,Random graph,Markov chain,Heuristics,Variable-order Markov model,Degree distribution,Multiple edges,Mathematics
Journal
abs/cs/051
Citations 
PageRank 
References 
7
0.77
12
Authors
2
Name
Order
Citations
PageRank
Alexandre O. Stauffer113011.34
Valmir C. Barbosa235056.76