计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (34): 87-88.DOI: 10.3778/j.issn.1002-8331.2008.34.026

• 网络、通信、安全 • 上一篇    下一篇

改进贪婪算法在博客突发事件检测中的研究

王 杰,刚轶金,李凤光,吴伟巍   

  1. 郑州大学 电气工程学院,郑州 450001
  • 收稿日期:2008-06-17 修回日期:2008-09-10 出版日期:2008-12-01 发布日期:2008-12-01
  • 通讯作者: 王 杰

Research of improved greed algorithm used in blogsphere outbreak detection

WANG Jie,GANG Yi-jin,LI Feng-guang,WU Wei-wei   

  1. School of Electrical Engineering,Zhengzhou University,Zhengzhou 450001,China
  • Received:2008-06-17 Revised:2008-09-10 Online:2008-12-01 Published:2008-12-01
  • Contact: WANG Jie

摘要: 博客在当今人们的生活中起到重要的作用,但是人们在有限的时间内读哪些博客而不丢失重要的内容呢?这个问题可以看做是突发检测,也就是从众多博客里面选取一个。用改进贪婪算法来处理这种和类似问题,并阐述了“子模性”的概念。这种算法能推广应用到其他领域,仿真表明此算法能够接近最优结果。

关键词: 博客, 突发检测, 贪婪算法, 子模性

Abstract: Blogs play an important role in our daily life today,but which blogs should we read to avoid missing important stories at limit time?This question can be as outbreak detection which can be modeled as selecting blogs in a blogsphere network.This paper uses a new methodology which improved from normal greed algorithm for detecting this problem in this and related problems,exhibiting the property of “submodularity”.This efficient algorithm scales to large problems,simulation results achieving near optimal solution.

Key words: blogs, outbreak detection, greed algorithm, submodularity