A Parallel PageRank Algorithm For Undirected Graph

PageRank is a fundamental property of graph and there have been plenty of PageRank algorithms. Generally, we consider undirected graph as a complicated directed graph. However, some properties of undirected graph, such as symmetry, are ignored when computing PageRank by existing algorithms. In this paper, we propose a parallel PageRank algorithm which is specially for undirected graph. We first demonstrate that the PageRank vector can be viewed as a linear combination of eigenvectors of probability transition matrix and the corresponding coefficients are the functions of eigenvalues. Then we introduce the Chebyshev polynomial approximation by which PageRank vector can be computed iteratively. Finally, we propose the parallel PageRank algorithm as the Chebyshev polynomial approximating algorithm(CPAA). Experimental results show that CPAA only takes 60% of iteration rounds of the power method and is at least 4 times faster than the power method.


I. INTRODUCTION
Plenty of applications such as power grids, traffic nets can be abstracted into undirected graph. PageRank [1], [2] is an essential field of graph including both directed graph and undirected graph. There is little work on computing PageRank of undirected graph. Usually, we consider undirected graph as a complicated directed graph when computing PageRank, and thus some disadvantages such as the increase in computation are inevitable. However, some important properties of undirected graph, such as symmetry, are ignored when computing PageRank by existing method.
For undirected graph, each eigenvalue of the probability transition matrix is real and the corresponding eigenvectors form a basis of the n-dimensional linear space. Then both personalized vector and PageRank vector are the linear combinations of the basis and completely determined by the coefficients. Thus computing PageRank vector from the personalized vector can be focused on the transformation of coefficients which is a function of eigenvalues. However, it is infeasible on large-scale graph because of the huge cost on computing eigenvalues and eigenvectors, we need another method to avoid this cost.
Chebyshev polynomial [3] is an effective tool on approximating. The recursion relation of Chebyshev polynomial can be extended to the domain of matrix, and thus the multiplication between Chebyshev matrix polynomial and personalized vector can be computed iteratively. It is possible to obtain the approximated PageRank vector without computing eigenvectors if we approximate the function of eigenvalues by Chebyshev polynomial. Naturally, we propose a parallel PageRank algorithm for undirected graph. The contributions of this paper are as follows: We show that PageRank vector of undirected graph is a linear combination of eigenvectors of the probability transition matrix and the corresponding coefficients are the functions of eigenvalues; We propose a parallel PageRank algorithm(CPAA) without computing eigenvectors for undirected graph; We compare CPAA with some other PageRank algorithms by experiments and the results demonstrate that CPAA converges faster.
The remains of this paper are as follows: section 2 is about the relate work; in section 3, we propose CPAA; some experiments are given in section 4; we conclude this paper in section 5.

II. RELATED WORKS
There have been plenty of PageRank algorithms [4] and Power method is the most fundamental one. Power method iteratively computes PageRank vector and the convergence rate depends on the damping factor. Although it has achieved success in many applications, power method is inefficient when dealing with the large-scale graph. Some improvements such as paralleling [5], utilizing the block structure [6] and utilizing the DAG structure [7] were proposed during the past decades.
Monte Carlo method [8] is also an excellent PageRank algorithm. From the perspective of stochastic process, PageRank can be viewed as the probability of each vertex being visited by a random walk which starts at a random vertex and walks according to the probability transition matrix. Monte Carlo method naturally supports parallelization. Some improvements based on the Monte Carlo method can be found in [9]- [11]. However, there is a big flaw that the Monte Carlo method requires large memory space and bandwidth.
Forward Push [12] is the state-of-the-art personalized PageRank algorithm and one of the improvements based on it is ITA. ITA is parallel and has low requirements on memory space and bandwidth. However, ITA is inefficient on undirected graph even compared with the power method since there is no dangling vertex or unreferenced vertex.

III. CPAA
In this section, we will propose a parallel PageRank algorithm which is specially for undirected graph. Firstly, we demonstrate that PageRank vector is the linear combination of eigenvectors of the probability transition matrix and the corresponding coefficients are the functions of eigenvalues. Then we introduce the Chebyshev polynomial and a method by which PageRank vector can be obtained without computing eigenvectors. Finally, we propose CPAA, a parallel PageRank algorithm for undirected graph. Before proceeding, we introduce some basic notations. Let a ij and P = AD −1 is the probability transition matrix. Then the PageRank vector π is given as where p is the personalized vector, I the identity matrix and c is the damping factor.

