research-article

Open access

Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study

Authors:

Sainyam Galhotra,

Sayan RanuAuthors Info & Claims

SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data

Pages 651 - 666

https://doi.org/10.1145/3035918.3035924

Published: 09 May 2017 Publication History

Abstract

Influence maximization (IM) on social networks is one of the most active areas of research in computer science. While various IM techniques proposed over the last decade have definitely enriched the field, unfortunately, experimental reports on existing techniques fall short in validity and integrity since many comparisons are not based on a common platform or merely discussed in theory. In this paper, we perform an in-depth benchmarking study of IM techniques on social networks. Specifically, we design a benchmarking platform, which enables us to evaluate and compare the existing techniques systematically and thoroughly under identical experimental conditions. Our benchmarking results analyze and diagnose the inherent deficiencies of the existing approaches and surface the open challenges in IM even after a decade of research. More fundamentally, we unearth and debunk a series of myths and establish that there is no single state-of-the-art technique in IM. At best, a technique is the state of the art in only one aspect.

References

[1]

arXiv. http://www.arxiv.org.

[2]

SNAP Datasets. https://snap.stanford.edu/data/.

[3]

C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, pages 946--957, 2014.

Digital Library

[4]

W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD, pages 1029--1038, 2010.

Digital Library

[5]

W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD, pages 199--208, 2009.

Digital Library

[6]

W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, pages 88--97, 2010.

Digital Library

[7]

S. Cheng, H. Shen, J. Huang, W. Chen, and X. Cheng. IMRank: influence maximization via finding self-consistent ranking. In SIGIR, pages 475--484, 2014.

Digital Library

[8]

S. Cheng, H. Shen, J. Huang, G. Zhang, and X. Cheng. Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In CIKM, pages 509--518, 2013.

Digital Library

[9]

E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. Sketch-based influence maximization and computation: Scaling up with guarantees. In CIKM, pages 629--638, 2014.

Digital Library

[10]

S. Galhotra, A. Arora, and S. Roy. Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. In SIGMOD, 2016.

Digital Library

[11]

S. Galhotra, A. Arora, S. Virinchi, and S. Roy. ASIM: A scalable algorithm for influence maximization under the independent cascade model. In WWW (Companion Volume), 2015.

Digital Library

[12]

A. Goyal, F. Bonchi, and L. V. Lakshmanan. Learning influence probabilities in social networks. In WSDM, pages 241--250, 2010.

Digital Library

[13]

A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. A data-based approach to social influence maximization. PVLDB, 5:73--84, 2011.

Digital Library

[14]

A. Goyal, W. Lu, and L. V. Lakshmanan. CELF : Optimizing the greedy algorithm for influence maximization in social networks. In WWW (Companion Volume), pages 47--48, 2011.

Digital Library

[15]

A. Goyal, W. Lu, and L. V. Lakshmanan. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In ICDM, pages 211--220, 2011.

Digital Library

[16]

K. Jung, W. Heo, and W. Chen. IRIE: Scalable and robust influence maximization in social networks. In ICDM, pages 918--923, 2012.

Digital Library

[17]

D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003.

Digital Library

[18]

J. Kim, S.-K. Kim, and H. Yu. Scalable and parallelizable processing of influence maximization for large-scale social networks? In ICDE, pages 266--277, 2013.

Digital Library

[19]

K. Kutzkov, A. Bifet, F. Bonchi, and A. Gionis. STRIP: Stream learning of influence probabilities. In KDD, pages 275--283, 2013.

Digital Library

[20]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420--429, 2007.

Digital Library

[21]

Q. Liu, B. Xiang, E. Chen, H. Xiong, F. Tang, and J. X. Yu. Influence maximization over large-scale social networks: A bounded linear approach. In CIKM, pages 171--180, 2014.

Digital Library

[22]

G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265--294, 1978.

Digital Library

[23]

H. T. Nguyen, M. T. Thai, and T. N. Dinh. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In SIGMOD, pages 695--710, 2016.

Digital Library

[24]

N. Ohsaka, T. Akiba, Y. Yoshida, and K. Kawarabayashi. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In AAAI, pages 138--144, 2014.

Digital Library

[25]

L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: bringing order to the web. 1999.

[26]

Y. Tang, Y. Shi, and X. Xiao. Influence maximization in near-linear time: A martingale approach. In SIGMOD, pages 1539--1554, 2015.

Digital Library

[27]

Y. Tang, X. Xiao, and Y. Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In SIGMOD, pages 75--86, 2014.

Digital Library

[28]

V. V. Vazirani. Approximation Algorithms. 2001.

Digital Library

[29]

H. Zhang, T. N. Dinh, and M. T. Thai. Maximizing the spread of positive influence in online social networks. In ICDCS, pages 317--326, 2013.

Digital Library

Cited By

