Degree Distribution Identifiability of Stochastic Kronecker Graphs

Abstract: Network generation for realistic, real-world processes is an important problem in the biological, social, and physical sciences. Large-scale analysis of the distributions of the networks graphs observed in naturally-occurring phenomena has revealed that the degrees of such graphs follow a power-law or lognormal distribution. Many network or graph generation algorithms rely on the Kronecker multiplication primitive. Seshadhri, Pinar, and Kolda (J. ACM, 2013) proved that Stochastic Kronecker Graph (SKG) models cannot generate graph with degree distribution that follows a power-law or lognormal distribution. As a result, variants of the SKG model have been proposed to generate graphs which approximately follow degree distributions, without any significant oscillations. However, all existing solutions either require significant additional parameterization or have no provable guarantees on the degree distribution.
In this work, we present statistical and computational identifiability notions which imply separation of SKG models. We prove that SKG models in different identifiability classes can be separated by the existence of isolated vertices and connected components. In addition, we present and analyze an efficient algorithm that can get rid of oscillations in the degree distribution by mixing Kronecker seeds of relative prime dimensions.
Based on joint work with Dimitris Kalimeris.

Bio: Daniel G. Alabi is a Junior Fellow of the Simons Foundation Society of Fellows and postdoctoral researcher hosted by Prof. Daniel Hsu at Columbia University. He earned his Ph.D. in computer science from Harvard University, where he was advised by Prof. Salil Vadhan. Also, he is the president and co-founder of NaijaCoder, Inc. NaijaCoder aims to proliferate early computer science education and research in Nigeria, and Africa in general. His research interests lie primarily in the design and analysis of algorithms with a focus on privacy-preserving applications. Some of the awards he earned during his Ph.D. include: a Ph.D. Fellowship from Meta AI, a Courtlandt Memorial Fellowship from Harvard GSAS, and a Harvard Certificate of Distinction in Teaching.