Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (34): 87-88.DOI: 10.3778/j.issn.1002-8331.2008.34.026

• 网络、通信、安全 • Previous Articles     Next Articles

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


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

  1. 郑州大学 电气工程学院,郑州 450001
  • 通讯作者: 王 杰

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

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

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