Revisiting the stop-and-stare algorithms for influence maximization

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....

Full description

Saved in:
Bibliographic Details
Main Authors: Huang, Keke, Wang, Sibo, Bevilacqua, Glenn, Xiao, Xiaokui, Lakshmanan, Laks V. S.
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2019
Subjects:
Online Access:https://hdl.handle.net/10356/105713
http://hdl.handle.net/10220/49548
http://dx.doi.org/10.14778/3099622.3099623
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-105713
record_format dspace
spelling sg-ntu-dr.10356-1057132019-12-06T21:56:23Z Revisiting the stop-and-stare algorithms for influence maximization Huang, Keke Wang, Sibo Bevilacqua, Glenn Xiao, Xiaokui Lakshmanan, Laks V. S. School of Computer Science and Engineering Social Network Engineering::Computer science and engineering SSA-Fix 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. MOE (Min. of Education, S’pore) Published version 2019-08-06T03:46:15Z 2019-12-06T21:56:23Z 2019-08-06T03:46:15Z 2019-12-06T21:56:23Z 2017 Journal Article 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 2150-8097 https://hdl.handle.net/10356/105713 http://hdl.handle.net/10220/49548 http://dx.doi.org/10.14778/3099622.3099623 en Proceedings of the VLDB Endowment © 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. 12 p. application/pdf
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Social Network
Engineering::Computer science and engineering
SSA-Fix
spellingShingle Social Network
Engineering::Computer science and engineering
SSA-Fix
Huang, Keke
Wang, Sibo
Bevilacqua, Glenn
Xiao, Xiaokui
Lakshmanan, Laks V. S.
Revisiting the stop-and-stare algorithms for influence maximization
description 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.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Huang, Keke
Wang, Sibo
Bevilacqua, Glenn
Xiao, Xiaokui
Lakshmanan, Laks V. S.
format Article
author Huang, Keke
Wang, Sibo
Bevilacqua, Glenn
Xiao, Xiaokui
Lakshmanan, Laks V. S.
author_sort Huang, Keke
title Revisiting the stop-and-stare algorithms for influence maximization
title_short Revisiting the stop-and-stare algorithms for influence maximization
title_full Revisiting the stop-and-stare algorithms for influence maximization
title_fullStr Revisiting the stop-and-stare algorithms for influence maximization
title_full_unstemmed Revisiting the stop-and-stare algorithms for influence maximization
title_sort revisiting the stop-and-stare algorithms for influence maximization
publishDate 2019
url https://hdl.handle.net/10356/105713
http://hdl.handle.net/10220/49548
http://dx.doi.org/10.14778/3099622.3099623
_version_ 1681038047104204800