A. PAGERANK OF UNDIRECTED GRAPH
Proof. Given a n-dimensional vector y, we can have that Since Theorem 1. All the eigenvalues of P T are real.
We denote the eigenvalue of P T by λ and χ is the corresponding eigenvector, thus we can have Since B is positive definite matrix, we can have λ = λ, namely λ is real.
Since P has the same eigenvalues with P T , there exist n linearly independent eigenvectors of P . Let λ 1 , λ 2 , · · · , λ n denote the eigenvalues of P and χ 1 , χ 2 , · · · , χ n are the corresponding eigenvectors. Then χ 1 , χ 2 , · · · , χ n form a basis of n-dimensional linear space, and the personalized vector p satisfies p = n l=1 α l χ l .
Combine with (1), we can have that (6) shows that PageRank vector π is a linear combination of eigenvectors of P and the corresponding coefficients are the functions of eigenvalues. However, computing eigenvectors is inefficient when G(V, E) is large-scale graph. In next section, we will propose a new method by which π can be obtained without computing eigenvalues and eigenvectors.

B. CHEBYSHEV POLYNOMIAL APPROXIMATION
Chebyshev polynomial is a set of orthogonal polynomials with good properties. Let {T n (x)} denotes the Chebyshev polynomial, then T n (x) satisfies (a) |T n (x)| ≤ 1; Given a function f (x) ∈ C(a, b) and b a f 2 (x)dx < ∞, since Chebyshev polynomial is the optimal uniform approximating polynomial, we can have that T k (λ l )α l χ l . Since we can have that From (7) and (8), we can have that c k T k (P )p). (9)

C. CPAA
Since T k+1 (P )p = 2P T k (P )p − T k−1 (P )p, from (9), PageRank vector can be approximated iteratively without computing eigenvectors. The calculations on each vertex can be done in parallel at the same iteration round. However, invoking thread for each vertex is unrealistic, we can generate K calculating threads and then assign all the vertices to them. The parallel PageRank algorithm for undirected graph is given as the follow which we abbreviate as CPAA.

A. EXPERIMENTAL SETTING
In this section, we evaluate the performance of CPAA experimentally. We first show the convergence of CPAA and then compare CPAA with the single-threaded power method [1], [2] as well as the multi-threaded power method [13]. Let RES = ||π(k) − π(k − 1)|| 2 , where π(k) is the result of the k th iteration. And ERR = max the result of 210 th iterations of the power method as the true value. R is the iteration round and T is the consumption of CPU time. The thread numbers of CPAA and multi-threaded power method are all 32. All of the three algorithms are implemented by C++ multi-threading technology. Table 1 shows the hardware and software utilized by these numerical experiments. Table 2 shows all four data sets, where n is the amount of vertices, m is the amount of edges, nd is the amount of dangling vertices and deg = m n .  Figure 1 shows the relations between k, RES and T .

CPU
(1) The blue lines show that RES monotonously decreases with k and exhibits an exponential relationship; (2) The red lines show that T monotonously increase with k and exhibits an linear relationship; (3) RES decreases exponentially with T , namely CPAA is converged.  Figure 2 shows the relations between T and ERR and Table  3 shows T and R when ERR < 0.001.
(1) The blue and green lines in Figure 2 show that MPI is faster than SPI. The multiplication between matrix and personalized vector is parallel in MPI while which is serial in SPI; (2) The red and blues lines in Figure 2 show that CPAA is faster than MPI. CPAA and MPI are all parallel, but the convergence rate of CPAA is higher; (3) Table 3 shows that CPAA only takes 60% of iteration rounds of power method and is at least 4 times faster than SPI.

V. CONCLUSION AND FUTURE WORK
In this paper, we propose CPAA which is parallel and specially for undirected graph. The experimental results show that CPAA takes less iteration rounds and less CPU time. CPAA is suitable for implementing in the distributed environment, especially in map-reduce framework. Our ongoing work includes approximating the function of eigenvalues by other orthogonal polynomials and extending CPAA to directed graph.