Tied Kronecker product graph models to capture variance in network populations

Sebastian Moreno, Sergey Kirshner, Jennifer Neville, S. V.N. Vishwanathan

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

20 Citas (Scopus)

Resumen

Much of the past work on mining and modeling networks has focused on understanding the observed properties of single example graphs. However, in many real-life applications it is important to characterize the structure of populations of graphs. In this work, we investigate the distributional properties of Kronecker product graph models (KPGMs) [1]. Specifically, we examine whether these models can represent the natural variability in graph properties observed across multiple networks and find surprisingly that they cannot. By considering KPGMs from a new viewpoint, we can show the reason for this lack of variance theoretically - which is primarily due to the generation of each edge independently from the others. Based on this understanding we propose a generalization of KPGMs that uses tied parameters to increase the variance of the model, while preserving the expectation. We then show experimentally, that our mixed-KPGM can adequately capture the natural variability across a population of networks.

Idioma originalInglés
Título de la publicación alojada2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Páginas1137-1144
Número de páginas8
DOI
EstadoPublicada - 2010
Publicado de forma externa
Evento48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 - Monticello, IL, Estados Unidos
Duración: 29 sept. 20101 oct. 2010

Serie de la publicación

Nombre2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010

Conferencia

Conferencia48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
País/TerritorioEstados Unidos
CiudadMonticello, IL
Período29/09/101/10/10

Citar esto