research-article

Public Access

Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks

Authors:

Hung T. Nguyen,

Thang N. DinhAuthors Info & Claims

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Pages 695 - 710

https://doi.org/10.1145/2882903.2915207

Published: 14 June 2016 Publication History

Abstract

Influence Maximization (IM), that seeks a small set of key users who spread the influence widely into the network, is a core problem in multiple domains. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, IM in billion-scale networks such as Facebook, Twitter, and World Wide Web has not been satisfactorily solved. Even the state-of-the-art methods such as TIM+ and IMM may take days on those networks. In this paper, we propose SSA and D-SSA, two novel sampling frameworks for IM-based viral marketing problems. SSA and D-SSA are up to 1200 times faster than the SIGMOD'15 best method, IMM, while providing the same (1-1/e-ε) approximation guarantee. Underlying our frameworks is an innovative Stop-and-Stare strategy in which they stop at exponential check points to verify (stare) if there is adequate statistical evidence on the solution quality. Theoretically, we prove that SSA and D-SSA are the first approximation algorithms that use (asymptotically) minimum numbers of samples, meeting strict theoretical thresholds characterized for IM. The absolute superiority of SSA and D-SSA are confirmed through extensive experiments on real network data for IM and another topic-aware viral marketing problem, named TVM.

References

[1]

D. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network," in KDD'03, pp. 137--146, ACM New York, NY, USA, 2003.

Digital Library

[2]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, "Cost-effective outbreak detection in networks," in ACM KDD '07, (New York, NY, USA), pp. 420--429, ACM, 2007.

Digital Library

[3]

W. Chen, C. Wang, and Y. Wang, "Scalable influence maximization for prevalent viral marketing in large-scale social networks," in ACM KDD '10, (New York, NY, USA), pp. 1029--1038, ACM, 2010.

Digital Library

[4]

A. Goyal, W. Lu, and L. Lakshmanan, "Simpath: An efficient algorithm for influence maximization under the linear threshold model," in Data Mining (ICDM), 2011 IEEE 11th International Conference on, pp. 211--220, IEEE, 2011.

Digital Library

[5]

A. Goyal, W. Lu, and L. Lakshmanan, "Celf+: optimizing the greedy algorithm for influence maximization in social networks," in Proceedings of the 20th international conference companion on World wide web, pp. 47--48, ACM, 2011.

Digital Library

[6]

E. Cohen, D. Delling, T. Pajor, and R. F. Werneck, "Sketch-based influence maximization and computation: Scaling up with guarantees," in Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pp. 629--638, ACM, 2014.

Digital Library

[7]

N. Ohsaka, T. Akiba, Y. Yoshida, and K.-i. Kawarabayashi, "Fast and accurate influence maximization on large networks with pruned monte-carlo simulations," in Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.

Digital Library

[8]

Y. Tang, X. Xiao, and Y. Shi, "Influence maximization: Near-optimal time complexity meets practical efficiency," in Proceedings of SIGMOD international conference on Management of data, pp. 75--86, ACM, 2014.

Digital Library

[9]

D. T. Nguyen, H. Zhang, S. Das, M. T. Thai, and T. N. Dinh, "Least cost influence in multiplex social networks: Model representation and analysis," in Data Mining (ICDM), 2013 IEEE 13th International Conference on, pp. 567--576, IEEE, 2013.

[10]

T. N. Dinh, Y. Shen, D. T. Nguyen, and M. T. Thai, "On the approximability of positive influence dominating set in social networks," Journal of Combinatorial Optimization, vol. 27, no. 3, pp. 487--503, 2014.

Digital Library

[11]

Y. Shen, T. N. Dinh, H. Zhang, and M. T. Thai, "Interest-matching information propagation in multiple online social networks," in Proceedings of the 21st ACM International Conference on Information and Knowledge Management, CIKM '12, (New York, NY, USA), pp. 1824--1828, ACM, 2012.

Digital Library

[12]

H. T. Nguyen, M. T. Thai, and T. N. Dinh, "Cost-aware targeted viral marketing in billion-scale networks," in INFOCOM, 2016 Proceedings IEEE, pp. 55--59, IEEE, 2013.

[13]

W. Chen, Y. Wang, and S. Yang, "Efficient influence maximization in social networks," in KDD '09, (New York, NY, USA), pp. 199--208, ACM, 2009.

Digital Library

[14]

K. Jung, W. Heo, and W. Chen, "Irie: Scalable and robust influence maximization in social networks," in Data Mining (ICDM), 2012 IEEE 12th International Conference on, pp. 918--923, IEEE, 2012.

Digital Library

[15]

Y. Wang, G. Cong, G. Song, and K. Xie, "Community-based greedy algorithm for mining top-k influential nodes in mobile social networks," in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1039--1048, ACM, 2010.

Digital Library

[16]

Y. Tang, Y. Shi, and X. Xiao, "Influence maximization in near-linear time: A martingale approach," in Proceedings of SIGMOD International Conference on Management of Data, pp. 1539--1554, ACM, 2015.

Digital Library

[17]

C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, "Maximizing social influence in nearly optimal time," in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pp. 946--957, SIAM, 2014.

Digital Library

[18]

M. Minoux, "Accelerated greedy algorithms for maximizing submodular set functions," in Optimization Techniques (J. Stoer, ed.), vol. 7 of Lecture Notes in Control and Information Sciences, pp. 234--243, Springer, 1978.

[19]

N. Chen, "On the approximability of influence in social networks," SIAM Journal of Discrete Mathematics, vol. 23, no. 3, pp. 1400--1415, 2009.

Digital Library

[20]

A. Goyal, F. Bonchi, and L. Lakshmanan, "Learning influence probabilities in social networks," in Proceedings of the third ACM international conference on Web search and data mining, pp. 241--250, ACM, 2010.

Digital Library

[21]

K. Kutzkov, A. Bifet, F. Bonchi, and A. Gionis, "Strip: stream learning of influence probabilities," in Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 275--283, ACM, 2013.

Digital Library

[22]

T. Dinh, H. Zhang, D. Nguyen, and M. Thai, "Cost-effective viral marketing for time-critical campaigns in large-scale social networks," Networking, IEEE/ACM Transactions on, 2014.

Digital Library

[23]

H. Zhang, T. Dinh, and M. Thai, "Maximizing the spread of positive influence in online social networks," in Distributed Computing Systems (ICDCS), 2013 IEEE 33rd International Conference on, pp. 317--326, July 2013.

Digital Library

[24]

W. Chen, W. Lu, and N. Zhang, "Time-critical influence maximization in social networks with time-delayed diffusion process," in Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.

Digital Library

[25]

N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha, "Scalable influence estimation in continuous-time diffusion networks," in Advances in neural information processing systems, pp. 3147--3155, 2013.

[26]

H. Nguyen and R. Zheng, "On budgeted influence maximization in social networks," Selected Areas in Communications, IEEE Journal on, vol. 31, no. 6, pp. 1084--1094, 2013.

[27]

P. Dagum, R. Karp, M. Luby, and S. Ross, "An optimal algorithm for monte carlo estimation," SIAM J. Comput., vol. 29, pp. 1484--1496, Mar. 2000.

Digital Library

[28]

S. Khuller, A. Moss, and J. S. Naor, "The budgeted maximum coverage problem," Information Processing Letters, vol. 70, no. 1, pp. 39--45, 1999.

Digital Library

[29]

Y. Li, D. Zhang, and K.-L. Tan, "Real-time targeted influence maximization for online advertisements," Proceedings of the VLDB Endowment, vol. 8, no. 10, 2015.

Digital Library

[30]

S. Bhattacharya, M. Henzinger, D. Nanongkai, and C. Tsourakakis, "Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams," in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 173--182, ACM, 2015.

Digital Library

[31]

G. L. Nemhauser and L. A. Wolsey, "Maximizing submodular set functions: formulations and analysis of algorithms," North-Holland Mathematics Studies, vol. 59, pp. 279--301, 1981.

[32]

H. Kwak, C. Lee, H. Park, and S. Moon, "What is twitter, a social network or a news media?," in Proceedings of the 19th international conference on World wide web, pp. 591--600, ACM, 2010.

Digital Library

[33]

