FPPR: Fast Pessimistic PageRank for Dynamic Directed Graphs

Jan 1, 2022·
Rohith Parjanya
Suman Kundu
Suman Kundu
· 0 min read
Abstract

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.

Type
Publication
Complex Networks & Their Applications X
Suman Kundu
Authors
Suman Kundu
Assistant Professor
My research interests lies in the intersection of Graph Algorithms and AI including graph representation learning, social network analysis, network data science, streaming algorithms, information retrival, big data, and data visualization.