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

Accelerating influence maximization using heterogeneous algorithms

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Influence maximization (IM) is an interesting study in the domain of social and complex networks which has gained widespread importance in recent years due to the growth in viral marketing and targeted advertisements through the use of online social networks. There have been several enriching contributions which focus on efficient algorithms for IM; a fundamental question remains as to how can the IM computations be done efficiently with better performance that can aid evaluations in real time. In this work, we present a novel mechanism of IM computation, using two case studies HBUTA and HSSA, that utilizes all the available computing hardware present in a current-generation high-end computing system. We present techniques for efficiently partitioning work, computations of IM in a distributed manner, consolidation, and addressing challenges towards ensuring maximum coverage of the input graph. We see that with our initial implementations, we get a maximum of 29.05% and 35.67% improvement in performance due to our HBUTA and HSSA algorithms, respectively, when used on a graph consisting of 1.6 million vertices and 30 million edges.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

References

  1. Arora A, Galhotra S, Ranu S (2017) Debunking the myths of influence maximization: an in-depth benchmarking study. In: Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD ’17, pp 651–666

  2. Bader D, Madduri K (2006) Gtgraph: a synthetic graph generator suite. http://www.cse.psu.edu/~kxm85/software/GTgraph/

  3. Banerjee DS, Kothapalli K (2011) Hybrid algorithms for list ranking and graph connected components. In: 18th IEEE international conference on high performance computing, HiPC 2011, Bengaluru, India, pp 1–10

  4. Besta M, Podstawski M, Groner L, Solomonik E, Hoefler T (2017) To push or to pull: on reducing communication and synchronization in graph computations. In: Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing, HPDC ’17. ACM, New York, NY, USA, pp 93–104

  5. Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14

  6. Çatalyürek ÜV, Kaya K, Sariyüce AE, Saule E (2013) Shattering and compressing networks for betweenness centrality. In: Proceedings of the 13th SIAM International Conference on Data Mining, May 2–4, 2013. Austin, TX, USA, pp 686–694

  7. Chakrabarti D, Zhan Y, Faloutsos C (2004) R-MAT: a recursive model for graph mining. In: Proceedings of the 2004 SIAM International Conference on Data Mining, pp 442–446

  8. Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10

  9. Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09. ACM, New York, NY, USA, pp 199–208

  10. Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01. New York, NY, USA, pp 57–66

  11. Gharaibeh A, Costa LB, Santos-Neto E, Ripeanu M (2013) On graphs, GPUs, and blind dating: a workload to processor matchmaking quest. In: Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, IPDPS ’13

  12. Goyal A, Lu W, Lakshmanan LV (2011) CELF++: Optimizing the Greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th International Conference Companion on World Wide Web, WWW ’11. ACM, New York, NY, USA, pp 47–48

  13. Harish P, Narayanan PJ (2007) Accelerating large graph algorithms on the GPU using CUDA. In: Proceedings of the 14th International Conference on High Performance Computing, HiPC’07. Springer, Berlin, Heidelberg, pp 197–208

  14. Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03. ACM, New York, NY, USA, pp 137–146

  15. Leskovec J, Sosič R (2014) SNAP: a general purpose network analysis and graph mining library in C++. http://snap.stanford.edu/snap

  16. Liu X, Li M, Li S, Peng S, Liao X, Lu X (2014) Imgpu: Gpu-accelerated influence maximization in large-scale social networks. IEEE Trans Parallel Distrib Syst 25(1):136–145

    Article  Google Scholar 

  17. Liu X, Li S, Liao X, Wang L, Wu Q (2012) In-time estimation for influence maximization in large-scale social networks. In: Proceedings of the Fifth Workshop on Social Network Systems, SNS ’12. ACM, New York, NY, USA, pp 3:1–3:6

  18. Manolis P, Stavroulakis G, Karatarakis A (2011) A new era in scientific computing: domain decomposition methods in hybrid CPU–GPU architectures. Comput Methods Appl Mech Eng 200:1490–1508

    Article  MathSciNet  Google Scholar 

  19. McColl R, Green O, Bader DA (2013) A new parallel algorithm for connected components in dynamic graphs. In: 20th Annual International Conference on High Performance Computing, HiPC 2013, Bengaluru (Bangalore), Karnataka, India, December 18–21, 2013, pp 246–255

  20. McLaughlin A, Bader DA (2014) Scalable and high performance betweenness centrality on the GPU. In: International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014, New Orleans, LA, USA, November 16–21, 2014, pp 572–583

  21. Munguía L, Bader DA, Ayguadé E (2012) Task-based parallel breadth-first search in heterogeneous environments. In: 19th International Conference on High Performance Computing, HiPC 2012, Pune, India, December 18–22, 2012, pp 1–10

  22. Nguyen DT, Zhang H, Das S, Thai MT, Dinh TN (2013) Least cost influence in multiplex social networks: model representation and analysis. In: 2013 IEEE 13th ICDM, pp 567–576

  23. Nguyen HT, Thai MT, Dinh TN (2016) Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: Proceedings of the 2016 ACM SIGMOD, pp 695–710

  24. Sariyüce AE, Kaya K, Saule E, Çatalyürek ÜV (2013) Betweenness centrality on GPUs and heterogeneous architectures. In: Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, GPGPU-6, Houston, Texas, USA, March 16, 2013, pp 76–85

  25. Saule E, Çatalyürek ÜV (2012) An early evaluation of the scalability of graph algorithms on the Intel MIC architecture. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW). IEEE, pp 1629–1639

  26. Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data

  27. Vineet V, Harish P, Patidar S, Narayanan PJ (2009) Fast minimum spanning tree for large graphs on the GPU. In: Proceedings of the Conference on High Performance Graphics 2009, HPG ’09. ACM, New York, NY, USA, pp 167–171

  28. Vömel C, Tomov S, Dongarra J (2012) Divide and conquer on hybrid GPU-accelerated multicore systems. SIAM J Sci Comput 34:C70–C82

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work is partially supported by Science and Engineering Research Board (SERB) of Department of Science and Technology (DST) India through the Grant ECR/2016/002061 and NVIDIA Corporation through the NVIDIA GPU Hardware Grant programme.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Information Technology Guwahati, IT Park Street, NH-37, Bongora, Guwahati, Assam, 781015, India

    Mridul Haque & Dip Sankar Banerjee

Authors
  1. Mridul Haque
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dip Sankar Banerjee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dip Sankar Banerjee.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Haque, M., Banerjee, D.S. Accelerating influence maximization using heterogeneous algorithms. J Supercomput 76, 4747–4769 (2020). https://doi.org/10.1007/s11227-019-03061-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-019-03061-8

Keywords

Search

Navigation