计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2091-2094.DOI: 10.11772/j.issn.1001-9081.2013.08.2091

• 网络与通信 •    下一篇

基于微博网络的影响力最大化算法

吴凯,季新生,郭进时,刘彩霞   

  1. 国家数字交换系统工程技术研究中心,郑州 450002
  • 收稿日期:2013-02-04 修回日期:2013-03-07 出版日期:2013-08-01 发布日期:2013-09-11
  • 通讯作者: 吴凯
  • 作者简介:吴凯(1988-),男,河北武安人,硕士研究生,主要研究方向:社会网络分析;
    季新生(1968-),男,江苏如东人,教授,博士,主要研究方向:移动通信;
    郭进时(1987-),女,吉林四平人,硕士研究生,主要研究方向:社会网络分析;
    刘彩霞(1974-),女,山东烟台人,副教授,博士,主要研究方向:移动通信、社会网络分析。
  • 基金资助:

    国家863计划项目

Influence maximization algorithm for micro-blog network

WU Kai,JI Xinsheng,GUO Jinshi,LIU Caixia   

  1. China National Digital Switching System Engineering and Technological R&D Center, Zhengzhou Henan 450002, China
  • Received:2013-02-04 Revised:2013-03-07 Online:2013-09-11 Published:2013-08-01
  • Contact: WU Kai

摘要: 由于影响范围的重叠效应,单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题,针对这一研究现状,提出一种用于微博网络中Top-K节点挖掘的算法GABE。通过归纳决定微博用户影响力的关键因素,提出了节点间影响率的概念,进而建立了用于用户影响力度量的WIR算法;根据得到的WIR值提出了符合微博特性的影响力传播模型,运用贪婪算法挖掘出微博网络中的Top-K节点。以爬取到的新浪微博数据进行了模拟验证,结果发现GABE在影响范围上与传统的最大化算法和影响力度量算法相比分别提高了7.7%和20%。这表明通过引入微博特性和贪婪思想,GABE较好地解决了微博网络中的影响力最大化问题。

关键词: 微博, 影响力度量, PageRank算法, 影响力最大化, 贪婪算法

Abstract: Influence maximization problem in micro-blog cannot be solved by simple user rank algorithm. To solve this problem, a greedy algorithm based on Extended Linear Threshold Model (ELTM) was proposed to solve Top-K problem in microblog. A concept of influence rate and a WIR (Weibo Influence Rank) algorithm were established to determine the user's influence by summarizing the key factors. Then, based on WIR values, an influence propagation model was proposed. After using greedy algorithm, the Top-K nodes were excavated. A simulation test based on Sina micro-blog was performed to validate the effectiveness of the proposed method. The result shows that the method outperforms the traditional algorithm.

Key words: micro-blog, influence measure, PageRank algorithm, influence maximization, greedy algorithm

中图分类号: