Title: Capturing the Natural Variability of Real Networks with Kronecker Product Graph Models

Speaker: Jennifer Neville, Purdue University

Date/Time: Wednesday, August 11, 2010       

Location: NM: CSRI/90 (videoconferenced from CA: 915/S101)

Brief Abstract: 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 recent work, we have investigated the distributional properties of state-of-the art generative models for graphs.  Specifically, we examined whether these models could represent the natural variability in graph properties observed across multiple networks and find surprisingly that they could not. We investigated this issue in detail for Kronecker Product Graph Models (KPGMs) and have found that a number of relatively simple approaches to increase variance in KPGMs do not work. 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 show experimentally, that our mixed-KPGM can adequately capture the natural variability across a population of networks.

CSRI POC: David Gleich, (925) 294-6769