Scalable Influence Estimation in Continuous-Time Diffusion Networks
Scalable Influence Estimation in Continuous-Time Diffusion Networks
复制标题
DOI：
--
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Nan Du;Le Song;M. Gomez-Rodriguez;H. Zha
中科院分区：
文献类型：
--
作者：
Nan Du;Le Song;M. Gomez-Rodriguez;H. Zha
如果一条信息从一个媒体网站上发布，我们能预测它是否会在一个月内传播到100万个网页上吗？这个影响估计问题是非常具有挑战性的，因为这两个任务的时间敏感性和可扩展性的要求需要同时解决。在本文中，我们提出了一个随机算法在连续时间扩散网络的影响估计。我们的算法可以估计网络中每个节点的影响，|V|节点和|ε|使用n = O（1/ε2）随机化和最多对数因子O（n）的精确度为ε的边缘|ε| +n| V|）计算。当作为贪婪影响最大化方法中的子程序使用时，我们提出的算法保证找到一组C节点，其影响至少为（1 - 1/e）OPT - 2Cε，其中OPT是最优值。在合成数据和真实数据上的实验表明，该算法可以很容易地扩展到数百万个节点的网络，同时在估计影响的准确性和最大化影响时所选节点的质量方面比以前的最新技术有显著提高。
If a piece of information is released from a media site, can we predict whether it may spread to one million web pages, in a month ? This influence estimation problem is very challenging since both the time-sensitive nature of the task and the requirement of scalability need to be addressed simultaneously. In this paper, we propose a randomized algorithm for influence estimation in continuous-time diffusion networks. Our algorithm can estimate the influence of every node in a network with |V| nodes and |ε| edges to an accuracy of ε using n = O(1/ε2) randomizations and up to logarithmic factors O(n|ε|+n|V|) computations. When used as a subroutine in a greedy influence maximization approach, our proposed algorithm is guaranteed to find a set of C nodes with the influence of at least (1 - 1/e) OPT - 2Cε , where OPT is the optimal value. Experiments on both synthetic and real-world data show that the proposed algorithm can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence.