摘要：

现有关于不确定图的研究较少考虑图中边对于信息传播的影响力,而对影响力较大的边进行查询和利用能够解决现实中很多问题。为此,给出在不确定图中查询边影响力的定义,研究解决该类问题的基本方法。针对穷举所有可能图时带来的时间随边数指数增长问题,提出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

中图分类号: 

• TP392