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

Details Efficient Generation ε-close to G(n,p) and Generalizations Efficient Generation ε-close to G(n,p) and Generalizations

2012-04-26

arxiv.org/abs/1204.5834v1

Computer Science

Data Structures and Algorithms

Scientific paper

We give an efficient algorithm to simulate G(n,p) sampling. 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 (and further multiplicative poly-logarithmic factors, as usual). The main technical ingredient is to determine the number of edges of the output graph by simulating a Markov chain, thus bypassing the difficulty of sampling from a binomial distribution. We note that previously known efficient algorithms for sampling G(n,p) assume constant cost for arbitrary accuracy real number representation and arithmetic (in practice, this appears to result in either efficient running time and biased sampling, or unbiased sampling and inefficient running time). We obtain similar results for random graphs with given arbitrary degree distributions. Our algorithm is a reduction to repeated sampling from G(n,p), and further normalizations. The main idea for the reduction is to assign suitable weights to vertices, and partition vertices to O(\log n) classes, where all vertices in the same class have weights within constant multiplicative factors. We also obtain similar results for Inhomogeneous Random Graphs, when the kernel function is the inner product. These graphs are important high dimensional generalizations of G(n,p). Our algorithm for this case uses all the above mentioned techniques, and fundamentals of high dimensional geometry. Efficient generation in the above mentioned random graph models is essential in modeling very large scale complex networks.

Affiliated with

Also associated with

No associations

Rating

Efficient Generation ε-close to G(n,p) and Generalizations 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 Efficient Generation ε-close to G(n,p) and Generalizations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Generation ε-close to G(n,p) and Generalizations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-313669