@inproceedings{69db9ca268f9495e8b503d46021e760a,
title = "Importance sketching of influence dynamics in billion-scale networks",
abstract = "The blooming availability of traces for social, biological, and communication networks opens up unprecedented opportunities in analyzing diffusion processes in networks. However, the sheer sizes of the nowadays networks raise serious challenges in computational efficiency and scalability. In this paper, we propose a new hyper-graph sketching framework for influence dynamics in networks. The core of our sketching framework, called SKIS, is an efficient importance sampling algorithm that returns only non-singular reverse cascades in the network. Comparing to previously developed sketches like RIS and SKIM, our sketch significantly enhances estimation quality while substantially reducing processing time and memory-footprint. Further, we present general strategies of using SKIS to enhance existing algorithms for influence estimation and influence maximization which are motivated by practical applications like viral marketing. Using SKIS, wedesign high-quality influence oracles for seed sets with average estimation error up to 10x times smaller than those using RIS and 6x times smaller than SKIMs. In addition, our influence maximization using SKIS substantially improves the quality of solutions for greedy algorithms. It achieves up to 10x times speed-up and 4x memory reduction for the fastest RIS-based DSSA algorithm, while maintaining the same theoretical guarantees.",
keywords = "Billion-scale Networks, Importance Sampling, Influence Dynamics",
author = "Nguyen, {Hung T.} and Nguyen, {Tri P.} and Nhathai Phan and Dinh, {Thang N.}",
note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 17th IEEE International Conference on Data Mining, ICDM 2017 ; Conference date: 18-11-2017 Through 21-11-2017",
year = "2017",
month = dec,
day = "15",
doi = "10.1109/ICDM.2017.43",
language = "English (US)",
series = "Proceedings - IEEE International Conference on Data Mining, ICDM",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "337--346",
editor = "George Karypis and Srinivas Alu and Vijay Raghavan and Xindong Wu and Lucio Miele",
booktitle = "Proceedings - 17th IEEE International Conference on Data Mining, ICDM 2017",
address = "United States",
}