Computer Science – Discrete Mathematics
Scientific paper
2009-12-03
Computer Science
Discrete Mathematics
Scientific paper
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 in general to sample uniformly at random because the state graph of the Markov chain decomposes into different isomorphic components. We call degree sequences for which the state graph is strongly connected arc swap sequences. To handle arbitrary degree sequences, we develop two different solutions. The first uses an additional operation (a reorientation of induced directed 3-cycles) which makes the state graph strongly connected, the second selects randomly one of the isomorphic components and samples inside it. Our main contribution is a precise characterization of arc swap sequences, leading to an efficient recognition algorithm. Finally, we point out some interesting consequences for network analysis.
Berger Annabell
Müller-Hannemann Matthias
No associations
LandOfFree
Uniform sampling of undirected and directed graphs with a fixed degree sequence 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 Uniform sampling of undirected and directed graphs with a fixed degree sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniform sampling of undirected and directed graphs with a fixed degree sequence will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-517837