toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) Moreno, S.; Pfeiffer, J.J.; Neville, J. pdf  doi
  Title Scalable and exact sampling method for probabilistic generative graph models Type Journal Article
  Year 2018 Publication Data Mining And Knowledge Discovery Abbreviated Journal Data Min. Knowl. Discov.  
  Volume 32 Issue 6 Pages 1561-1596  
  Keywords Network analysis; Network models; Social networks; Graph generation; Scalable sampling  
  Abstract 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.  
  Address [Moreno, Sebastian] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email:;  
  Corporate Author Thesis  
  Publisher Springer Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1384-5810 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000444383000002 Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 913  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: