A Scalable Method for Exact Sampling from Kronecker Family Models

Sebastian Moreno, Joseph J. Pfeiffer, Jennifer Neville, Sergey Kirshner

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

The recent interest in modeling complex networks has fueled the development of generative graph models, such as Kronecker Product Graph Model (KPGM) and mixed KPGM (mKPGM). The Kronecker family of models are appealing because of their elegant fractal structure, as well as their ability to capture important network characteristics such as degree, diameter, and (in the case of mKPGM) clustering and population variance. In addition, scalable sampling algorithms for KPGMs made the analysis of large-scale, sparse networks feasible for the first time. In this work, we show that the scalable sampling methods, in contrast to prior belief, do not in fact sample from the underlying KPGM distribution and often result in sampling graphs that are very unlikely. To address this issue, we develop a new representation that exploits the structure of Kronecker models and facilitates the development of novel grouped sampling methods that are provably correct. In this paper, we outline efficient algorithms to sample from mKPGMs and KPGMs based on these ideas. Notably, our mKPGM algorithm is the first available scalable sampling method for this model and our KPGM algorithm is both faster and more accurate than previous scalable methods. We conduct both theoretical analysis and empirical evaluation to demonstrate the strengths of our algorithms and show that we can sample a network with 75 million edges in 87 seconds on a single processor.

Original languageEnglish
Title of host publicationProceedings - 14th IEEE International Conference on Data Mining, ICDM 2014
EditorsRavi Kumar, Hannu Toivonen, Jian Pei, Joshua Zhexue Huang, Xindong Wu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages440-449
Number of pages10
EditionJanuary
ISBN (Electronic)9781479943029
DOIs
StatePublished - 1 Jan 2014
Externally publishedYes
Event14th IEEE International Conference on Data Mining, ICDM 2014 - Shenzhen, China
Duration: 14 Dec 201417 Dec 2014

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
NumberJanuary
Volume2015-January
ISSN (Print)1550-4786

Conference

Conference14th IEEE International Conference on Data Mining, ICDM 2014
Country/TerritoryChina
CityShenzhen
Period14/12/1417/12/14

Fingerprint

Dive into the research topics of 'A Scalable Method for Exact Sampling from Kronecker Family Models'. Together they form a unique fingerprint.

Cite this