There has recently been a great deal of work focused on developing statistical models of graph structure---with the goal of modeling probability distributions over graphs from which new,  similar  graphs can be generated by sampling from the estimated distributions. Although current graph models can capture several important characteristics of social network graphs (e.g., degree, path lengths), many of them do not generate graphs with sufficient  variation  to reflect the natural variability in real world graph domains. One exception is the  mixed Kronecker Product Graph Model  (mKPGM), a generalization of the Kronecker Product Graph Model, which uses  parameter tying  to capture variance in the underlying distribution [10]. The enhanced representation of mKPGMs enables them to match both the mean graph statistics and their spread as observed in real network populations, but unfortunately to date, the only method to estimate mKPGMs involves an exhaustive search over the parameters.   In this work, we present the first learning algorithm for mKPGMs. The  O (| E |) algorithm searches over the continuous parameter space using constrained line search and is based on  simulated method of moments , where the objective function minimizes the distance between the observed moments in the training graph and the  empirically estimated  moments of the model. We evaluate the mKPGM learning algorithm by comparing it to several different graph models, including KPGMs. We use multi-dimensional KS distance to compare the generated graphs to the observed graphs and the results show mKPGMs are able to produce a closer match to real-world graphs (10-90% reduction in KS distance), while still providing natural variation in the generated graphs.
['Sebastian Moreno', 'Jennifer Neville', 'Sergey Kirshner']
Learning mixed kronecker product graph models with simulated method of moments