標題: Efficient algorithms for influence maximization in social networks
作者: Chen, Yi-Cheng
Peng, Wen-Chih
Lee, Suh-Yin
資訊工程學系
Department of Computer Science
關鍵字: Community discovery;Diffusion models;Influence maximization;Social network
公開日期: 1-十二月-2012
摘要: In recent years, due to the surge in popularity of social-networking web sites, considerable interest has arisen regarding influence maximization in social networks. Given a social network structure, the problem of influence maximization is to determine a minimum set of nodes that could maximize the spread of influences. With a large-scale social network, the efficiency and practicability of such algorithms are critical. Although many recent studies have focused on the problem of influence maximization, these works in general are time-consuming when a social network is large-scale. In this paper, we propose two novel algorithms, CDH-Kcut and Community and Degree Heuristic on Kcut/SHRINK, to solve the influence maximization problem based on a realistic model. The algorithms utilize the community structure, which significantly decreases the number of candidates of influential nodes, to avoid information overlap. The experimental results on both synthetic and real datasets indicate that our algorithms not only significantly outperform the state-of-the-art algorithms in efficiency but also possess graceful scalability.
URI: http://dx.doi.org/10.1007/s10115-012-0540-7
http://hdl.handle.net/11536/20607
ISSN: 0219-1377
DOI: 10.1007/s10115-012-0540-7
期刊: KNOWLEDGE AND INFORMATION SYSTEMS
Volume: 33
Issue: 3
起始頁: 577
結束頁: 601
顯示於類別:期刊論文


文件中的檔案:

  1. 000310871700004.pdf