A. Goyal, W. Lu, and L. V. Lakshmanan, "Celf+: optimizing the greedy algorithm for influence maximization in social networks," in Proceedings of the 20th international conference companion on World wide web, pp. 47--48, ACM, 2011.

Digital Library

Cited By

Wang HPan QTang J(2024)HEDV-Greedy: An Advanced Algorithm for Influence Maximization in HypergraphsMathematics10.3390/math1207104112:7(1041)Online publication date: 30-Mar-2024
https://doi.org/10.3390/math12071041
Feng CChen XGuo QZhang FWang S(2024)Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage GuaranteeProceedings of the ACM on Management of Data10.1145/36771332:4(1-26)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677133
Feng YTan VCautis BBaeza-Yates RBonchi F(2024)Influence Maximization via Graph Neural BanditsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671983(771-781)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671983
Show More Cited By

Index Terms

Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks
1. Information systems
  1. Information systems applications
    1. Data mining
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Approximation algorithms

Recommendations

Effective Method for Promoting Viral Marketing in Microblog
SOCIALCOM '13: Proceedings of the 2013 International Conference on Social Computing

Based on word-of-mouth effect, viral marketing has developed into an important marketing strategy recently. Meanwhile, microblog has drawn global attention as a potential marketing group over the past decade. Thus how to promote viral marketing in ...
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 ...
A Bio-Inspired Defensive Rumor Confinement Strategy in Online Social Networks

Online social networks (OSNs) are used to connect people and propagate information around the globe. Along with information propagation, rumors also penetrate across the OSNs in a massive order. Controlling the rumor propagation is utmost important to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

June 2016

2300 pages

ISBN:9781450335317

DOI:10.1145/2882903

General Chairs:
Fatma Özcan
IBM Research, USA
,
Georgia Koutrika
HP Labs, USA
,
Program Chair:
Sam Madden
Massachusetts Institute of Technology, USA

Copyright © 2016 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 ACM 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 History

Published: 14 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SIGMOD/PODS'16

Sponsor:

SIGMOD

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

June 26 - July 1, 2016

California, San Francisco, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

270
Total Citations
View Citations
2,749
Total Downloads

Downloads (Last 12 months)368
Downloads (Last 6 weeks)28

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang HPan QTang J(2024)HEDV-Greedy: An Advanced Algorithm for Influence Maximization in HypergraphsMathematics10.3390/math1207104112:7(1041)Online publication date: 30-Mar-2024
https://doi.org/10.3390/math12071041
Feng CChen XGuo QZhang FWang S(2024)Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage GuaranteeProceedings of the ACM on Management of Data10.1145/36771332:4(1-26)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677133
Feng YTan VCautis BBaeza-Yates RBonchi F(2024)Influence Maximization via Graph Neural BanditsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671983(771-781)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671983
Tang JLi Y(2024)A hybrid dynamic memetic algorithm for the influence maximization problem in social networksInternational Journal of Modern Physics C10.1142/S0129183124501924Online 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
Tran CShin WSpitz A(2024)IM-META: Influence Maximization Using Node Metadata in Networks With Unknown TopologyIEEE Transactions on Network Science and Engineering10.1109/TNSE.2024.336290311:3(3148-3160)Online publication date: May-2024
https://doi.org/10.1109/TNSE.2024.3362903
Liu YWang XWang XWang Z(2024)Fast Outbreak Sense and Effective Source Inference via Minimum Observer SetIEEE/ACM Transactions on Networking10.1109/TNET.2024.338254632:4(3111-3125)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3382546
Yao XZhao YGao NDu HHuang H(2024)Causal Related Rumors Controlling in Social Networks of Multiple InformationIEEE/ACM Transactions on Networking10.1109/TNET.2023.333777432:3(2085-2098)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2023.3337774
Guo JNi QWu WDu D(2024)Composite Community-Aware Diversified Influence Maximization With Efficient ApproximationIEEE/ACM Transactions on Networking10.1109/TNET.2023.332187032:2(1584-1599)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3321870
Guo JNi QWu WDu D(2024)Multi-Task Diffusion Incentive Design for Mobile Crowdsourcing in Social NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2023.3310383(1-15)Online publication date: 2024
https://doi.org/10.1109/TMC.2023.3310383
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents