Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/105713
Title: | Revisiting the stop-and-stare algorithms for influence maximization | Authors: | Huang, Keke Wang, Sibo Bevilacqua, Glenn Xiao, Xiaokui Lakshmanan, Laks V. S. |
Keywords: | Social Network Engineering::Computer science and engineering SSA-Fix |
Issue Date: | 2017 | Source: | Huang, K., Wang, S., Bevilacqua, G., Xiao, X., & Lakshmanan, L. V. S. (2017). Revisiting the stop-and-stare algorithms for influence maximization. Proceedings of the VLDB Endowment, 10(9), 913-924. doi:10.14778/3099622.3099623 | Series/Report no.: | Proceedings of the VLDB Endowment | Abstract: | Influence maximization is a combinatorial optimization problem that finds important applications in viral marketing, feed recommendation, etc. Recent research has led to a number of scalable approximation algorithms for influence maximization, such as TIM+ and IMM, and more recently, SSA and D-SSA. The goal of this paper is to conduct a rigorous theoretical and experimental analysis of SSA and D-SSA and compare them against the preceding algorithms. In doing so, we uncover inaccuracies in previously reported technical results on the accuracy and efficiency of SSA and D-SSA, which we set right. We also attempt to reproduce the original experiments on SSA and D-SSA, based on which we provide interesting empirical insights. Our evaluation confirms some results reported from the original experiments, but it also reveals anomalies in some other results and sheds light on the behavior of SSA and D-SSA in some important settings not considered previously. We also report on the performance of SSA-Fix, our modification to SSA in order to restore the approximation guarantee that was claimed for but not enjoyed by SSA. Overall, our study suggests that there exist opportunities for further scaling up influence maximization with approximation guarantees. | URI: | https://hdl.handle.net/10356/105713 http://hdl.handle.net/10220/49548 |
ISSN: | 2150-8097 | DOI: | 10.14778/3099622.3099623 | Schools: | School of Computer Science and Engineering | Rights: | © 2017 VLDB Endowment. This work is licensed under the Creative Commons AttributionNonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SCSE Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Revisiting the stop-and-stare algorithms for influence maximization.pdf | 765.76 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
5
94
Updated on Mar 28, 2024
Web of ScienceTM
Citations
5
69
Updated on Oct 28, 2023
Page view(s)
276
Updated on Mar 27, 2024
Download(s) 50
116
Updated on Mar 27, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.