Efficient Computing of PageRank Scores on Exact Expected Transition Matrix of Large Uncertain Graph
Efficient Computing of PageRank Scores on Exact Expected Transition Matrix of Large Uncertain Graph
复制标题
DOI：
10.1109/bigdata50022.2020.9378076
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Takayasu Fushimi;Kazumi Saito;K. Ohara;M. Kimura;H. Motoda
中科院分区：
文献类型：
--
作者：
Takayasu Fushimi;Kazumi Saito;K. Ohara;M. Kimura;H. Motoda
当图很大时，由于可能世界的数量非常多，对不确定图中的节点进行排序的计算成本很高。一般来说，需要某种近似。我们专注于PageRank中心性度量排名，并提出了一种方法，不使用任何近似的不确定图中的所有链接可以是不确定的。我们首先准确地计算所有可能的图上的期望转移矩阵，然后只运行一次PageRank算法来对节点进行排名（p-avg方法）。这与首先计算每个图的得分，然后通过取平均值对节点进行排名（s-avg方法）不同。后者的精确计算是不可能的，因为沉重的计算负荷，只有近似的分数是通过抽样限制图形的数量。我们已经使用三个真实的世界网络从不同角度测试了性能。我们表明，所提出的方法（p-avg方法）提供了非常高的精度，以s-avg方法的高排名节点，可以是一个很好的替代它。实际上，p-avg方法运行的数量级，即，样本量，比s-avg方法更快。
Ranking nodes in uncertain graph is computationally expensive when the graph is huge due to the extremely large number of possible worlds. Some approximation is needed in general. We focus on PageRank centrality measure to rank and propose a method that does not use any approximation for uncertain graph in which all the links can be uncertain. We first compute the expected transition matrix over all the possible graphs accurately and then run PageRank algorithm only once to rank the nodes (p-avg approach). This is not the same as computing the scores for each individual graph first and then rank the nodes by taking their average (s-avg approach). Exact computation of the latter is not possible because of the heavy computational load and only the approximate scores are obtained by limiting the number of graphs by sampling. We have tested the performance from various angles using three real world networks. We show that the proposed method (p-avg approach) gives very high precision to the s-avg approach for highly ranked nodes and can be a good alternative to it. Pactically, the p-avg approach runs orders of magnitude, i.e., sample size, faster than the s-avg approach.