title: A Fast and Efficient Algorithm for Mining Top-k Nodes in Complex Networks.
abstract: One of the key problems in social network analysis is influence maximization, which has great significance both in theory and practical applications. Given a complex network and a positive integer k, and asks the k nodes to trigger the largest expected number of the remaining nodes. Many mature algorithms are mainly divided into propagation-based algorithms and topology- based algorithms. The propagation-based algorithms are based on optimization of influence spread process, so the influence spread of them significantly outperforms the topology-based algorithms. But these algorithms still takes days to complete on large networks. Contrary to propagation based algorithms, the topology-based algorithms are based on intuitive parameter statistics and static topology structure properties. Their running time are extremely short but the results of influence spread are unstable. In this paper, we propose a novel topology-based algorithm based on local index rank (LIR). The influence spread of our algorithm is close to the propagation-based algorithm and sometimes over them. Moreover, the running time of our algorithm is millions of times shorter than that of propagation-based algorithms. Our experimental results show that our algorithm has a good and stable performance in IC and LT model.
authors.affiliation: School of Computer and information Engineering, Henan Normal University, Xinxiang, 453007, China.|Engineering Technology Research Center for Computing Intelligence and Data Mining, Henan Province, Xinxiang 453007, China.
authors.forename: Dong
authors.initials: D
authors.lastname: Liu
authors.affiliation: School of Computer and information Engineering, Henan Normal University, Xinxiang, 453007, China.
authors.forename: Yun
authors.initials: Y
authors.lastname: Jing
authors.affiliation: School of Computer and information Engineering, Henan Normal University, Xinxiang, 453007, China.
authors.forename: Jing
authors.initials: J
authors.lastname: Zhao
authors.affiliation: School of Computer Science and Technology, Tianjin University, Tianjin, 300350, China.
authors.forename: Wenjun
authors.initials: W
authors.lastname: Wang
authors.affiliation: Key Laboratory of Machine Perception, Peking University, Beijing, 100871, China.
authors.forename: Guojie
authors.initials: G
authors.lastname: Song