Data Analysis and Applications 3, 3rd Edition

2Updating of PageRank in Evolving Treegraphs

Updating PageRank refers to a process of computing new PageRank values after change(s) has occurred in a graph. The main goal of the updating is to avoid recalculating the values from scratch. It is known from the literature that handling PageRank’s update is problematic, in particular when it involves both link and vertex updates. In this chapter, we focus on updating PageRank of an evolving treegraph when a vertex and an edge are added sequentially. We describe how to maintain level structures when a cycle is created and investigate the practical and theoretical efficiency to update PageRanks for an evolving graph with many cycles. In addition, we discuss the convergence of the power method applied to stochastic complement of Google matrix when a feedback vertex set is used.

2.1. Introduction

The field in which graphs are proving to be natural modeling abstraction in real life is vast. For instance, biological networks, transportation system, Internet, communication data and many others [GLE 15]. In spite of fundamental importance of graphical models, the challenges posed by processing huge graphs are not resolved yet. Such drawbacks include storage and keeping up with changes in edges or vertices. Numerous research efforts have been devoted to the study of dynamic graph problems [BAS 15, FRA 01].

In [FRA 01], dynamic algorithms for maintaining a breadth-first search tree in a directed graph were investigated. The study reveals ...