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 (2006) proposed an algorithm to update PageRank using an aggregation/disaggregation concept. In Bahmani et al. (2012), an algorithm that estimates a PageRank vector by crawling a small portion of the graph has been proposed, while Ohsaka et al. (2015) proposed an updating method for personalized PageRanks. In addition, the idea of partitioning information networks into connected acyclic and strongly connected components and then applying iterative methods of solving linear systems - while keeping an eye on the component(s) that has evolved - is proposed in Engström (2016) and Engström and Silvestrov (2016). In fact, all of these authors treat PageRank computation using matrix-vector multiplication.

There is evidence that tree graphs have applications in science and engineering. For instance, in Han et al. (2016), a directed acyclic graph (DAG) has been used in optimization problems, while Shandilya et al. (2014) applies the graph model in security systems.

Furthermore, tree graphs have been used to investigate ecological systems and functional similarity in biological networks (Ulanowicz 2004; Rocchi et al. 2017). For the case of an ecosystem, analysis of extinction risk or identifying important species in such a network is of significance (Allesina and Bodini 2004; Allesina and Pascual 2009). The notion of modeling an ecosystem as a tree graph is the result of mutual dependence between interacting species, for instance, dominator tree and food web structures (Ulanowicz 2004). In fact, dependence interaction can lead to interesting problems of network evolution. For example, if an organism Y requires nutrients from an organism X, in short, X Y, then lack of nutrients from X may lead to the extinction of Y unless it switches to another form of resource by addition of a new link. This is one of the primary roles of ecosystem-based management, as mentioned in Rocchi et al. (2017).

According to Wang et al. (2010), it has been found that a gene's functions are closely associated with different diseases, and such a dependence relationship requires a tree graph model. In view of Wang et al. (2010) and Han et al. (2016), a graph model improves computation cost and conceptualizes large networks.

The existing methods are virtually rooted in the iterative techniques which might be demanding when a localized change only occurs in a large network. Furthermore, the methods pay little attention to specific kinds of networks such as tree and strongly connected graphs. Computing PageRank of such components can lead to a great reduction in time complexity. For example, vertices of a strongly connected graph can be reordered by a feedback vertex set. In light of all of the above, we focus on the algorithm that updates PageRank when vertices are reordered by their levels, specifically for evolving directed tree graphs.

The remaining sections of this chapter are organized as follows. In section 1.2, we propose a technique for updating transition matrices when an edge is added or removed. Section 1.3 presents a single vertex update of PageRank when an edge is inserted or removed. Furthermore, we demonstrate that refinement iterative formation of linear systems fits in a single vertex update. Section 1.4 is devoted to maintaining the levels of vertices after some changes, and the conclusion is given in section 1.5.

1.2. Notations and definitions

For convenience, we define some notations that will be used throughout this chapter.

• - Let us denote a directed graph by G = (V, E), where V and E are sets of vertices and edges, respectively. The number of vertices in graph G will be denoted by |V | or n. Furthermore, G ? ?G will denote a new graph after some changes of the edges or vertices.
• - A ? Rn×n represents a matrix derived from G, and Ai means the ith row of A.
• - denotes a column vector, and represents a row vector. We denote as a vector with 1 in the ith entry and 0 elsewhere.
• - is the personalization vector of the vertices, which can be thought of as preference assigned to each of the vertices, and c is the damping parameter, usually taken to be 0.85.

DEFINITION 1.1.- A directed tree graph G is a digraph without cycles.

DEFINITION 1.2.- The PageRank of a vertex vi, denoted by pi, is defined as

where deg(u) is the degree of u and No is the out-neighbor of u. If vi is a root, then pi = (1 - c)?i.

1.3. Updating the transition matrix

In this section, we present how to update the transition matrix when an edge(s) is added or removed. Two cases are considered:

(1) a source vertex vi has at most one outgoing edge and at least one edge is added;

(2) a source vertex vi has at least one outgoing edge and at least one edge is removed.

Each case will be handled separately.

Case 1: Addition of an edge to a source vertex with and without outgoing edges.

LEMMA 1.1.- Let A(1) and A(2) be transition matrices of a tree graph G and G??G, respectively. Let deg(vi) be the out-degree of vertex vi. Suppose an edge vi vj is added, then a new matrix A(2) can be updated as

1. (i) A(2) = A(1) + , if deg(vi) = 0;
2. (ii) A(2) = , if deg(vi) = 1.

We remark that a matrix A in (ii) is a sub-matrix of unaffected vertices in the graph G.

PROOF.- (i) Let be a column vector with 1 at the ith entry and 0 elsewhere. If there was no edge between vertex vi and vj, then the only edge is the new one, vi vj. To write the new transition matrix A(2), we apply the well-known shearing matrix properties: If , for i, j = 1, 2, . . . , n, then

where A(1) = . Upon adding vi vj the entry , hence A(2) = A(1) + .

(ii) Let us define an operation on identity matrix I, at an entry (i, i) as in Lancaster and Tismenetsky (1985), then

Then, the result of multiplying the ith row of A(1) by a non-zero scalar µ yields

Using Lemma 1.1 (i) and substituting , we write

where A = .

Adding an edge vi vk, for k ? j to the source vertex vi, the weight of the outgoing edges changes to . Let , and by applying relation [1.2], we get

rearranging [1.3] completes the proof.

?

Let V0 be a set of vertices without outgoing edges and suppose vh ? V0. Then, a generalization of Lemma 1.1(i) when multiple edges, say k edges, are added takes the form

Without loss of generality, we define the transition matrix A(2) when the source vertex vi has the degree deg(vi) and k edges are added to distinct target vertices as

where is a row vector with 1 in all the k target vertices and 0 elsewhere.

Case 2: Removal of edge(s) from a source vertex with at least one outgoing edge.

LEMMA 1.2.- Let A(1) and A(2) be transition matrices of tree graphs G and G??G, respectively. Suppose an edge vi vj is removed, then...