A general multi-splitting iteration method for computing PageRank
- PDF / 773,044 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 68 Downloads / 251 Views
(2019) 38:60
A general multi-splitting iteration method for computing PageRank Maoyi Tian1 · Yan Zhang1 · Yudong Wang2 · Zhaolu Tian3 Received: 13 May 2018 / Revised: 10 November 2018 / Accepted: 1 March 2019 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2019
Abstract In this paper, based on the multi-splitting iteration (MSI) method (Gu and Wang in J Appl Math Comput 42:479–490, 2013), we present a general multi-splitting iteration (GMSI) method for solving the PageRank problem. The convergence of the GMSI method is analyzed in detail. Moreover, the same idea can be used as a preconditioning technique to accelerate Krylov subspace methods, such as the GMRES method. Finally, several numerical examples are given to illustrate the effectiveness of the proposed algorithm. Keywords PageRank vector · Inner–outer iteration · Convergence · Matrix splitting · Preconditioning Mathematics Subject Classification 65F08 · 65F10
1 Introduction With the booming advance of the Internet and its technology, Google’s PageRank has become the most important algorithm to determine the importance of Web pages according to the link structure of the Web. The PageRank algorithm, as the key technology of Google, has attracted much attention in the scientific community in the last decades. At first, we introduce the mathematical background of the PageRank problem; for more details, readers can refer to Page et al. (1998) and Langville and Meyer (2006). As a matter of fact, the link structure of Web pages can be viewed as a direct graph K, each of the n pages is a node, and we have an edge for node i to node j when there is a link from node i to node
Communicated by Jinyun Yuan.
B
Zhaolu Tian [email protected]
1
Geomatics College, Shandong University of Science and Technology, Qingdao 266590, People’s Republic of China
2
College of Textile Engineering, Taiyuan University of Technology, Taiyuan 030024, People’s Republic of China
3
College of Applied Mathematics, Shanxi University of Finance and Economics, Taiyuan 030006, People’s Republic of China
123
60
Page 2 of 29
M. Tian et al.
j. The nonnegative link matrix P˜ ∈ R n×n is expressed as 1 , i → j, P˜i j = n i 0, otherwise, where the scalar n i is the number of outlinks of page i, and i → j represents page i can link to page j. These pages are called dangling nodes (Ipsen and Selee 2007) if they have no outlinks to other pages. Let d be the n-dimensional column vector and 1, if n i = 0, di = 0, otherwise, which identifies the nodes with outdegree 0. Define an n-dimensional column vector 1 , v= n n×1 which represents a uniform probability distribution over all n nodes. Then we get the following row stochastic matrix Pˆ given by Pˆ = P˜ + dv T , where v T is the transpose of v. Due to the ergodic theorem (Grimmett and Stirzaker 2001), it is clear that the stationary distribution of the Markov chain is unique and is the limiting distribution starting from any initial distribution when the transition matrix is aperiodic and irreducible. For th
Data Loading...
