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

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.