International Journal of
Information and Education Technology

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.