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 LT-LinUCB 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 OIM-ETC 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.


翻译:在线影响最大化( OIM) 在社交网络中是一个流行的问题, 以学习传播模型参数的影响, 并同时最大限度地扩大影响范围。 大多数先前的研究都侧重于边端反馈下的独立的级联(IC) 模型。 在本文中, 我们用线性阈值( LT) 模型处理 OIM 。 由于LT 模型中的节点激活是所有活跃邻居的综合效应, 模拟 OIM 和节点级反馈比较自然。 这给在线学习带来了新的挑战, 因为我们只观察节点组和组群的汇总反馈效果也是随机的。 根据节点启动中的线性结构, 我们吸收线性突盗的想法, 设计一个与所观察到的反馈相一致的LT- LinUCB 算法 。 通过验证组式观察( GOM) 约束的光度属性, 随机观测的影响差异的新结果, 我们为 $tilde{ O} (mathrem} (mathrey} (ma) (marty) (m) 和 sqrt{t} (m) 提供了新的挑战 。 。 $ 。 美元是这个模型的底端端端端端点和 。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
123+阅读 · 2020年9月8日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【跟踪Tracking】15篇论文+代码 | 中秋快乐~
专知
18+阅读 · 2018年9月24日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
已删除
将门创投
4+阅读 · 2018年6月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
6+阅读 · 2018年11月29日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
5+阅读 · 2018年1月30日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【跟踪Tracking】15篇论文+代码 | 中秋快乐~
专知
18+阅读 · 2018年9月24日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
已删除
将门创投
4+阅读 · 2018年6月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员