Furutani SAoshima TShibahara TAkiyama MAida M(2025)Suppressing the Endogenous Negative Influence Through Node Intervention in Social NetworksIEEE Access10.1109/ACCESS.2024.352303613(9290-9302)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2024.3523036
Singh SSrivastava DVerma MMuhuri S(2025)Information diffusion analysis: process, model, deployment, and applicationThe Knowledge Engineering Review10.1017/S026988892400010939Online publication date: 22-Jan-2025
https://doi.org/10.1017/S0269888924000109
Li PXie QChen WYang QGuo S(2025)Using upper and lower bounds to estimate indirect influence probability in social networks under independent cascade modelPhysica A: Statistical Mechanics and its Applications10.1016/j.physa.2025.130430662(130430)Online publication date: Mar-2025
https://doi.org/10.1016/j.physa.2025.130430
Show More Cited By

Index Terms

Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study
1. Information systems
  1. Information systems applications
    1. Data mining
  2. World Wide Web
    1. Web applications
      1. Social networks

Recommendations

Myths and realities: the performance impact of garbage collection

This paper explores and quantifies garbage collection behavior for three whole heap collectors and generational counterparts: copying semi-space, mark-sweep, and reference counting, the canonical algorithms from which essentially all other collection ...
Myths and realities: the performance impact of garbage collection
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

This paper explores and quantifies garbage collection behavior for three whole heap collectors and generational counterparts: copying semi-space, mark-sweep, and reference counting, the canonical algorithms from which essentially all other collection ...
Influence of program inputs on the selection of garbage collectors
VEE '09: Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments

Many studies have shown that the best performer among a set of garbage collectors tends to be different for different applications. Researchers have proposed application-specific selection of garbage collectors. In this work, we concentrate on a second ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data

May 2017

1810 pages

ISBN:9781450341974

DOI:10.1145/3035918

General Chairs:
Rada Chirkova
North Carolina State University, USA
,
Jun Yang
Duke University, USA
,
Program Chair:
Dan Suciu
University of Washington, USA

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication Notes

Badge change: Article originally badged under Version 1.0 guidelines https://www.acm.org/publications/policies/artifact-review-badging

Publication History

Published: 09 May 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tag

in-depth benchmarking study

Qualifiers

Research-article

Conference

SIGMOD/PODS'17

Sponsor:

SIGMOD

SIGMOD/PODS'17: International Conference on Management of Data

May 14 - 19, 2017

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

98
Total Citations
View Citations
1,636
Total Downloads

Downloads (Last 12 months)231
Downloads (Last 6 weeks)27

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Furutani SAoshima TShibahara TAkiyama MAida M(2025)Suppressing the Endogenous Negative Influence Through Node Intervention in Social NetworksIEEE Access10.1109/ACCESS.2024.352303613(9290-9302)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2024.3523036
Singh SSrivastava DVerma MMuhuri S(2025)Information diffusion analysis: process, model, deployment, and applicationThe Knowledge Engineering Review10.1017/S026988892400010939Online publication date: 22-Jan-2025
https://doi.org/10.1017/S0269888924000109
Li PXie QChen WYang QGuo S(2025)Using upper and lower bounds to estimate indirect influence probability in social networks under independent cascade modelPhysica A: Statistical Mechanics and its Applications10.1016/j.physa.2025.130430662(130430)Online publication date: Mar-2025
https://doi.org/10.1016/j.physa.2025.130430
Barik RCappa WFerdous SMinutoli MHalappanavar MKalyanaraman A(2025)GreediRIS: Scalable Influence Maximization using Distributed Streaming Maximum CoverJournal of Parallel and Distributed Computing10.1016/j.jpdc.2025.105037(105037)Online publication date: Jan-2025
https://doi.org/10.1016/j.jpdc.2025.105037
Agra ASamuco J(2024)A New Algorithm Framework for the Influence Maximization Problem Using Graph ClusteringInformation10.3390/info1502011215:2(112)Online publication date: 14-Feb-2024
https://doi.org/10.3390/info15020112
Liang ZYang YKe XXiao XGao Y(2024)A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over GraphsProceedings of the VLDB Endowment10.14778/3681954.368202917:11(3666-3679)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682029
Theocharidis KKarras PTerrovitis MSkiadopoulos SLauw H(2024)Adaptive Content-Aware Influence Maximization via Online Learning to RankACM Transactions on Knowledge Discovery from Data10.1145/365198718:6(1-35)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3651987
HUSSAIN OZAIDI F(2024)IMine: A CUSTOMIZABLE FRAMEWORK FOR INFLUENCE MINING IN COMPLEX NETWORKSAdvances in Complex Systems10.1142/S021952592450004827:01n02Online publication date: 27-Jun-2024
https://doi.org/10.1142/S0219525924500048
Tang JLi Y(2024)A hybrid dynamic memetic algorithm for the influence maximization problem in social networksInternational Journal of Modern Physics C10.1142/S012918312450192436:03Online publication date: 17-Aug-2024
https://doi.org/10.1142/S0129183124501924
Biswas TAbbasi AChakrabortty R(2024)Generalized hop‐based approaches for identifying influential nodes in social networksExpert Systems10.1111/exsy.13649Online publication date: 4-Jun-2024
https://doi.org/10.1111/exsy.13649
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten