||Much of the past work on mining and modeling networks has focused on understanding the observed prop- erties of single example graphs. However, in many real-life applications it is important to characterize the structure of populations of graphs. In this work, we investigate the distributional properties of Kronecker product graph models (KPGMs) [Leskovec et al. 2010]. Specifically, we examine whether these models can represent the natural variability in graph properties observed across multiple networks and find surpris- ingly that they cannot. 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 the mixed Kronecker Product Graph Model (mKPGM) a generalization of KPGMs that uses tied parameters to increase the variance of the model, while preserving the expectation. We evaluate the mKPGM model by comparing to several different graph models, through the multi-dimensional Kolgomorov Smirnov statistics, a new statistic that consider the relation among the characteristics of the networks. The results show mKPGMs are able to produce a closer match to real-world graphs, while still providing natural variation in the generated graphs.