Affiliations: [a] Shandong Province Key Laboratory of Wisdom Mine Information Technology, College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, China
| [b]
Qilu University of Technology/Shandong Academy of Sciences, Jinan, China
| [c]
Information Research Institute of Shandong Academy of Sciences, Jinan, China
| [d]
National Technical University of Ukraine, Igor Sikorsky Kyiv Polytechnic Institute
Correspondence:
[*]
Corresponding author. Shiwei Zhu, Qilu University of Technology/Shandong Academy of Sciences, Information Research Institute of Shandong Academy of Sciences, Jinan, 250014, China; National Technical University of Ukraine, Igor Sikorsky Kyiv Polytechnic Institute; E-mail: sc_zsw@163.com.
Abstract: Influence maximization is a classic network optimization problem, which has been widely used in the field of viral marketing. The influence maximization problem aims to find a fixed number of active nodes. After a specific propagation model, the number of active nodes reaches the maximum. However, the existing influence maximization algorithms are overly pursuing certain indicators of efficiency or accuracy, which cannot be well accepted by some researchers. This paper proposes an effective algorithm to balance the accuracy and efficiency of the influence maximization problem called local two-hop search algorithm (LTHS). The core of the proposed algorithm is a node not only be affected by one-hop neighbor nodes, but also by two-hop neighbor nodes. Firstly, this paper selects initial seed nodes according to the characteristics of the node degree. Generally, the high degree of nodes regards as influential nodes. Secondly, this paper proposes a node two-hop influence evaluate function called two-hop diffusion value (THDV), which can evaluate node influence more accurately. Furthermore, in order to seek higher efficiency, this paper proposes a method to reduce the network scale. This paper conducted full experiments on five real-world social network datasets, and compared with other four well-known algorithms. The experimental results show that the LTHS algorithm is better than the comparison algorithms in terms of efficiency and accuracy.
Keywords: Social network, influence maximization, local influence, heuristic algorithm
