TY - JOUR
T1 - Tied kronecker product graph models to capture variance in network populations
AU - Moreno, Sebastian
AU - Neville, Jennifer
AU - Kirshner, Sergey
N1 - Funding Information:
Sergey Kirshner’s contributions were made while he was affiliated with Purdue University. Sebastian Moreno acknowledges the support of “CONICYT + PAI/Concurso nacional de apoyo al retorno de investi-gadores/as desde el extranjero, convocatoria 2014 + folio 82140043.” This research is also supported by NSF under Contract numbers IIS-1149789, IIS-1618690, IIS-1546488, and CCF-0939370. Authors’ addresses: S. Moreno, Avda. Padre Hurtado 750, A-212, Viña del Mar, Chile; email: sebastianmoreno@uai.cl; J. Neville, 305 N. University St., 2142D, West Lafayette, IN 47907-2107, USA; email: neville@cs.purdue.edu; S. Kirshner, 1 Hacker Way, Menlo Park, CA 94025, USA; email: kirshner@fb.com. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2018 ACM 1556-4681/2018/03-ART35 $15.00 https://doi.org/10.1145/3161885
Publisher Copyright:
© 2018 ACM.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Graph generation models
KW - Kronecker product graph models
KW - Social network analysis
UR - http://www.scopus.com/inward/record.url?scp=85047016729&partnerID=8YFLogxK
U2 - 10.1145/3161885
DO - 10.1145/3161885
M3 - Article
AN - SCOPUS:85047016729
SN - 1556-4681
VL - 12
JO - ACM Transactions on Knowledge Discovery from Data
JF - ACM Transactions on Knowledge Discovery from Data
IS - 3
M1 - 35
ER -