期刊
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
卷 29, 期 2, 页码 359-372出版社
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2016.2620141
关键词
Influence maximization; influential nodes tracking; social network; scalable algorithm
类别
资金
- National High Technology Research and Development Program of China [2014AA015103]
- National Science and Technology Support Plan [2014BAG01B02]
- National Natural Science Foundation of China [61572041]
- Beijing Natural Science Foundation [4152023]
As both social network structure and strength of influence between individuals evolve constantly, it requires tracking the influential nodes under a dynamic setting. To address this problem, we explore the Influential Node Tracking (INT) problem as an extension to the traditional Influence Maximization problem (IM) under dynamic social networks. While the Influence Maximization problem aims at identifying a set of k nodes to maximize the joint influence under one static network, the INT problem focuses on tracking a set of influential nodes that keeps maximizing the influence as the network evolves. Utilizing the smoothness of the evolution of the network structure, we propose an efficient algorithm, Upper Bound Interchange Greedy (UBI) and a variant, UBI+. Instead of constructing the seed set from the ground, we start from the influential seed set we found previously and implement node replacement to improve the influence coverage. Furthermore, by using a fast update method by calculating the marginal gain of nodes, our algorithm can scale to dynamic social networks with millions of nodes. Empirical experiments on three real large-scale dynamic social networks show that our UBI and its variants, UBI+ achieves better performance in terms of both influence coverage and running time.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据