Computer Science – Discrete Mathematics
Scientific paper
2005-12-29
Computer Science
Discrete Mathematics
Minor typos corrected
Scientific paper
We study the problem of generating connected random graphs with no self-loops or multiple edges and that, in addition, have a given degree sequence. The generation method we focus on is the edge-switching Markov-chain method, whose functioning depends on a parameter w related 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' performance at generating random graphs whose node degrees are distributed as power laws.
Barbosa Valmir C.
Stauffer Alexandre O.
No associations
LandOfFree
A study of the edge-switching Markov-chain method for the generation of random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A study of the edge-switching Markov-chain method for the generation of random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A study of the edge-switching Markov-chain method for the generation of random graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-701024