Timezone: »

 
Poster
Online Influence Maximization under Linear Threshold Model
Shuai Li · Fang Kong · Kejie Tang · Qizhi Li · Wei Chen

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #1163
in Poster Session 3 »
Online influence maximization (OIM) is a popular problem in social networks to learn influence propagation model parameters and maximize the influence spread at the same time. Most previous studies focus on the independent cascade (IC) model under the edge-level feedback. In this paper, we address OIM in the linear threshold (LT) model. Because node activations in the LT model are due to the aggregated effect of all active neighbors, it is more natural to model OIM with the node-level feedback. And this brings new challenge in online learning since we only observe aggregated effect from groups of nodes and the groups are also random. Based on the linear structure in node activations, we incorporate ideas from linear bandits and design an algorithm $\ltlinucb$ that is consistent with the observed feedback. By proving group observation modulated (GOM) bounded smoothness property, a novel result of the influence difference in terms of the random observations, we provide a regret of order $\tilde{O}(\mathrm{poly}(m)\sqrt{T})$, where $m$ is the number of edges and $T$ is the number of rounds. This is the first theoretical result in such order for OIM under the LT model. In the end, we also provide an algorithm $\oimetc$ with regret bound $O(\mathrm{poly}(m)\ T^{2/3})$, which is model-independent, simple and has less requirement on online feedback and offline computation.

Author Information

Shuai Li (Shanghai Jiao Tong University)
Fang Kong (Shanghai Jiao Tong University)
Kejie Tang (Shanghai Jiao Tong University)
Qizhi Li (Shanghai Jiao Tong University)
Wei Chen (Microsoft Research)

More from the Same Authors