Abstract—It’s a challenging task to find a subset of node of
size k in a social network such that targeting them initially as
the seeds will maximize the influence spread. This problem is
proved to be a NP-hard problem. We solve this problem in two
aspects: 1) we improve the basic greedy algorithm, limiting the
influence spread in a neighbor space to reduce the running
time. We use the DAG and the recursion method to calculate
the influence spread of each node. Also we transform this
problem to a reachable probability query problem in an
uncertain graph; 2) we present a more accurate degree
discount heuristic algorithm which considers the relationship
between the node and its neighbors. Intensive experiments on a
large real-world social network show that: our improved
greedy algorithm and degree discount heuristic algorithm are
more efficient than the basic greedy algorithm and other
heuristic methods.
Index Terms—Classify-tree, DAG, degree heuristic, greedy,
influence spread maximization, sampling.
The authors are with the Massive Data Computing Research Lab,
Computer Science and Technology, Harbin Institute of Technology (e-mail:
xinfeishi@gmail.com, wangzh@hit.edu.cn, lijzh@hit.edu.cn).
Cite:Xinfei Shi, Hongzhi Wang, Jianzhong Li, and Hong Gao, "Influence Spread Maximization in Social Network," International Journal of Information and Education Technology vol. 3, no. 6, pp. 660-666, 2013.