TY - GEN
T1 - Adaptive submodular influence maximization with myopic feedback
AU - Salha, Guillaume
AU - Tziortziotis, Nikolaos
AU - Vazirgiannis, Michalis
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/10/24
Y1 - 2018/10/24
N2 - This paper examines the problem of adaptive influence maximization in social networks. As adaptive decision making is a time-critical task, a realistic feedback model has been considered, called myopic. In this direction, we propose the myopic adaptive greedy policy that is guaranteed to provide a (1 - 1/e) -approximation of the optimal policy under a variant of the independent cascade diffusion model. This strategy maximizes an alternative utility function that has been proven to be adaptive monotone and adaptive submodular. The proposed utility function considers the cumulative number of active nodes through the time, instead of the total number of the active nodes at the end of the diffusion. Our empirical analysis on real-world social networks reveals the benefits of the proposed myopic strategy, validating our theoretical results.
AB - This paper examines the problem of adaptive influence maximization in social networks. As adaptive decision making is a time-critical task, a realistic feedback model has been considered, called myopic. In this direction, we propose the myopic adaptive greedy policy that is guaranteed to provide a (1 - 1/e) -approximation of the optimal policy under a variant of the independent cascade diffusion model. This strategy maximizes an alternative utility function that has been proven to be adaptive monotone and adaptive submodular. The proposed utility function considers the cumulative number of active nodes through the time, instead of the total number of the active nodes at the end of the diffusion. Our empirical analysis on real-world social networks reveals the benefits of the proposed myopic strategy, validating our theoretical results.
KW - adaptive submodularity
KW - influence maximization
KW - myopic feedback
KW - social networks
UR - https://www.scopus.com/pages/publications/85057329128
U2 - 10.1109/ASONAM.2018.8508254
DO - 10.1109/ASONAM.2018.8508254
M3 - Conference contribution
AN - SCOPUS:85057329128
T3 - Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
SP - 455
EP - 462
BT - Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
A2 - Tagarelli, Andrea
A2 - Reddy, Chandan
A2 - Brandes, Ulrik
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 10th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
Y2 - 28 August 2018 through 31 August 2018
ER -