2013 LearningMixedKroneckerProductGr

• (Moreno et al., 2013) ⇒ Sebastian I. Moreno, Jennifer Neville, and Sergey Kirshner. (2013). “Learning Mixed Kronecker Product Graph Models with Simulated Method of Moments.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487675

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Learning+Mixed+Kronecker+Product+Graph+Models+with+Simulated+Method+of+Moments
• http://dl.acm.org/citation.cfm?id=2487575.2487675&preflayout=flat#citedby

Quotes

Author Keywords

• Kronecker models; link analysis; method of moments estimation; parameter learning; statistical graph models

Abstract

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 LearningMixedKroneckerProductGr	Jennifer Neville Sebastian I. Moreno Sergey Kirshner			Learning Mixed Kronecker Product Graph Models with Simulated Method of Moments				10.1145/2487575.2487675		2013