TY - GEN
T1 - Maximizing time-decaying influence in social networks
AU - Ohsaka, Naoto
AU - Yamaguchi, Yutaro
AU - Kakimura, Naonori
AU - Kawarabayashi, Ken Ichi
N1 - Funding Information:
N. O. was supported by JSPS Grant-in-Aid for JSPS Research Fellow Grant Number 16J09440. Y. Y. was supported by JSPS Grant-in-Aid for JSPS Fellows Grant Number 13J02522. N. K. was partially supported by JSPS KAKENHI Grant Numbers 25730001, 24106002.
Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016
Y1 - 2016
N2 - Influence maximization is a well-studied problem of finding a small set of highly influential individuals in a social network such that the spread of influence under a certain diffusion model is maximized. We propose new diffusion models that incorporate the time-decaying phenomenon by which the power of influence decreases with elapsed time. In standard diffusion models such as the independent cascade and linear threshold models, each edge in a network has a fixed power of influence over time. However, in practical settings, such as rumor spreading, it is natural for the power of influence to depend on the time influenced. We generalize the independent cascade and linear threshold models with time-decaying effects. Moreover, we show that by using an analysis framework based on submodular functions, a natural greedy strategy obtains a solution that is provably within (1 − 1/e) of optimal. In addition, we propose theoretically and practically fast algorithms for the proposed models. Experimental results show that the proposed algorithms are scalable to graphs with millions of edges and outperform baseline algorithms based on a state-of-the-art algorithm.
AB - Influence maximization is a well-studied problem of finding a small set of highly influential individuals in a social network such that the spread of influence under a certain diffusion model is maximized. We propose new diffusion models that incorporate the time-decaying phenomenon by which the power of influence decreases with elapsed time. In standard diffusion models such as the independent cascade and linear threshold models, each edge in a network has a fixed power of influence over time. However, in practical settings, such as rumor spreading, it is natural for the power of influence to depend on the time influenced. We generalize the independent cascade and linear threshold models with time-decaying effects. Moreover, we show that by using an analysis framework based on submodular functions, a natural greedy strategy obtains a solution that is provably within (1 − 1/e) of optimal. In addition, we propose theoretically and practically fast algorithms for the proposed models. Experimental results show that the proposed algorithms are scalable to graphs with millions of edges and outperform baseline algorithms based on a state-of-the-art algorithm.
UR - http://www.scopus.com/inward/record.url?scp=84988625085&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84988625085&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-46128-1_9
DO - 10.1007/978-3-319-46128-1_9
M3 - Conference contribution
AN - SCOPUS:84988625085
SN - 9783319461274
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 132
EP - 147
BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings
A2 - Giuseppe, Jilles
A2 - Landwehr, Niels
A2 - Manco, Giuseppe
A2 - Frasconi, Paolo
PB - Springer Verlag
T2 - 15th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2016
Y2 - 19 September 2016 through 23 September 2016
ER -