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
Suman Kundu
Suman Kundu
Assistant Professor of Computer Science and Engineering

My research interests include social network analysis, network data science, streaming algorithms, big data, granular computing, soft computing, fuzzy and rough sets.