## Abstract

There has recently been a great deal of work focused on de- veloping 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 reect 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 un- fortunately 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(jEj) algorithm searches over the contin- uous 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.

Original language | English |
---|---|

Title of host publication | KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining |

Editors | Rajesh Parekh, Jingrui He, Dhillon S. Inderjit, Paul Bradley, Yehuda Koren, Rayid Ghani, Ted E. Senator, Robert L. Grossman, Ramasamy Uthurusamy |

Publisher | Association for Computing Machinery |

Pages | 1052-1060 |

Number of pages | 9 |

ISBN (Electronic) | 9781450321747 |

DOIs | |

State | Published - 11 Aug 2013 |

Externally published | Yes |

Event | 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 - Chicago, United States Duration: 11 Aug 2013 → 14 Aug 2013 |

### Publication series

Name | Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining |
---|---|

Volume | Part F128815 |

### Conference

Conference | 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 |
---|---|

Country/Territory | United States |

City | Chicago |

Period | 11/08/13 → 14/08/13 |

## Keywords

- Kronecker models
- Link analysis
- Method of moments estimation
- Statistical graph models