TY - GEN
T1 - Learning cascaded influence under partial monitoring
AU - Zhang, Jie
AU - Ma, Jiaqi
AU - Tang, Jie
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/11/21
Y1 - 2016/11/21
N2 - Social influence has attracted tremendous attention from both academic and industrial communities due to the rapid development of online social networks. While most research has been focused on the direct influence between peers, learning cascaded indirect influence has not been previously studied. In this paper, we formulate the concept of cascade indirect influence based on the Independent Cascade model and then propose a novel online learning algorithm for learning the cascaded influence in the partial monitoring setting. We propose two bandit algorithms E-EXP3 and RE-EXP3 to address this problem. We theoretically prove that E-EXP3 has a cumulative regret bound of O(√T) over T, the number of time stamps. We will also show that RE-EXP3, a relaxed version of E-EXP3, achieves a better performance in practice. We compare the proposed algorithms with three baseline methods on both synthetic and real networks (Weibo and AMiner). Our experimental results show that RE-EXP3 converges 100× faster than E-EXP3. Both of them significantly outperform the alternative methods in terms of normalized regret. Finally, we apply the learned cascaded influence to help behavior prediction and experiments show that our proposed algorithms can help achieve a significant improvement (10-15% by accuracy) for behavior prediction.
AB - Social influence has attracted tremendous attention from both academic and industrial communities due to the rapid development of online social networks. While most research has been focused on the direct influence between peers, learning cascaded indirect influence has not been previously studied. In this paper, we formulate the concept of cascade indirect influence based on the Independent Cascade model and then propose a novel online learning algorithm for learning the cascaded influence in the partial monitoring setting. We propose two bandit algorithms E-EXP3 and RE-EXP3 to address this problem. We theoretically prove that E-EXP3 has a cumulative regret bound of O(√T) over T, the number of time stamps. We will also show that RE-EXP3, a relaxed version of E-EXP3, achieves a better performance in practice. We compare the proposed algorithms with three baseline methods on both synthetic and real networks (Weibo and AMiner). Our experimental results show that RE-EXP3 converges 100× faster than E-EXP3. Both of them significantly outperform the alternative methods in terms of normalized regret. Finally, we apply the learned cascaded influence to help behavior prediction and experiments show that our proposed algorithms can help achieve a significant improvement (10-15% by accuracy) for behavior prediction.
UR - http://www.scopus.com/inward/record.url?scp=85006833504&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85006833504&partnerID=8YFLogxK
U2 - 10.1109/ASONAM.2016.7752243
DO - 10.1109/ASONAM.2016.7752243
M3 - Conference contribution
AN - SCOPUS:85006833504
T3 - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
SP - 255
EP - 262
BT - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
A2 - Kumar, Ravi
A2 - Caverlee, James
A2 - Tong, Hanghang
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
Y2 - 18 August 2016 through 21 August 2016
ER -