作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2018, Vol. 44 ›› Issue (11): 19-26. doi: 10.19678/j.issn.1000-3428.0048861

• 先进计算与数据处理 • 上一篇    下一篇

不确定图上Top-k最大影响力边查询算法

胡阳1,黄金晶1,2,刘光富1,赵雷1   

  1. 1.苏州大学 计算机科学与技术学院,江苏 苏州 215006; 2.苏州工业职业技术学院 软件与服务外包学院,江苏 苏州 215104
  • 收稿日期:2017-10-09 出版日期:2018-11-15 发布日期:2018-11-15
  • 作者简介:胡阳(1990—),男,硕士研究生,主研方向为数据管理、数据分析;黄金晶,讲师、博士研究生;刘光富,硕士研究生;赵雷(通信作者),教授。
  • 基金资助:

    国家自然科学基金(61572335);江苏省自然科学基金(BK20151223)

Top-k Edge Query Algorithm with Maximum Influence on Uncertain Graph

HU Yang 1,HUANG Jinjing 1,2,LIU Guangfu 1,ZHAO Lei 1   

  1. 1.School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China; 2.Software and Service Outsourcing College,Suzhou Vocational Institute of Industrial Technology,Suzhou,Jiangsu 215104,China
  • Received:2017-10-09 Online:2018-11-15 Published:2018-11-15

摘要:

现有关于不确定图的研究较少考虑图中边对于信息传播的影响力,而对影响力较大的边进行查询和利用能够解决现实中很多问题。为此,给出在不确定图中查询边影响力的定义,研究解决该类问题的基本方法。针对穷举所有可能图时带来的时间随边数指数增长问题,提出2种抽样技术来近似解决,并且采用优化方法进一步提高效率。实验结果表明,基于FFB抽样的剪枝BFS算法具有较高的准确性和效率。

关键词: 不确定数据, 不确定图, 边影响力, 抽样技术, 最大影响力

Abstract:

Recently,researches on uncertain graphs mostly ignore the influence of edges when information spreading to the networks,meanwhile these influential edges could settle with many practical problems by querying and applying to them.So that this paper proposes the definition of the query of impact edges on the uncertain graph as well as the basic method to deal with this kind of problems.In order to overcome the hard problem that time consumption with edge size increases exponentially when calculating all the possible graphs,this paper proposes two kinds of sampling techniques to solve it approximately,and the optimization method is adopted to further improve the efficiency.Experimental results show that the pruned BFS method based on FFB sampling performs better in accuracy and efficiency.

Key words: uncertain data, uncertain graph, edge influence, sampling technique, maximum influence

中图分类号: