Approximate Solutions for the Influence Maximization Problem in a Social Network
Approximate Solutions for the Influence Maximization Problem in a Social Network
复制标题
DOI：
10.1007/11893004_120
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
M. Kimura;Kazumi Saito
中科院分区：
文献类型：
--
作者：
M. Kimura;Kazumi Saito
本文基于独立级联模型（ICM）研究了大规模社会网络中信息传播的最大化问题。当我们解决影响最大化问题，即选择最有影响力的节点的优化问题时，我们需要计算给定节点集合所影响的节点的期望数量。然而，对该量的精确计算或良好估计需要大量的计算。因此，需要非常大的计算量来近似地解决基于自然贪婪算法的影响最大化问题。在本文中，我们提出的方法，有效地获得良好的近似解的影响最大化问题的情况下，通过链路的传播概率很小。使用真实的数据在一个大规模的博客网络，我们实验证明了所提出的方法的有效性。
We address the problem of maximizing the spread of information in a large-scale social network based on theIndependent Cascade Model (ICM). When we solve theinfluence maximization problem, that is, the optimization problem of selecting the most influential nodes, we need to compute the expected number of nodes influenced by a given set of nodes. However, an exact calculation or a good estimate of this quantity needs a large amount of computation. Thus, very large computational quantities are needed to approximately solve the influence maximization problem based on a natural greedy algorithm. In this paper, we propose methods to efficiently obtain good approximate solutions for the influence maximization problem in the case where the propagation probabilities through links are small. Using real data on a large-scale blog network, we experimentally demonstrate the effectiveness of the proposed methods.