Efficient Computing of PageRank Scores on Exact Expected Transition Matrix of Large Uncertain Graph

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.