Influence Spread Maximization In Social Network

It’s a challenging task to find a subset of nodes of size k in a social networksuch that targeting them initially as the seeds will maximize the influence spread.This problem is proved to be a NP-hard problem. Luckily, the influence spreadfunction () has sub-modularity, so the basic greedy algorithm has ()approximation of the optimal result. But the greedy algorithm is very slow, so wesolve this problem in three aspects:(1) we improve the basic greedy algorithm,limiting the influence spread in a neighbor space to reduce the running time. We usethe DAG and the recursion method to calculate the influence spread of each node.(2)Also we transform this problem to a reachable probability query problem in anuncertain graph;(3) we present a more accurate degree discount heuristic algorithmwhich considers the relationship between the node and its one hop neighbors. Thenwe parallelize them using the Hadoop and present some other improvements for theabove three algorithms:(a) we divide and parallelize the computation of influencespread of nodes set to its member nodes;(b) we parallelize the independentsampling process, and we present a further parallel from the left-right child nodeinstead of the root node.(c) Enlarging the steps, calculating the relative influencespread of node considering the two hop neighbors according to the method of (3).And also, we present a new practicable method which can consider even biggersteps.Intensive experiments on a large real-world social network show that: ourimproved greedy algorithm and degree discount heuristic algorithm are moreefficient than the basic greedy algorithm and other heuristic methods. And theparallel and other improvements utilize the computational ability of clustersufficiently, improving the efficiency and accuracy of our algorithm. Hence, itmakes our algorithm more suitable for the large-scale social network dataset.