TY - GEN
T1 - Dynamic update upper bounds influence maximization algorithm
AU - Shang, Junying
AU - Li, Kan
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/12/8
Y1 - 2018/12/8
N2 - In the field of social network analysis, influence maximization is an important research area. The goal is to find K nodes that maximize the final range of influence based on a given spread model. In the study of influence maximization, the research method based on greedy algorithm mainly focuses on how to further reduce Monte-Carlo simulations. In this paper, based on the dynamic update of the upper bound of marginal benefit of node, we propose an Upper Bound Update Greedy (UBUG) algorithm and an Upper Bound Update Heuristic (UBUH) algorithm. Experimental results show that the UBUG algorithm can reduce more MC simulations than the CELF [1] and UBLF [2] algorithms without losing the accuracy of the results. And compared to other heuristic algorithms, the UBUH not only meets the requirements of high calculation speed but also has a good accuracy.
AB - In the field of social network analysis, influence maximization is an important research area. The goal is to find K nodes that maximize the final range of influence based on a given spread model. In the study of influence maximization, the research method based on greedy algorithm mainly focuses on how to further reduce Monte-Carlo simulations. In this paper, based on the dynamic update of the upper bound of marginal benefit of node, we propose an Upper Bound Update Greedy (UBUG) algorithm and an Upper Bound Update Heuristic (UBUH) algorithm. Experimental results show that the UBUG algorithm can reduce more MC simulations than the CELF [1] and UBLF [2] algorithms without losing the accuracy of the results. And compared to other heuristic algorithms, the UBUH not only meets the requirements of high calculation speed but also has a good accuracy.
KW - Influence maximization
KW - Social network
KW - Upper bounds
UR - http://www.scopus.com/inward/record.url?scp=85062783920&partnerID=8YFLogxK
U2 - 10.1145/3297156.3297185
DO - 10.1145/3297156.3297185
M3 - Conference contribution
AN - SCOPUS:85062783920
T3 - ACM International Conference Proceeding Series
SP - 212
EP - 217
BT - Proceedings of the 2018 2nd International Conference on Computer Science and Artificial Intelligence, CSAI 2018 - 2018 the 10th International Conference on Information and Multimedia Technology, ICIMT 2018
PB - Association for Computing Machinery
T2 - 2nd International Conference on Computer Science and Artificial Intelligence, CSAI 2018
Y2 - 8 December 2018 through 10 December 2018
ER -
