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

摘要

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