IEEE Transactions on Parallel and Distributed Systems · 2013 · 65 citations · 19 references
ComputingComputer ScienceHigh-performance ComputingComputer GraphicsParallel ComputingSocial InfluenceData ParallelismGraph AlgorithmsGraph AnalyticsGraphics Processing Unit ComputingSocial Network AnalysisSocial Network MiningComputational EfficiencyDivergenceGpgpu ComputingGpu ArchitectureGpu Parallel AlgorithmsGraph ProcessingGreedy HeuristicsParallel Processing
Influence Maximization aims to find the top-$(K)$ influential individuals to maximize the influence spread within a social network, which remains an important yet challenging problem. Proven to be NP-hard, the influence maximization problem attracts tremendous studies. Though there exist basic greedy algorithms which may provide good approximation to optimal result, they mainly suffer from low computational efficiency and excessively long execution time, limiting the application to large-scale social networks. In this paper, we present IMGPU, a novel framework to accelerate the influence maximization by leveraging the parallel processing capability of graphics processing unit (GPU). We first improve the existing greedy algorithms and design a bottom-up traversal algorithm with GPU implementation, which contains inherent parallelism. To best fit the proposed influence maximization algorithm with the GPU architecture, we further develop an adaptive K-level combination method to maximize the parallelism and reorganize the influence graph to minimize the potential divergence. We carry out comprehensive experiments with both real-world and sythetic social network traces and demonstrate that with IMGPU framework, we are able to outperform the state-of-the-art influence maximization algorithm up to a factor of 60, and show potential to scale up to extraordinarily large-scale networks.
19
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
What is Twitter, a social network or a news media?
Haewoon Kwak, Changhyun Lee, Hosung Park et al. · 2010 · 6.7K citations · Full text
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin et al. · 2007 · 2.5K citations · Full text
Public Health, Environmental Sciences, Outbreak Detection +7
Jure Leskovec, Jon Kleinberg, Christos Faloutsos · 2005 · 2.3K citations