Dissertation
Parallel Influence Maximization Algorithms and Their Applications
Washington State University
Doctor of Philosophy (PhD), Washington State University
01/2021
DOI:
https://doi.org/10.7273/000001851
Handle:
https://hdl.handle.net/2376/120461
Abstract
Influence Maximization is the problem of identifying a small set of influencers from a social network that, when initially activated, will result in the maximum number of activations over the network. The underlying hypothesis is that a small cohort of actors is sufficient to exert a large degree of influence on the network. Consequently, the problem has been of interest for many application domains including marketing, social media analysis, and epidemiology. Efficient and scalable algorithms for Influence Maximization need to addressthe challenges emerging from its combinatorial nature and its embedded stochasticity. Achieving scale of computation while preserving high quality approximations has been an important challenge for real world applications with the current methods. Surprisingly, parallel computing approaches have been left largely unexplored. Parallel algorithms for Influence Maximization need to address new challenges.The unique characteristics of its highly dynamic workload and the data volume required for good quality approximations, set Influence Maximization apart from the classical parallel graph analytics methods. Approaches and implementations presented in this dissertation constitute a systematic effort to address all the key parallelization challenges of Influence Maximization methods. This dissertation presents the design, development, and application of scalable Influence Maximization algorithms. We introduce the first parallel and scalable algorithm for distributed memory systems. Our method enables to compute high quality approximate solutions on million scale networks. We propose the first parallel and scalable algorithms targeting multi-GPU systems and the upcoming generation of exascale machines. We formulate the problem of controlling an epidemic through vaccination as the maximization of the individuals saved from the disease and we show the submodularity of the objective function.
Metrics
32 File views/ downloads
52 Record Views
Details
- Title
- Parallel Influence Maximization Algorithms and Their Applications
- Creators
- Marco Minutoli
- Contributors
- Ananth Kalyanaraman (Advisor)Mahantesh Halappanavar (Advisor)Eric Lofgren (Committee Member)Aravind Sukumaran Rajam (Committee Member)Janardhan Rao (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 130
- Identifiers
- 99900606549701842
- Language
- English
- Resource Type
- Dissertation