Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs

Details Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs

2011-10-24

arxiv.org/abs/1110.5383v2

Statistics

Machine Learning

Scientific paper

We describe the first sub-quadratic sampling algorithm for the Multiplicative Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close connection between MAGM and the Kronecker Product Graph Model (KPGM) of Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices to sample small number of KPGM graphs and \emph{quilt} them together. Under a restricted set of technical conditions our algorithm runs in $O((\log_2(n))^3 |E|)$ time, where $n$ is the number of nodes and $|E|$ is the number of edges in the sampled graph. We demonstrate the scalability of our algorithm via extensive empirical evaluation; we can sample a MAGM graph with 8 million nodes and 20 billion edges in under 6 hours.

Affiliated with

Also associated with

No associations

Rating

Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute 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 Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93881