Tied kronecker product graph models to capture variance in network populations

Sebastian Moreno, Jennifer Neville, Sergey Kirshner

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Much of the past work on mining and modeling networks has focused on understanding the observed properties 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 analyze the distributional properties of probabilistic generative graph models (PGGMs) for network populations. PGGMs are statistical methods that model the network distribution and match common characteristics of real-world networks. Specifically, we show that most PGGMs cannot reflect the natural variability in graph properties observed across multiple networks because their edge generation process assumes independence among edges. Then, we propose the mixed Kronecker Product Graph Model (mKPGM), a scalable generalization of KPGMs that uses tied parameters to increase the variability of the sampled networks, while preserving the edge probabilities in expectation. We compare mKPGM to several other graph models. The results show that learned mKPGMs accurately represent the characteristics of real-world networks, while also effectively capturing the natural variability in network structure.

Original languageEnglish
Article number35
JournalACM Transactions on Knowledge Discovery from Data
Volume12
Issue number3
DOIs
StatePublished - 2018
Externally publishedYes

Keywords

  • Graph generation models
  • Kronecker product graph models
  • Social network analysis

Fingerprint

Dive into the research topics of 'Tied kronecker product graph models to capture variance in network populations'. Together they form a unique fingerprint.

Cite this