用昂贵的网络信息播种-研究论文

我们研究了社交网络中 k 个节点的选择，以播种具有最大预期传播大小的扩散。 之前关于这个问题的大部分工作（称为影响最大化）都集中在有效的算法上，以在假设了解整个网络的情况下，用可证明的保证来逼近最优种子集。 然而，在实践中，获得网络的全部知识是非常昂贵的。 为了解决这个差距，我们提出了对图结构进行有限数量查询并提供几乎严格的近似保证的算法。 我们在经验网络数据上测试我们的算法，以量化获取更精细网络信息的成本与用于指导改进播种策略的附加信息的好处之间的权衡。