PageRank in Evolving Tree Graphs

TitlePageRank in Evolving Tree Graphs
Publication TypeJournal Article
Year of Publication2018
AuthorsAbola, B, Biganda, PSeleka, Engström, C, Mango, JMagero, Kakuba, G, Silvestrov, S
Date Published05 December 2018
KeywordsBreadth-first search Forward edge PageRank Random walk Tree

In this article, we study how PageRank can be updated in an evolving tree graph. We are interested in finding how ranks of the graph can be updated simultaneously and effectively using previous ranks without resorting to iterative methods such as the Jacobi or Power method. We demonstrate and discuss how PageRank can be updated when a leaf is added to a tree, at least one leaf is added to a vertex with at least one outgoing edge, an edge added to vertices at the same level and forward edge is added in a tree graph. The results of this paper provide new insights and applications of standard partitioning of vertices of the graph into levels using breadth-first search algorithm. Then, one determines PageRanks as the expected numbers of random walk starting from any vertex in the graph. We noted that time complexity of the proposed method is linear, which is quite good. Also, it is important to point out that the types of vertex play essential role in updating of PageRank.