Applied Modeling Techniques and Data Analysis 1

1 A Variant of Updating PageRank in Evolving Tree Graphs

A PageRank update refers to the process of computing new PageRank values after a change(s) (addition or removal of links/vertices) has occurred in real-life networks. The purpose of updating is to avoid re-calculating the values from scratch. To efficiently carry out the update, we consider PageRank to be the expected number of visits to a target vertex if multiple random walks are performed, starting at each vertex once and weighing each of these walks by a weight value. Hence, it might be looked at as updating a non-normalized PageRank. We focus on networks of tree graphs and propose an approach to sequentially update a scaled adjacency matrix after every change, as well as the levels of the vertices. In this way, we can update the PageRank of affected vertices by their corresponding levels.

1.1. Introduction

Most real-world networks are continuously changing, and this phenomenon has come with challenges to the known data mining algorithms that assume the static form of datasets (Bahmani et al. 2012). Besides, it is a primary aim of network analysts to keep track of critical nodes.

Since Brin and Page (1998) pioneered PageRank centrality more than two decades ago, the centrality measure has found its applications in many disciplines (Gleich 2015). Recently, the study of PageRank of evolving graphs has drawn considerable attention and several computational models have been proposed. For instance, Langville and Meyer ...