Computer Science – Social and Information Networks
Scientific paper
2012-02-15
Computer Science
Social and Information Networks
12 pages, 4 figures, 1 table. Submitted to 9th Workshop on Algorithms and Models for the Web Graph, Dalhousie University in Ha
Scientific paper
Markov chains are a convenient means of generating realizations of networks, since they require little more than a procedure for rewiring edges. If a rewiring procedure exists for generating new graphs with specified statistical properties, then a Markov chain sampler can generate an ensemble of graphs with prescribed characteristics. However, successive graphs in a Markov chain cannot be used when one desires independent draws from the distribution of graphs; the realizations are correlated. Consequently, one runs a Markov chain for N iterations before accepting the realization as an independent sample. In this work, we devise two methods for calculating N. They are both based on the binary "time-series" denoting the occurrence/non-occurrence of edge (u, v) between vertices u and v in the Markov chain of graphs generated by the sampler. They differ in their underlying assumptions. We test them on the generation of graphs with a prescribed joint degree distribution. We find the N proportional |E|, where |E| is the number of edges in the graph. The two methods are compared by sampling on real, sparse graphs with 10^3 - 10^4 vertices.
Pinar Ali
Ray Jaideep
Seshadhri C.
No associations
LandOfFree
Are we there yet? When to stop a Markov chain while generating 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 Are we there yet? When to stop a Markov chain while generating random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Are we there yet? When to stop a Markov chain while generating random graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-124815