[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Scalable influence maximization for independent cascade model in large-scale social networks

  • Published:
Data Mining and Knowledge Discovery Aims and scope Submit manuscript

Abstract

Influence maximization, defined by Kempe et al. (SIGKDD 2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (SIGKDD 2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this article, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread—it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100–260% increase in influence spread.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Aiello W, Chung FRK, Lu L (2000) A random graph model for massive graphs. In: STOC ’00

  • Bakshy E, Karrer B, Adamic LA (2009) Social influence and the diffusion of user-created content. In: EC ’09: Proc. 10th ACM Conf. Electronic Commerce

  • Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw 30(1-7): 107–117

    Google Scholar 

  • Cha M, Mislove A, Gummadi KP (2009) A measurement-driven analysis of information propagation in the flickr social network. In: WWW ’09

  • Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: KDD ’09

  • Chen W, Wang C, Wang Y (2010a) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: KDD ’10

  • Chen W, Yuan Y, Zhang L (2010b) Scalable influence maximization in social networks under the linear threshold model. In: ICDM ’10

  • Chen W, Collins A, Cummings R, Ke T, Liu Z, Rincon D, Sun X, Wang Y, Wei W, Yuan Y (2011) Influence maximization in social networks when negative opinions may emerge and propagate. In: SDM ’11

  • Cui P, Wang F, Liu S, Ou M, Yang S, Sun L (2011) Who should share what?: item-level social influence prediction for users and posts ranking. In: SIGIR ’11

  • Domingos P, Richardson M (2001) Mining the network value of customers. In: KDD ’01

  • Feige U (1998) A threshold of ln n for approximating set cover. J ACM 45(4): 634–652

    Article  MathSciNet  MATH  Google Scholar 

  • Freeman L (1979) Centrality in social networks: conceptual clarification. Soc Netw 1: 215–239

    Article  Google Scholar 

  • Goyal A, Bonchi F, Lakshmanan LV (2010) Learning influence probabilities in social networks. In: WSDM ’10

  • Gruhl D, Guha RV, Liben-Nowell D, Tomkins A (2004) Information diffusion through blogspace. In: WWW ’04

  • Kempe D, Kleinberg JM, Tardos É (2003) Maximizing the spread of influence through a social network. In: KDD ’03

  • Kimura M, Saito K (2006) Tractable models for information diffusion in social networks. In: PKDD ’06

  • Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance NS (2007) Cost-effective outbreak detection in networks. In: KDD ’07

  • Misner IR (1999) The world’s best known marketing secret: Building your business with word-of-mouth marketing, 2nd edn. Bard Press, Austin

    Google Scholar 

  • Nail J (2004) The consumer advertising backlash. Forrester Research and Intelliseek Market Research Report

  • Nemhauser G, Wolsey L, Fisher M (1978) An analysis of the approximations for maximizing submodular set functions. Math Program 14: 265–294

    Article  MathSciNet  MATH  Google Scholar 

  • Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: KDD ’02

  • Rodriguez MG, Leskovec J, Krause A (2010) Inferring networks of diffusion and influence. In: KDD ’10

  • Streeter M, Golovin D (2007) An online algorithm for maximizing submodular functions. Technical Report CMU-CS-07-171, Carnegie Mellon University, Pittsburgh

  • Tang J, Sun J, Wang C, Yang Z (2009) Social influence analysis in large-scale networks. In: KDD ’09

  • Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8(3): 410–421

    Article  MathSciNet  MATH  Google Scholar 

  • Vazirani VV (2004) Approximation algorithms. Springer, Berlin

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Illinois at Urbana-Champaign, Urbana, IL, USA

    Chi Wang

  2. Microsoft Research Asia, Beijing, China

    Wei Chen & Yajun Wang

Authors
  1. Chi Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yajun Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chi Wang.

Additional information

Responsible editor: Fei Wang, Hanghang Tong, Philip Yu, Charu Aggarwal.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, C., Chen, W. & Wang, Y. Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Disc 25, 545–576 (2012). https://doi.org/10.1007/s10618-012-0262-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10618-012-0262-1

Keywords