A Scalable Method for Exact Sampling from Kronecker Family Models

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

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

8 Citas (Scopus)


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.

Idioma originalInglés
Título de la publicación alojadaProceedings - 14th IEEE International Conference on Data Mining, ICDM 2014
EditoresRavi Kumar, Hannu Toivonen, Jian Pei, Joshua Zhexue Huang, Xindong Wu
EditorialInstitute of Electrical and Electronics Engineers Inc.
Número de páginas10
ISBN (versión digital)9781479943029
EstadoPublicada - 1 ene. 2014
Publicado de forma externa
Evento14th IEEE International Conference on Data Mining, ICDM 2014 - Shenzhen, China
Duración: 14 dic. 201417 dic. 2014

Serie de la publicación

NombreProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (versión impresa)1550-4786


Conferencia14th IEEE International Conference on Data Mining, ICDM 2014


Profundice en los temas de investigación de 'A Scalable Method for Exact Sampling from Kronecker Family Models'. En conjunto forman una huella única.

Citar esto