Influence maximization is the task of selecting a small number of seed nodes in a social network to maximize the spread of the influence from these seeds, and it has been widely investigated in the past two decades. In the canonical setting, the whole social network as well as its diffusion parameters is given as input. In this paper, we consider the more realistic sampling setting where the network is unknown and we only have a set of passively observed cascades that record the set of activated nodes at each diffusion step. We study the task of influence maximization from these cascade samples (IMS), and present constant approximation algorithms for this task under mild conditions on the seed set distribution. To achieve the optimization goal, we also provide a novel solution to the network inference problem, that is, learning diffusion parameters and the network structure from the cascade data. Comparing with prior solutions, our network inference algorithm requires weaker assumptions and does not rely on maximum-likelihood estimation and convex programming. Our IMS algorithms enhance the learning-and-then-optimization approach by allowing a constant approximation ratio even when the diffusion parameters are hard to learn, and we do not need any assumption related to the network structure or diffusion parameters.


翻译:影响最大化的任务是在社会网络中选择少量种子节点,以最大限度地扩大这些种子的影响的传播。 在过去二十年中,已经对此进行了广泛调查。在典型的环境中,整个社会网络及其传播参数被作为投入。在本文中,我们考虑的是网络未知的更现实的抽样环境,我们只有一套被动观察的级联,记录每个传播步骤的一组激活节点。我们研究的是从这些级联样本(IMS)中影响最大化的任务,并在种子集分布的温和条件下为这一任务提出恒定的近似算法。为了实现优化目标,我们还从级联数据中为网络推论问题提供了新的解决办法,即学习扩散参数和网络结构。与先前的解决办法相比,我们的网络推论算法需要较弱的假设,并不依赖最大相似的估算和convex编程。我们的IMS算法通过允许一个恒定的近比方法,即使传播参数难以学习,我们也不需要任何网络参数。

7
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
【Cell】神经算法推理,Neural algorithmic reasoning
专知会员服务
27+阅读 · 2021年7月16日
专知会员服务
123+阅读 · 2020年9月8日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
152+阅读 · 2020年5月26日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
已删除
将门创投
7+阅读 · 2018年8月28日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Inference for Dependent Data with Learned Clusters
Arxiv
0+阅读 · 2021年7月30日
Arxiv
0+阅读 · 2021年7月29日
Arxiv
0+阅读 · 2021年7月29日
Arxiv
0+阅读 · 2021年7月28日
Arxiv
0+阅读 · 2021年7月27日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
已删除
将门创投
7+阅读 · 2018年8月28日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员