Iterative Learning of Graph Connectivity from Partially-Observed Cascade Samples
- Title
- Iterative Learning of Graph Connectivity from Partially-Observed Cascade Samples
- Authors
- WOO, JIIN; OK, JUNGSEUL; YI, YUNG
- Date Issued
- 2020-10-13
- Publisher
- ACM SIGMOBILE
- Abstract
- Graph learning is an inference problem of estimating connectivity of a graph from a collection of epidemic cascades, with many useful applications in the areas of online/offline social networks, p2p networks, computer security, and epidemiology. We consider a practical scenario when the information of cascade samples are partially observed in the independent cascade (IC) model. For the graph learning problem, we propose an efficient algorithm that solves a localized version of computationally-intractable maximum likelihood estimation through approximations in both temporal and spatial aspects. Our algorithm iterates the operations of recovering missing time logs and inferring graph connectivity, and thereby progressively improves the inference quality. We study the sample complexity, which is the number of required cascade samples to meet a given inference quality, and show that it is asymptotically close to a lower bound, thus near-order-optimal in terms of the number of nodes. We evaluate the performance of our algorithm using five real-world social networks, whose size ranges from 20 to 900, and demonstrate that our algorithm performs better than other competing algorithms in terms of accuracy while maintaining fast running time.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/104572
- ISSN
- 0000-0000
- Article Type
- Conference
- Citation
- ACM Mobihoc: International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, page. 141 - 150, 2020-10-13
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.