TY - GEN
T1 - A hierarchy based influence maximization algorithm in social networks
AU - Li, Lingling
AU - Li, Kan
AU - Xiang, Chao
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2018.
PY - 2018
Y1 - 2018
N2 - Influence maximization refers to mining top-K most influential nodes from a social network to maximize the final propagation of influence in the network, which is one of the key issues in social network analysis. It is a discrete optimization problem and is also NP-hard under both independent cascade and linear threshold models. The existing researches show that although the greedy algorithm can achieve an approximate ratio of (1-1/e), its time cost is expensive. Heuristic algorithms can improve the efficiency, but they sacrifice a certain degree of accuracy. In order to improve efficiency without sacrificing much accuracy, in this paper, we propose a new approach called Hierarchy based Influence Maximization algorithm (HBIM in short) to mine top-K influential nodes. It is a two-phase method: (1) an algorithm for detecting information diffusion levels based on the first-order and second-order proximity between social nodes. (2) a dynamic programming algorithm for selecting levels to find influential nodes. Experiments show that our algorithm outperforms the benchmarks.
AB - Influence maximization refers to mining top-K most influential nodes from a social network to maximize the final propagation of influence in the network, which is one of the key issues in social network analysis. It is a discrete optimization problem and is also NP-hard under both independent cascade and linear threshold models. The existing researches show that although the greedy algorithm can achieve an approximate ratio of (1-1/e), its time cost is expensive. Heuristic algorithms can improve the efficiency, but they sacrifice a certain degree of accuracy. In order to improve efficiency without sacrificing much accuracy, in this paper, we propose a new approach called Hierarchy based Influence Maximization algorithm (HBIM in short) to mine top-K influential nodes. It is a two-phase method: (1) an algorithm for detecting information diffusion levels based on the first-order and second-order proximity between social nodes. (2) a dynamic programming algorithm for selecting levels to find influential nodes. Experiments show that our algorithm outperforms the benchmarks.
KW - Hierarchy
KW - Influence maximization
KW - Social networks
UR - http://www.scopus.com/inward/record.url?scp=85054879666&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-01421-6_42
DO - 10.1007/978-3-030-01421-6_42
M3 - Conference contribution
AN - SCOPUS:85054879666
SN - 9783030014209
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 434
EP - 443
BT - Artificial Neural Networks and Machine Learning – ICANN 2018 - 27th International Conference on Artificial Neural Networks, 2018, Proceedings
A2 - Manolopoulos, Yannis
A2 - Hammer, Barbara
A2 - Maglogiannis, Ilias
A2 - Kurkova, Vera
A2 - Iliadis, Lazaros
PB - Springer Verlag
T2 - 27th International Conference on Artificial Neural Networks, ICANN 2018
Y2 - 4 October 2018 through 7 October 2018
ER -