• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文期刊> 《物理学报》 >一种新的复杂网络影响力最大化发现方法∗

一种新的复杂网络影响力最大化发现方法∗

         
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Influence maximization modeling and analyzing is a critical issue in social network analysis in a complex network environment, and it can be significantly beneficial to both theory and real life. Given a fixed number k, how to find the set size k which has the greatest influencing scope is a combinatory optimization problem that has been proved to be NP-hard by Kempe et al. (2003). State-of-the-art random algorithm, although it is computation efficient, yields the worst performance;on the contrary, the well-studied greedy algorithms can achieve approximately optimal performance but its computing complexity is prohibitive for large social network; meanwhile, these algorithms should first acquire the global information (topology) of the network which is impractical for the colossal and forever changing network. We propose a new algorithm for influence maximization computing-RMDN and its improved version RMDN++. RMDN uses the information of a randomly chosen node and its nearest neighboring nodes which can avoid the procedure of knowing knowledge of the whole network. This can greatly accelerate the computing process, but its computing complexity is limited to the order of O(k log(n)). We use three different real-life datasets to test the effectiveness and efficiency of RMDN in IC model and LT model respectively. Result shows that RMDN has a comparable performance as the greedy algorithms, but obtains orders of magnitude faster according to different network; in the meantime, we have systematically and theoretically studied and proved the feasibility of our method. The wider applicability and stronger operability of RMDN may also shed light on the profound problem of influence maximization in social network.

著录项

  • 来源
    《物理学报》 |2015年第19期|1-12|共12页
  • 作者

    胡庆成; 张勇; 许信辉; 邢春晓; 陈池; 陈信欢;

  • 作者单位

    清华大学计算机科学与技术系;

    信息技术研究院;

    清华信息科学与技术国家实验室;

    北京 100084;

    清华大学计算机科学与技术系;

    信息技术研究院;

    清华信息科学与技术国家实验室;

    北京 100084;

    清华大学计算机科学与技术系;

    信息技术研究院;

    清华信息科学与技术国家实验室;

    北京 100084;

    清华大学计算机科学与技术系;

    信息技术研究院;

    清华信息科学与技术国家实验室;

    北京 100084;

    清华大学计算机科学与技术系;

    信息技术研究院;

    清华信息科学与技术国家实验室;

    北京 100084;

    清华大学计算机科学与技术系;

    信息技术研究院;

    清华信息科学与技术国家实验室;

    北京 100084;

  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类
  • 关键词

    复杂网络; 影响力最大化; 信息传播; 贪心算法;

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号