FPPR: Fast Pessimistic PageRank for Dynamic Directed Graphs


The paper presents a new algorithm for updating PageRank on dynamic directed graphs after the addition of a node. The algorithm uses the expected value of the random surfer to calculate the score of the newly added node and nodes of the existing chain where the new node is added. The complexity of the algorithm for k updates is $$backslashmathcal O(kbackslashtimes d_avg)$$O(k×davg). Extensive experiments have been performed on different synthetic and real-world networks. The experimental result shows that the rank generated by the proposed method is highly correlated with that of the benchmark algorithm of Power Iteration.

Complex Networks & Their Applications X