Scalable and exact sampling method for probabilistic generative graph models
Moreno
S
author
Pfeiffer
J
J
author
Neville
J
author
2018
English
Interest in modeling complex networks has fueled the development of multiple probabilistic generative graph models (PGGMs). PGGMs are statistical methods that model the network distribution and match common characteristics of real world networks. Recently, scalable sampling algorithms for well known PGGMs, made the analysis of large-scale, sparse networks feasible for the first time. However, it has been demonstrated that these scalable sampling algorithms do not sample from the original underlying distribution, and sometimes produce very unlikely graphs. To address this, we extend the algorithm proposed in Moreno et al.(in: IEEE 14th international conference on data mining, pp 440-449, 2014) for a single model and develop a general solution for a broad class of PGGMs. Our approach exploits the fact that PGGMs are typically parameterized by a small set of unique probability valuesthis enables fast generation via independent sampling of groups of edges with the same probability value. By sampling within groups, we remove bias due to conditional sampling and probability reallocation. We show that our grouped sampling methods are both provably correct and efficient. Our new algorithm reduces time complexity by avoiding the expensive rejection sampling step previously necessary, and we demonstrate its generality, by outlining implementations for six different PGGMs. We conduct theoretical analysis and empirical evaluation to demonstrate the strengths of our algorithms. We conclude by sampling a network with over a billion edges in 95s on a single processor.
Network analysis
Network models
Social networks
Graph generation
Scalable sampling
WOS:000444383000002
exported from refbase (http://ficpubs.uai.cl/show.php?record=913), last updated on Thu, 22 Nov 2018 13:31:51 +0000
text
http://ficpubs.uai.cl/files/769_Moreno_etal2018.pdf
10.1007/s10618-018-0566-x
Moreno_etal2018
Data Mining And Knowledge Discovery
Data Min. Knowl. Discov.
2018
Springer
continuing
periodical
academic journal
32
6
1561
1596
1384-5810