A Note on a Minimal Irreducible Adjustment Pagerank

Abstract

The stochastic modification and irreducible modification in PageRank produce large web link changes correspondingly. To get a minimal irreducible web link adjustment, a PageRank model of minimal irreducible adjustment and its lumping method are discussed by Li, Chen, and Song. In this paper, we provide alternative proofs for the minimal irreducible PageRank by a new type of similarity transformation matrices. To further provide theorems and fast algorithms on a reduced matrix, an $4\times 4$ block matrix partition case of the minimal irreducible PageRank model is utilized and analyzed. For some real applications of our results, a lumping algorithm used for speeding up PageRank vector computations is also presented. Numerical results are also reported to show the efficiency of the proposed algorithm.

1. Introduction

In modern Internet search engine and web information retrieval domains, a good ranking method is extremely important due to the fact that it reveals the relative importance of the corresponding web page. As one of the Markov chain applications in web information retrieval, PageRank is such a famous web ranking method. It assumes that the importance of a web page mainly depends on the relative importance of the pages linking to it [1]. In matrix expression, the iterative procedure of the raw PageRank computation is defined by

$$\begin{array}{c}\hfill {\pi }^{(k+1)T}={\pi }^{\left(k\right)T}H,\mathrm{where}H\in {\mathbb{R}}^{n\times n},{\pi }^{\left(k\right)}\ge 0,{\pi }^{\left(k\right)T}e=1,k=0,1,2,\cdots ,\end{array}$$

(1)

where the matrix $H\in {\mathbb{R}}^{n\times n}$ models the web link structure matrix, ${\pi }^{\left(k\right)}$, $k=0,1,2,\cdots$ is an iterative vector whose entries represent the importance or weight of each page [2,3]. The web link structure matrix H is given by

$$h_{ij}=\left\{\begin{array}{c}{\displaystyle \frac{1}{n_i}},\mathrm{if} \mathrm{page} i \mathrm{links} \mathrm{to} \mathrm{page} j,\hfill \\ 0,\mathrm{otherwise},\hfill \end{array}\right.$$

where $n_i$, $i=1,2,\cdots ,n$ stands for the number of outlinks of page i. As (1) can not insure the uniqueness of the PageRank vector, Page and Brin design an $n\times n$ matrix by two rank-1 modification procedures [1]

$$G=\alpha S+(1-\alpha )e{v}^T,\mathrm{where}S=H+d{w}^T,\mathrm{the} \mathrm{damping} \mathrm{factor}\alpha \in (0,1),$$

(2)

where the nonnegative vector of unit length $w\in {\mathbb{R}}^n$ is the dangling node vector, $e\in {\mathbb{R}}^n$ is a vector of all ones, the nonnegative vector v ($v\in {\mathbb{R}}^n$, ${\parallel v\parallel }_1=1$) is a personalization vector, and the entries of the dangling node indicator vector d are given by

$$d_i=\left\{\begin{array}{c}1,\mathrm{if} \mathrm{page} i \mathrm{does} \mathrm{not} \mathrm{link} \mathrm{to} \mathrm{other} \mathrm{pages},\hfill \\ 0,\mathrm{otherwise}.\hfill \end{array}\right.$$

As we know, some web pages may not have links to other web pages. If web pages have no outlinks, they are called dangling nodes; otherwise, they are called nondangling nodes, such as videos, jpg files, or pdf files are common dangling nodes in web pages. Thus, the above stochastic modification is necessary. The heart of the unique eigenvector is the irreducibility issue; therefore, the matrix $e{v}^T$ (where e and v are defined in (2)) is further used to handle this uniqueness problem. The classical PageRank vector is defined by the principle eigenvector of the Google matrix G with unit 1-norm. It is also to find a stationary probability distribution vector of a Markov chain. In other words, the PageRank computation problem is defined by

$$\begin{array}{c}\hfill {\pi }^{T}G={\pi }^T,G\in {\mathbb{R}}^{n\times n},\pi \ge 0,{\pi }^{T}e=1.\end{array}$$

However, it may take much time merely to compute a large PageRank vector, since hyperlink matrices involved stand for even over a billion pages’ link relationships [1,4]. Hence, faster methods are increasingly heated topics. The Arnoldi method can estimate the first few eigenvalues for nonsymmetric eigenvalue problems, while it may cost expensively in each iteration. The inverse iteration is not suitable for PageRank since it may need $O\left(n^3\right)$ operations by finding an inversion of a large web link matrix. Instead, methods based on the power method are increasingly attractive recently. The damping factor represents the coupling degree of the corresponding Markov chain. A large value of the damping factor stands for a nearly coupled Markov chain. However, as the damping factor increases, the power method converges slowly [3,5,6]. The lumping or reordering method takes full advantage of the zero entries in the Google matrix [2]. Some recent methods for computing PageRank effectively involve Chebyshev polynomial techniques, matrix splitting methods [7,8], the lumping method [9,10], coupled iteration algorithm [11], Hessenberg-type method [12], a simpler GMRES accelerated by Chebyshev polynomials [13], and hybrid methods [14]. Other accelerated methods, theoretical and numerical results are available, see [7,15,16]. Adding dangling nodes’ links to other web sites will change links between web pages maximally. If the number of web pages expands, there will be more dangling node web pages. In addition, every node can be directly connected to other nodes by adding the matrix $e{v}^T$; hence, in this case, irreducibility is enforced trivially. In addition, the web link change is increasingly large, so the adjustment (2) is called maximal irreducible adjustment. For more details of the PageRank model and computation, see [1,2,3,17].

Our recent work provides relatively easy alternative proofs for classical PageRank theoretical analyses by a class of new similarity matrices [18,19]. One may wonder whether the minimal irreducible PageRank model still has similar theoretical results. To further reduce the computational overhead, we discuss a level 4 partition of the minimal irreducible PageRank model matrix. In the level 4 partition of the minimal irreducible Google matrix, we provide a smaller lumping matrix and take full advantage of zero entries in the minimal irreducible Google matrix.

The remainder of this paper is as follows: Section 2 discusses the main theorems of the minimal irreducible PageRank model in [20]. Section 3 presents a class of new similarity matrices which can be used in theoretical analysis. Section 4 provides alternative proofs for the main results due to Li, Chen, and Song [20]. Section 5 discusses the $4\times 4$ level case, and one can derive a solution vector expression by further partitioning the minimal irreducible Google matrix. Hence, the matrix computation dimension involved is reduced and the corresponding computation process can speed up. Finally, Section 6 gives some conclusions of this paper. Throughout the paper, we first revisit the theoretical results of Li, Chen, and Song on a minimal irreducible PageRank model [20]. In addition, Matlab notation is used if necessary.

2. Some Theoretical Results on a Minimal Irreducible PageRank Model

In this section, we focus on underlying theoretical and computational contributions on a kind of minimal irreducible PageRank by the lumping method. Hence, a minimal irreducible PageRank model is discussed below.

2.1. A Minimal Irreducible PageRank Model

If all dangling nodes are lumped into a single node, then the Google matrix is said to be lumpable [9,21]. In general, the matrix M is lumpable with respect to the partition if

$$\begin{array}{c}\hfill M_{ij}e=\mu e,\mathrm{where} \mathrm{the} \mathrm{scalar}\mu \ne 0,e={\left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]}^T,\end{array}$$

where $i\ne j$, $1\le i,j\le k+1$, and the matrix

$$\begin{array}{c}\hfill PM{P}^T=\left[\begin{array}{ccc}{M}_{11}& \cdots & M_{1,k+1}\\ ⋮& \ddots & ⋮\\ M_{k+1,1}& \cdots & M_{k+1,k+1}\end{array}\right],\end{array}$$

and P is a proper permutation matrix.

Suppose that $H\in {\mathbb{R}}^{n\times n}$ has k nondangling nodes and $n-k$ dangling nodes, thus there exists a permutation matrix $\mathsf{\Pi }\in {\mathbb{R}}^{n\times n}$, such that

$$\mathsf{\Pi }H{\mathsf{\Pi }}^T=\left[\begin{array}{cc}{H}_{11}& H_{12}\\ 0& 0\end{array}\right].$$

Hence,

$$\begin{array}{cc}\hfill A=\mathsf{\Pi }G{\mathsf{\Pi }}^T=& \alpha \overline{S}+(1-\alpha )e{v}^T\hfill \\ \hfill =& \alpha \left[\begin{array}{cc}{H}_{11}& H_{12}\\ e{w}_1^T& e{w}_2^T\end{array}\right]+\left(1-\alpha \right)\left[\begin{array}{cc}e{v}_1^T& e{v}_2^T\\ e{v}_1^T& e{v}_2^T\end{array}\right]\hfill \\ \hfill =& \left[\begin{array}{cc}\alpha H_{11}+(1-\alpha )e{v}_1^T& \alpha H_{12}+(1-\alpha )e{v}_2^T\\ e(\alpha w_1^T+(1-\alpha )v_1^T)& e(\alpha w_2^T+(1-\alpha )v_2^T)\end{array}\right]\hfill \\ \hfill =& \left[\begin{array}{cc}{A}_{11}& A_{12}\\ e{u}_1^T& e{u}_2^T\end{array}\right],\mathrm{where}\overline{S}=\mathsf{\Pi }S{\mathsf{\Pi }}^T,\hfill \end{array}$$

(3)

where the dangling node vector w and personalization vector v are partitioned into $w_1\in {\mathbb{R}}^k$, $w_2\in {\mathbb{R}}^{n-k}$ and $v_1\in {\mathbb{R}}^k$, $v_2\in {\mathbb{R}}^{n-k}$. Moreover, if

$$\begin{array}{c}\hfill {\overline{\pi }}^T={\overline{\pi }}^{T}A={\overline{\pi }}^T\mathsf{\Pi }G{\mathsf{\Pi }}^T,\mathrm{with}\overline{\pi }\ge 0,{\parallel \overline{\pi }\parallel }_1=1,\end{array}$$

(4)

where $A=\mathsf{\Pi }G{\mathsf{\Pi }}^T$, $G\in {\mathbb{R}}^{n\times n}$ is the classical Google matrix, and $\overline{\pi }$ is the stationary distribution of A, then the PageRank vector corresponding to (4) is defined by

$${\pi }^T={\overline{\pi }}^T\mathsf{\Pi }.$$

In [20], Li, Chen, and Song discussed a minimal irreducible Google matrix by changing $\overline{S}$ to a bordered matrix

$$\begin{array}{c}\hfill \tilde{S}=\left[\begin{array}{cc}\frac{n}{n+1}\overline{S}& \frac{1}{n+1}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}\end{array}\right]=\left[\begin{array}{ccc}\frac{n}{n+1}{H}_{11}& \frac{n}{n+1}{H}_{12}& \frac{1}{n+1}e\\ \frac{n}{n+1}e{w}_1^T& \frac{n}{n+1}e{w}_2^T& \frac{1}{n+1}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}\end{array}\right].\end{array}$$

(5)

The new PageRank vector of order $n+1$ is the solution vector defined by the principle eigenvector of the new Google matrix $\tilde{S}$,

$${\tilde{\pi }}^T={\tilde{\pi }}^T\tilde{S},\mathrm{or}\tilde{\pi }={\tilde{S}}^T\tilde{\pi },\mathrm{with}\tilde{\pi }\ge 0,{\parallel \tilde{\pi }\parallel }_1=1.$$

We note that this modification only increases one additional row and column to ensure that the link matrix is strongly connected, in order to ensure that the new Google matrix $\tilde{S}$ is irreducible. In this way, the Perron–Frobenius theorem can guarantee the uniqueness of a positive principle eigenvector $\tilde{\pi }$ with unit length ($\parallel \tilde{\pi }{\parallel }_1=1$). Note that the decomposition presented in (5) has been studied before in various forms. See, e.g., [22,23]. In Section 4.3, we mainly studied the first two layers of such decompositions. In addition, another way of creating a minimal irreducible Google matrix is defined by [24,25]

$$\begin{array}{c}\hfill {\tilde{S}}^{\prime }=\left[\begin{array}{cc}\alpha \overline{S}& (1-\alpha )e\\ v^T& 0\end{array}\right]=\left[\begin{array}{ccc}\alpha H_{11}& \alpha H_{12}& (1-\alpha )e\\ \alpha e{w}_1^T& \alpha e{w}_2^T& (1-\alpha )e\\ v^T& v^T& 0\end{array}\right].\end{array}$$

(6)

In this paper, we mainly discuss the minimal irreducible Google matrix (5). In addition, we will briefly discuss our results on (6) and leave it as a further question.

In the following, in order to lump the stochastic matrix and show our theoretical results conveniently, we first permutate the rows and columns of $\tilde{S}$ simultaneously. Thus, we first permutate $\tilde{S}$, such that

$$\begin{array}{c}\hfill \widehat{S}=\tilde{\mathsf{\Pi }}\tilde{S}{\tilde{\mathsf{\Pi }}}^T=\left[\begin{array}{ccc}\frac{n}{n+1}{H}_{11}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{1}{n+1}{e}^T\\ \frac{n}{n+1}e{w}_1^T& \frac{1}{n+1}e& \frac{n}{n+1}e{w}_2^T\end{array}\right],\end{array}$$

where the corresponding permutation matrix

$$\begin{array}{c}\hfill \tilde{\mathsf{\Pi }}=\left[\begin{array}{ccc}{I}_k& 0& 0\\ 0& 0& 1\\ 0& I_{n-k}& 0\end{array}\right].\end{array}$$

2.2. Some Related Theorems on the Minimal Irreducible PageRank Model

The similarity transformation matrix

$$\begin{array}{c}\hfill L=I_{n-k}-\frac{1}{n-k}\widehat{e}{e}^T,\mathrm{where}\widehat{e}=e-e_1={\left[\begin{array}{c}0,1,\cdots ,1\end{array}\right]}^T\in {\mathbb{R}}^{n-k}\end{array}$$

is employed by Ipsen and Selee to analyze the theoretical results, and the identity matrix of order n is denoted by $I_n=\left[\begin{array}{cccc}{e}_1& e_2& \cdots & e_n\end{array}\right],$ where $e_i$, $i=1,2,\cdots ,n$ is the ith column vector of $I_n$. If large scale computation problems can be reduced to a relatively small scale, the computations can be simplified and accelerated. Fortunately, lumping is one of these methods. In [20], Li, Chen, and Song obtained the following theorems for the new Google matrix. They showed that the minimal irreducible Google matrix can also be lumped. In addition, the spectral distribution of the new Google matrix, the relationship between the eigenvector part associated with the dangling nodes, and the eigenvector part associated with the nondangling nodes is as follows.

Theorem 1

([20,26]). Given the stochastic matrix $\overline{S}$ with spectrum $\left\{1,{\lambda }_2,{\lambda }_3,\cdots ,{\lambda }_n\right\}$. Then, the spectral of the matrix

$$\tilde{S}=\left[\begin{array}{cc}\frac{n}{n+1}\overline{S}& \frac{1}{n+1}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}\end{array}\right]$$

is $\left\{1,\frac{n}{n+1}{\lambda }_2,\frac{n}{n+1}{\lambda }_3,\cdots ,\frac{n}{n+1}{\lambda }_n,0\right\}.$

Theorem 2

([20]). With the above notation, let

$$X=\left[\begin{array}{ccc}{I}_k& 0& 0\\ 0& 1& 0\\ 0& 0& L\end{array}\right],whereL=I_{n-k}-\frac{1}{n-k}\widehat{e}{e}^{T}and\widehat{e}=e-e_1={\left[\begin{array}{cccc}0& 1& \cdots & 1\end{array}\right]}^T.$$

Then,

$$\begin{array}{c}\hfill X\widehat{S}{X}^{-1}=\left[\begin{array}{cc}{\widehat{S}}^{\left(1\right)}& {\widehat{S}}^{\left(2\right)}\\ 0& 0\end{array}\right],where{\widehat{S}}^{\left(1\right)}=\left[\begin{array}{ccc}\frac{n}{n+1}{H}_{11}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{n-k}{n+1}\\ \frac{n}{n+1}{w}_1^T& \frac{1}{n+1}& \frac{n}{n+1}{w}_2^{T}e\end{array}\right],\end{array}$$

so that $\widehat{S}$ has at least $n-k-1$ zero eigenvalues.

Theorem 3

([20]). With the above notation, let

$$\begin{array}{c}\hfill {\sigma }^T\left[\begin{array}{ccc}\frac{n}{n+1}{H}_{11}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{n-k}{n+1}\\ \frac{n}{n+1}{w}_1^T& \frac{1}{n+1}& \frac{n}{n+1}{w}_2^{T}e\end{array}\right]={\sigma }^T,\sigma \in {\mathbb{R}}^{k+2}\ge 0,{\parallel \sigma \parallel }_1=1,\end{array}$$

and partition ${\sigma }^T=\left[\begin{array}{ccc}{\sigma }_{1:k}^T& {\sigma }_{k+1}& {\sigma }_{k+2}\end{array}\right]$, where ${\sigma }_{k+1}$ and ${\sigma }_{k+2}$ are scalars. Then, the PageRank vector of $\tilde{S}$ equals

$${\tilde{\pi }}^T=\left[\begin{array}{ccc}{\sigma }_{1:k}^T& {\sigma }^T\left[\begin{array}{c}\frac{n}{n+1}{H}_{12}\\ \frac{1}{n+1}{e}^T\\ \frac{n}{n+1}{w}_2^T\end{array}\right]& {\sigma }_{k+1}\end{array}\right].$$

3. New Similarity Transformation Matrix

In order to further study the lumping method and make contribution to the PageRank computation, we derive alternative proofs for related theorems by using new similarity transformation matrices [18,19] and try to establish efficient algorithms to compute PageRank. To discuss this topic, we begin to introduce some related work.

Suppose that ${\lambda }_i$ is the eigenvalues of $A\in {\mathbb{R}}^{n\times n}$ ordered as $|{\lambda }_1|>|{\lambda }_2|\ge |{\lambda }_3|\ge \cdots \ge |{\lambda }_n|\ge 0$. In [27], Ding and Zhou proposed the following rank-1 updated spectral theorem.

Theorem 4

([27]). Let u and v be two $n-$ dimensional column vectors such that u is an eigenvector of A associated with the eigenvalue ${\lambda }_1$. Then, the eigenvalues of $A+u{v}^T$ are $\left\{{\lambda }_1+v^{T}u,{\lambda }_2,\cdots ,{\lambda }_n\right\}$, counting algebraic multiplicity.

Langville and Meyer in their book [3] analyze the spectral distribution of the classical Google matrix by employing a similarity transformation method. To find the relationship between PageRank of the nondangling nodes ${\pi }_1$ and that of dangling nodes ${\pi }_2$, Ipsen and Selee in [9] employed the similarity transformation matrix

$$\begin{array}{c}\hfill X=\left[\begin{array}{cc}{I}_k& 0\\ 0& L\end{array}\right],L=I_{n-k}-\frac{1}{n-k}\widehat{e}{e}^T,\widehat{e}=e-e_1={\left[\begin{array}{cccc}0& 1& \cdots & 1\end{array}\right]}^T.\end{array}$$

(7)

As it is pointed in [18], the invertible matrix L exists such that the related theorem holds. However, the matrix L is not unique. In the general case of the Google matrix, if the matrix L satisfies the condition

$$\begin{array}{c}\hfill Le=e_1,\mathrm{where} e \mathrm{is} a \mathrm{vector} \mathrm{of} \mathrm{all} \mathrm{ones},\end{array}$$

(8)

then the proof process can be more simpler and shortened. Motivated by the above conclusion, we further study the case in the new PageRank model. In Theorem 2, if we exploit the matrix [18]    

$$\begin{array}{c}\hfill \tilde{X}=\left[\begin{array}{cc}{I}_k& 0\\ 0& \tilde{L}\end{array}\right],\mathrm{where}\tilde{L}=I_{n-k}-\widehat{e}{e}_1^T,\widehat{e}=e-e_1={\left[\begin{array}{cccc}0& 1& \cdots & 1\end{array}\right]}^T,\end{array}$$

(9)

and we separate the first row and column of $\tilde{L}$

$$\begin{array}{c}\hfill \tilde{L}=\left[\begin{array}{cc}1& 0\\ -e& I_{n-k-1}\end{array}\right],\end{array}$$

(10)

and partition L in (7) conformally with $\tilde{L}$,

$$\begin{array}{c}\hfill L=\left[\begin{array}{cc}1& 0\\ -\frac{1}{n-k}e& I_{n-k-1}-\frac{1}{n-k}e{e}^T\end{array}\right],\end{array}$$

(11)

where the 2-by-2 block of L in (11) is

$$I_{n-k-1}-\frac{1}{n-k}e{e}^T=\left[\begin{array}{cccc}\frac{n-k-1}{n-k}& \frac{-1}{n-k}& \cdots & \frac{-1}{n-k}\\ \frac{-1}{n-k}& \frac{n-k-1}{n-k}& \cdots & \frac{-1}{n-k}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{-1}{n-k}& \frac{-1}{n-k}& \cdots & \frac{n-k-1}{n-k}\end{array}\right].$$

Unfortunately, it is a typical dense matrix; therefore, it is complex when we analyze it, and it is expensive when we compute or store it. Furthermore, the matrix (10) is actually [18]

$$\tilde{L}=\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ -1& 1& 0& \cdots & 0\\ -1& 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & \ddots & ⋮\\ -1& 0& \cdots & 0& 1\end{array}\right].$$

because $\tilde{L}$ is a triangular matrix while L is a dense matrix. Inspired and motivated by the easier similarity transformation matrix $\tilde{L}$, we consider replacing L with $\tilde{L}$ in X so that an alternative proof process can be presented, and its process can be simplified and shortened. Moreover, if

$$\tilde{L}=\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ -1& 1& 0& \cdots & 0\\ 0& -1& 1& \cdots & 0\\ ⋮& ⋮& \ddots & \ddots & ⋮\\ 0& 0& \cdots & -1& 1\end{array}\right]$$

in (9), then the proof process of the above theorems also holds. In other words, this similarity transformation matrix is not unique at all. Instead of the matrix L used in [9], we propose a class of invertible matrices $\widehat{L}$, which satisfy the condition (8). Particularly, if $\widehat{L}=L$, it becomes the similarity transformation matrix proposed by Ipsen and Selee in [9]. In the following, as we mainly discuss the minimal irreducible PageRank matrix (5), one may wonder “Could you apply your methods on the results in [24,25]?” Thus, we provide a remark below.

Remark 1.

If we permutate ${\tilde{S}}^{\prime }$ by the permutation matrix $\tilde{\mathsf{\Pi }}$, such that ${\tilde{S}}^{\prime }$ is reordered as

$$\left[\begin{array}{ccc}\alpha H_{11}& (1-\alpha )e& \alpha H_{12}\\ v_1^T& 0& v_2^T\\ \alpha e{w}_1^T& (1-\alpha )e& \alpha e{w}_2^T\end{array}\right].$$

Performing a similarity transformation on it, we yield

$$\begin{array}{cc}\hfill \left[\begin{array}{ccc}I& 0& 0\\ 0& 1& 0\\ 0& 0& L\end{array}\right]& \left[\begin{array}{ccc}\alpha H_{11}& (1-\alpha )e& \alpha H_{12}\\ v_1^T& 0& v_2^T\\ \alpha e{w}_1^T& (1-\alpha )e& \alpha e{w}_2^T\end{array}\right]\left[\begin{array}{ccc}I& 0& 0\\ 0& 1& 0\\ 0& 0& L^{-1}\end{array}\right]\hfill \\ \hfill =& \left[\begin{array}{ccc}\alpha H_{11}& (1-\alpha )e& \alpha H_{12}{L}^{-1}\\ v_1^T& 0& v_2^t{L}^{-1}\\ \alpha Le{w}_1^T& (1-\alpha )Le& \alpha Le{w}_2^T{L}^{-1}\end{array}\right]\hfill \\ \hfill =& \left[\begin{array}{cccc}\alpha H_{11}& (1-\alpha )e& \alpha H_{12}{L}^{-1}{e}_1& \alpha H_{12}{L}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ v_1^T& 0& v_2^T{L}^{-1}{e}_1& v_2^T{L}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ \alpha w_1^T& (1-\alpha )& \alpha w_2^T{L}^{-1}{e}_1& \alpha w_2^T{L}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ 0& 0& 0& 0\end{array}\right],\hfill \end{array}$$

where the invertible matrix L satisfies $Le=e_1$, $e_1=\left[\begin{array}{cccc}1& 0& \cdots & 0\end{array}\right]$, and e is a column vector of all ones. Therefore, we preliminarily judge that the new similarity matrix results and theoretical results are also suitable for this form of minimal irreducibility Google matrix. More detailed work is under consideration.

4. Alternative Proofs

In this section, we will analyze theoretical results of the minimal irreducible PageRank model based on the similarity transformation matrix (9). Here, we mainly provide alternative proofs for the minimal irreducible PageRank model.

4.1. An Alternative Proof of Theorem 1

In [20], Li, Chen, and Song completed the proof of Theorem 1 by using the determinant property: That is,

$$\begin{array}{c}\hfill det\left(\left[\begin{array}{cc}\frac{n}{n+1}\overline{S}& \frac{1}{n+1}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}\end{array}\right]-\lambda I_{n+1}\right)=\lambda \left(\lambda -1\right)\left(\frac{n}{n+1}{\lambda }_2-\lambda \right)\cdots \left(\frac{n}{n+1}{\lambda }_n-\lambda \right),\end{array}$$

Thus, one can conclude that the eigenvalues of $\tilde{S}$ is $\{1,\frac{n}{n+1}{\lambda }_2,\cdots ,\frac{n}{n+1}{\lambda }_n,0\}$. Here, we show an alternative proof for Theorem 1 by using the similarity transformation matrix.

Proof. 

A similarity transformation is done as follows:

$$\begin{array}{cc}\hfill \left[\begin{array}{cc}I& \frac{1}{n}e\\ 0& 1\end{array}\right]\tilde{S}\left[\begin{array}{cc}I& -\frac{1}{n}e\\ 0& 1\end{array}\right]=& \left[\begin{array}{cc}I& \frac{1}{n}e\\ 0& 1\end{array}\right]\left[\begin{array}{cc}\frac{n}{n+1}\overline{S}& \frac{1}{n+1}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}\end{array}\right]\left[\begin{array}{cc}I& -\frac{1}{n}e\\ 0& 1\end{array}\right]\hfill \\ \hfill =& \left[\begin{array}{cc}\frac{n}{n+1}\overline{S}+\frac{1}{n(n+1)}e{e}^T& 0\\ \frac{1}{n+1}{e}^T& 0\end{array}\right].\hfill \end{array}$$

The eigenvalues of the stochastic matrix $\overline{S}$ are denoted by $\left\{1,{\lambda }_2,{\lambda }_3,\cdots ,{\lambda }_n\right\}$. By Theorem 4, we obtain that the eigenvalues of $\tilde{S}$ are

$$\frac{1}{n+1}\left(n+\frac{1}{n}·n\right)=1,\frac{n}{n+1}{\lambda }_2,\frac{n}{n+1}{\lambda }_3,\cdots ,\frac{n}{n+1}{\lambda }_n,$$

and the remaining eigenvalue is 0. Thus, we complete the proof.    □

4.2. An Alternative Proof of Theorem 2

Li, Chen, and Song [20] present the proof of Theorem 2 by using the similarity transformation matrix (7). Now, we validate Theorem 2 by a general invertible matrix $\widehat{L}$ satisfying $\widehat{L}e=e_1$ below.

Proof. 

Since

$$\begin{array}{c}\hfill {\tilde{X}}^{-1}=\left[\begin{array}{ccc}{I}_k& 0& 0\\ 0& 1& 0\\ 0& 0& {\tilde{L}}^{-1}\end{array}\right],\mathrm{where}\tilde{L}=I_{n-k}-\widehat{e}{e}_1^T\mathrm{and}{\tilde{L}}^{-1}=I_{n-k}+\widehat{e}{e}_1^T,\end{array}$$

then

$$\begin{array}{cc}\hfill \tilde{X}\widehat{S}{\tilde{X}}^{-1}=& \left[\begin{array}{ccc}\frac{n}{n+1}{H}_{11}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}{\tilde{L}}^{-1}\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{1}{n+1}{e}^T{\tilde{L}}^{-1}\\ \frac{n}{n+1}\tilde{L}e{w}_1^T& \frac{1}{n+1}\tilde{L}e& \frac{n}{n+1}\tilde{L}e{w}_2^T{\tilde{L}}^{-1}\end{array}\right]\hfill \\ \hfill =& \left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}{\tilde{L}}^{-1}{e}_1& \frac{n}{n+1}{H}_{12}{\tilde{L}}^{-1}\left[\begin{array}{cccc}{e}_2& e_3& \cdots & e_{n-k}\end{array}\right]\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{1}{n+1}{e}^T{\tilde{L}}^{-1}{e}_1& \frac{1}{n+1}{e}^T{\tilde{L}}^{-1}\left[\begin{array}{cccc}{e}_2& e_3& \cdots & e_{n-k}\end{array}\right]\\ \frac{n}{n+1}{e}_1^T\tilde{L}e{w}_1^T& \frac{1}{n+1}{e}_1^T\tilde{L}e& \frac{n}{n+1}{e}_1^T\tilde{L}e{w}_2^T{\tilde{L}}^{-1}{e}_1& \frac{n}{n+1}{e}_1^T\tilde{L}e{w}_2^T{\tilde{L}}^{-1}\left[\begin{array}{cccc}{e}_2& e_3& \cdots & e_{n-k}\end{array}\right]\\ 0& 0& 0& 0\end{array}\right]\hfill \\ \hfill =& \left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}e& \frac{n}{n+1}{H}_{12}{\tilde{L}}^{-1}\left[\begin{array}{cccc}{e}_2& e_3& \cdots & e_{n-k}\end{array}\right]\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{n-k}{n+1}& \frac{1}{n+1}{e}^T{\tilde{L}}^{-1}\left[\begin{array}{cccc}{e}_2& e_3& \cdots & e_{n-k}\end{array}\right]\\ \frac{n}{n+1}{w}_1^T& \frac{1}{n+1}& \frac{n}{n+1}{w}_2^{T}e& \frac{n}{n+1}{w}_2^T{\tilde{L}}^{-1}\left[\begin{array}{cccc}{e}_2& e_3& \cdots & e_{n-k}\end{array}\right]\\ 0& 0& 0& 0\end{array}\right],\hfill \end{array}$$

where $e={\left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]}^T\in {\mathbb{R}}^{n-k}$, $e^{T}e=n-k$, ${\tilde{L}}^{-1}{e}_1=e$, and the last quality follows form $\tilde{L}e=e_1$ (thus, $e_1^T\tilde{L}e=1$).    □

Remark 2.

During the above proof of Theorem 2, if $\tilde{X}$ is generalized to

$$\begin{array}{c}\hfill {\widehat{X}}^{}=\left[\begin{array}{ccc}{I}_k& 0& 0\\ 0& 1& 0\\ 0& 0& {\widehat{L}}^{}\end{array}\right],\mathit{where}\mathit{an}\mathit{invertible}\mathit{matrix}\widehat{L}\mathit{satisfies}\widehat{L}e=e,\end{array}$$

the proof also holds.

4.3. An Alternative Proof of Theorem 3

In this alternative proof, the similarity matrix is chosen as ${\widehat{X}}^{}$. A general invertible matrix $\widehat{L}$ satisfying $\widehat{L}e=e_1$ is applied to validate Theorem 3.

Proof. 

If

$$\begin{array}{c}\hfill \widehat{X}\widehat{S}{\widehat{X}}^{-1}=\left[\begin{array}{cc}{\widehat{S}}^{\left(1\right)}& {\widehat{S}}^{\left(2\right)}\\ 0& 0\end{array}\right],\mathrm{where}{\widehat{S}}^{\left(1\right)}=\left[\begin{array}{ccc}\frac{n}{n+1}{H}_{11}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{n-k}{n+1}\\ \frac{n}{n+1}{w}_1^T& \frac{1}{n+1}& \frac{n}{n+1}{w}_2^{T}e\end{array}\right],\end{array}$$

then the stochastic matrix ${\widehat{S}}^{\left(1\right)}$ of order $k+2$ has the same nonzero eigenvalues as $\widehat{S}$. We obtain that

$$\left[{\sigma }^T\right.\left.{\sigma }^T{\widehat{S}}^{\left(2\right)}\right]$$

is an eigenvector for $\widehat{X}\widehat{S}{\widehat{X}}^{-1}$ associated with the eigenvalue $\lambda =1$. This follows from

$$\begin{array}{c}\hfill \left[\begin{array}{cc}{\sigma }^T& {\sigma }^T{\widehat{S}}^{\left(2\right)}\end{array}\right]\left[\begin{array}{cc}{\widehat{S}}^{\left(1\right)}& {\widehat{S}}^{\left(2\right)}\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}{\sigma }^T{\widehat{S}}^{\left(1\right)}& {\sigma }^T{\widehat{S}}^{\left(2\right)}\end{array}\right]=\left[\begin{array}{cc}{\sigma }^T& {\sigma }^T{\widehat{S}}^{\left(2\right)}\end{array}\right].\end{array}$$

Therefore,

$$\begin{array}{c}\hfill {\widehat{\pi }}^T=\left[\begin{array}{cc}{\sigma }^T& {\sigma }^T{\widehat{S}}^{\left(2\right)}\end{array}\right]\widehat{X}\end{array}$$

is an eigenvector of $\widehat{S}$ associated with $\lambda =1$. Since $\widehat{S}$ and ${\widehat{S}}^{\left(1\right)}$ have the same nonzero eigenvalues, and the principle eigenvalue of S or $\widehat{S}$ is distinct, the stationary probability distribution $\sigma$ of ${\widehat{S}}^{\left(1\right)}$ is unique. We repartition

$$\begin{array}{c}\hfill {\widehat{\pi }}^T=\left[\begin{array}{ccc}{\sigma }_{1:k}^T& {\sigma }_{k+1}& \left[\begin{array}{cc}{\sigma }_{k+2}& {\sigma }^T{\widehat{S}}^{\left(2\right)}\end{array}\right]\end{array}\right]\left[\begin{array}{ccc}{I}_k& 0& 0\\ 0& 1& 0\\ 0& 0& \widehat{L}\end{array}\right].\end{array}$$

Multiplying out

$$\begin{array}{c}\hfill {\widehat{\pi }}^T=\left[\begin{array}{ccc}{\sigma }_{1:k}^T& {\sigma }_{k+1}& \left[\begin{array}{cc}{\sigma }_{k+2}& {\sigma }^T{\widehat{S}}^{\left(2\right)}\end{array}\right]\widehat{L}\end{array}\right].\end{array}$$

Since

$$\begin{array}{cc}\hfill \left[\begin{array}{cc}{\sigma }_{k+2}& {\sigma }^T{\widehat{S}}^{\left(2\right)}\end{array}\right]\widehat{L}& =\left[\begin{array}{cc}{\sigma }^T{\widehat{s}}^{\left(1\right)}e& {\sigma }^T{\widehat{s}}^{\left(1\right)}{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\end{array}\right]\widehat{L}\hfill \\ \hfill & =\left[\begin{array}{cc}{\sigma }^T{\widehat{s}}^{\left(1\right)}{\widehat{L}}^{-1}{e}_1& {\sigma }^T{\widehat{s}}^{\left(1\right)}{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\end{array}\right]\widehat{L}\hfill \\ \hfill & ={\sigma }^T{\widehat{s}}^{\left(1\right)},\hfill \end{array}$$

the first equation uses the fact that

$$\begin{array}{c}\hfill {\widehat{s}}^{\left(1\right)}={\left[\begin{array}{ccc}\frac{n}{n+1}{H}_{12}^T& \frac{1}{n+1}e& \frac{n}{n+1}{w}_2\end{array}\right]}^T,{\sigma }_{k+2}={\sigma }^T{\widehat{s}}^{\left(1\right)}e\mathrm{and}{\widehat{S}}^{\left(2\right)}={\widehat{s}}^{\left(1\right)}{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right],\end{array}$$

and the second equation uses $e={\widehat{L}}^{-1}{e}_1$. Hence,

$${\widehat{\pi }}^T=\left[\begin{array}{ccc}{\sigma }_{1:k}^T& {\sigma }_{k+1}& {\sigma }^T{\widehat{s}}^{\left(1\right)}\end{array}\right].$$

Furthermore,

$$\begin{array}{c}\hfill {\tilde{\pi }}^T={\widehat{\pi }}^T\tilde{\mathsf{\Pi }}=\left[\begin{array}{ccc}{\sigma }_{1:k}^T& {\sigma }^T{\widehat{s}}^{\left(1\right)}& {\sigma }_{k+1}\end{array}\right],\mathrm{with}{\widehat{s}}^{\left(1\right)}={\left[\begin{array}{ccc}\frac{n}{n+1}{H}_{12}^T& \frac{1}{n+1}e& \frac{n}{n+1}{w}_2\end{array}\right]}^T.\end{array}$$

As the claim $\tilde{\pi }$ is unique, we conclude that $\tilde{\pi }$ is the stationary probability of the PageRank model if $e^T\tilde{\pi }=1.$ Therefore, we complete the proof.    □

5. Results for 4-Level Matrix Partition

We will show that the nondangling nodes can also be further classified into two classes. The nodes which are nondangling but point to only the dangling nodes are further called “weakly nondangling” nodes. The other nondangling nodes are referred to as “strongly nondangling” nodes [10]. Therefore, the reduced matrix obtained by lumping dangling nodes can be further reduced by lumping weakly nondangling nodes, to another single node. In addition, the further reduced matrix is also stochastic with the same nonzero eigenvalues as the Google matrix.

5.1. Derivation

To lump dangling nodes and weakly nondangling nodes [10] to a level 4 matrix partition, we permutate the matrix S in (3) such that

$$\begin{array}{c}\hfill \overline{S}=\mathsf{\Pi }S{\mathsf{\Pi }}^T=\left[\begin{array}{ccc}{H}_{11}^{\left(11\right)}& H_{11}^{\left(12\right)}& H_{12}^{\left(1\right)}\\ 0& 0& H_{12}^{\left(2\right)}\\ e{w}_{k_1}^T& e{w}_{k_2}^T& e{w}_2^T\end{array}\right],\end{array}$$

where $H_{11}^{\left(11\right)}\in {\mathbb{R}}^{k_1\times k_1}$, $H_{11}^{\left(12\right)}\in {\mathbb{R}}^{k_1\times k_2}$, $H_{12}^{\left(1\right)}\in {\mathbb{R}}^{k_1\times (n-k)}$, $H_{12}^{\left(2\right)}\in {\mathbb{R}}^{k_2\times (n-k)}$, $w_2\in {\mathbb{R}}^{n-k}$, $k_1$, and $k_2$ are the number of strongly nondangling nodes and weakly nondangling nodes, respectively. Moveover, $k=k_1+k_2$ and $\overline{S}e=e$. After the adjustment by Li, Chen, and Song [20], the new Google matrix in $4\times 4$ block form is

$$\begin{array}{c}\hfill G=\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{n}{n+1}{H}_{12}^{\left(1\right)}& \frac{1}{n+1}e\\ 0& 0& \frac{n}{n+1}{H}_{12}^{\left(2\right)}& \frac{1}{n+1}e\\ \frac{n}{n+1}e{w}_{k_1}^T& \frac{n}{n+1}e{w}_{k_2}^T& \frac{n}{n+1}e{w}_2^T& \frac{1}{n+1}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}\end{array}\right].\end{array}$$

(12)

We define the permutation matrix

$$\begin{array}{c}\hfill {\mathsf{\Pi }}_1=\left[\begin{array}{cccc}I& 0& 0& 0\\ 0& I& 0& 0\\ 0& 0& 0& 1\\ 0& 0& I& 0\end{array}\right]\end{array}$$

to permutate the third and fourth row and column of G simultaneously. Performing ${\mathsf{\Pi }}_{1}G{\mathsf{\Pi }}_1^T$ yields

$$\begin{array}{c}\hfill {\mathsf{\Pi }}_{1}G{\mathsf{\Pi }}_1^T=\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(1\right)}\\ 0& 0& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(2\right)}\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{1}{n+1}{e}^T\\ \frac{n}{n+1}e{w}_{k_1}^T& \frac{n}{n+1}e{w}_{k_2}^T& \frac{1}{n+1}e& \frac{n}{n+1}e{w}_2^T\end{array}\right].\end{array}$$

Let

$$X=\left[\begin{array}{cccc}{I}_{k_1}& 0& 0& 0\\ 0& I_{k_2}& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& \widehat{L}\end{array}\right],\mathrm{where}\widehat{L}\in {\mathbb{R}}^{(n-k)\times (n-k)}\mathrm{is} \mathrm{an} \mathrm{invertible} \mathrm{matrix} \mathrm{with} \widehat{L}e=e_1,$$

then

$$\begin{array}{cc}\hfill X{\mathsf{\Pi }}_{1}G{\mathsf{\Pi }}_1^T{X}^{-1}& =\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(1\right)}{\widehat{L}}^{-1}\\ 0& 0& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(2\right)}{\widehat{L}}^{-1}\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{1}{n+1}{e}^T{\widehat{L}}^{-1}\\ \frac{n}{n+1}\widehat{L}e{w}_{k_1}^T& \frac{n}{n+1}\widehat{L}e{w}_{k_2}^T& \frac{1}{n+1}\widehat{L}e& \frac{n}{n+1}\widehat{L}e{w}_2^T{\widehat{L}}^{-1}\end{array}\right]\hfill \\ \hfill & =\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(1\right)}{\widehat{L}}^{-1}\\ 0& 0& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(2\right)}{\widehat{L}}^{-1}\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{1}{n+1}{e}^T{\widehat{L}}^{-1}\\ \frac{n}{n+1}{e}_1{w}_{k_1}^T& \frac{n}{n+1}{e}_1{w}_{k_2}^T& \frac{1}{n+1}{e}_1& \frac{n}{n+1}{e}_1{w}_2^T{\widehat{L}}^{-1}\end{array}\right]\hfill \\ \hfill & =\left[\begin{array}{ccccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e& \frac{n}{n+1}{H}_{12}^{\left(1\right)}{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ 0& 0& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(2\right)}e& \frac{n}{n+1}{H}_{12}^{\left(2\right)}{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{n-k}{n+1}& \frac{1}{n+1}{e}^T{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_{k_2}^T& \frac{1}{n+1}& \frac{n}{n+1}{w}_2^{T}e& \frac{n}{n+1}{w}_2^T{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ 0& 0& 0& 0& 0\end{array}\right].\hfill \end{array}$$

Denote by

$$G_1=\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e\\ 0& 0& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(2\right)}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{n-k}{n+1}\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_{k_2}^T& \frac{1}{n+1}& \frac{n}{n+1}{w}_2^{T}e\end{array}\right],$$

and then we permutate the second and fourth block row and column of $G_1$ simultaneously by a permutation matrix ${\mathsf{\Pi }}_2$,

$$\begin{array}{cc}\hfill {\mathsf{\Pi }}_2{G}_1{\mathsf{\Pi }}_2^T=& \left[\begin{array}{cccc}I& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\\ 0& I& 0& 0\end{array}\right]\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e\\ 0& 0& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{12}^{\left(2\right)}e\\ \frac{1}{n+1}{e}^T& \frac{1}{n+1}{e}^T& \frac{1}{n+1}& \frac{n-k}{n+1}\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_{k_2}^T& \frac{1}{n+1}& \frac{n}{n+1}{w}_2^{T}e\end{array}\right]{\left[\begin{array}{cccc}I& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\\ 0& I& 0& 0\end{array}\right]}^T\hfill \\ \hfill =& \left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{11}^{\left(12\right)}\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_2^{T}e& \frac{1}{n+1}& \frac{n}{n+1}{w}_{k_2}^T\\ \frac{1}{n+1}{e}^T& \frac{n-k}{n+1}& \frac{1}{n+1}& \frac{1}{n+1}{e}^T\\ 0& \frac{n}{n+1}{H}_{12}^{\left(2\right)}e& \frac{1}{n+1}e& 0\end{array}\right].\hfill \end{array}$$

Denote by

$$\begin{array}{c}\hfill X_1=\left[\begin{array}{cccc}I& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& \widehat{L}\end{array}\right],\mathrm{where}\widehat{L}\in {\mathbb{R}}^{k_2\times k_2}\mathrm{is} \mathrm{an} \mathrm{invertible} \mathrm{matrix} \mathrm{with} \widehat{L}e=e_1.\end{array}$$

Then,

$$\begin{array}{cc}\hfill & X_1{\mathsf{\Pi }}_2{G}_1{\mathsf{\Pi }}_2^T{X}_1^{-1}=\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{11}^{\left(12\right)}{\widehat{L}}^{-1}\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_2^{T}e& \frac{1}{n+1}& \frac{n}{n+1}{w}_{k_2}^T{\widehat{L}}^{-1}\\ \frac{1}{n+1}{e}^T& \frac{n-k}{n+1}& \frac{1}{n+1}& \frac{1}{n+1}{e}^T{\widehat{L}}^{-1}\\ 0& \frac{n}{n+1}\widehat{L}{H}_{12}^{\left(2\right)}e& \frac{1}{n+1}\widehat{L}e& 0\end{array}\right]\hfill \\ \hfill & =\left[\begin{array}{ccccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{11}^{\left(12\right)}{\widehat{L}}^{-1}{e}_1& \frac{n}{n+1}{H}_{11}^{\left(12\right)}{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_2^{T}e& \frac{1}{n+1}& \frac{n}{n+1}{w}_{k_2}^T{\widehat{L}}^{-1}{e}_1& \frac{n}{n+1}{w}_{k_2}^T{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ \frac{1}{n+1}{e}^T& \frac{n-k}{n+1}& \frac{1}{n+1}& \frac{1}{n+1}{e}^T{\widehat{L}}^{-1}{e}_1& \frac{1}{n+1}{e}^T{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ 0& \frac{n}{n+1}& \frac{1}{n+1}& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]\hfill \\ \hfill & =\left[\begin{array}{ccccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{11}^{\left(12\right)}e& \frac{n}{n+1}{H}_{11}^{\left(12\right)}{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_2^{T}e& \frac{1}{n+1}& \frac{n}{n+1}{w}_{k_2}^{T}e& \frac{n}{n+1}{w}_{k_2}^T{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ \frac{1}{n+1}{e}^T& \frac{n-k}{n+1}& \frac{1}{n+1}& \frac{k_2}{n+1}& \frac{1}{n+1}{e}^T{\widehat{L}}^{-1}\left[\begin{array}{ccc}{e}_2& \cdots & e_{n-k}\end{array}\right]\\ 0& \frac{n}{n+1}& \frac{1}{n+1}& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right],\hfill \end{array}$$

due to the fact that $H_{12}^{\left(2\right)}e=e,ande={\widehat{L}}^{-1}{e}_1.$

Let

$$\begin{array}{c}\hfill G_2=\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(11\right)}& \frac{n}{n+1}{H}_{12}^{\left(1\right)}e& \frac{1}{n+1}e& \frac{n}{n+1}{H}_{11}^{\left(12\right)}e\\ \frac{n}{n+1}{w}_{k_1}^T& \frac{n}{n+1}{w}_2^{T}e& \frac{1}{n+1}& \frac{n}{n+1}{w}_{k_2}^{T}e\\ \frac{1}{n+1}{e}^T& \frac{n-k}{n+1}& \frac{1}{n+1}& \frac{k_2}{n+1}\\ 0& \frac{n}{n+1}& \frac{1}{n+1}& 0\end{array}\right].\end{array}$$

(13)

Then, we obtain a PageRank vector expression for this level 4 partition by using Theorem 3.

Theorem 5.

Using the above notations and defining $G_2$ by (13), then $G_2$ of order $k_1+3$ with the same nonzero eigenvalues as the full new Google matrix G is stochastic. Let

$$\begin{array}{c}\hfill {\widehat{\sigma }}^T={\widehat{\sigma }}^T{G}_2,\widehat{\sigma }\ge 0,{\widehat{\sigma }}^{T}e=1,where{G}_2\in {\mathbb{R}}^{(k_1+3)\times (k_1+3)}.\end{array}$$

Partition ${\widehat{\sigma }}^T=\left[\begin{array}{ccc}{\widehat{\sigma }}_{1:k_1+1}^T& {\widehat{\sigma }}_{k_1+2}& {\widehat{\sigma }}_{k_1+3}\end{array}\right]$, where ${\widehat{\sigma }}_{k_1+2}$ and ${\widehat{\sigma }}_{k_1+3}$ are scalars. Then, we define the vector

$$\begin{array}{c}\hfill {\sigma }^T=\left[\begin{array}{ccc}{\widehat{\sigma }}_{1:k_1+1}^T& {\widehat{\sigma }}^T\left[\begin{array}{c}\frac{n}{n+1}{H}_{11}^{\left(12\right)}\\ \frac{n}{n+1}{w}_{k_2}^T\\ \frac{1}{n+1}{e}^T\\ 0\end{array}\right]& {\widehat{\sigma }}_{k_1+2}\end{array}\right]\in {\mathbb{R}}^{k_1+k_2+2},\end{array}$$

and the vector σ satisfies ${\sigma }^T{G}_1={\sigma }^T$. Thus, the PageRank vector ${\pi }_{n+1}$ for $G\in {\mathbb{R}}^{(n+1)\times (n+1)}$ is given by

$$\begin{array}{c}\hfill {\pi }_{n+1}^T=\left[\begin{array}{ccc}{\sigma }_{1:k_1+k_2}^T& {\sigma }^T\left[\begin{array}{c}\frac{n}{n+1}{H}_{12}^{\left(1\right)}\\ \frac{n}{n+1}{H}_{12}^{\left(2\right)}\\ \frac{1}{n+1}{e}^T\\ \frac{n}{n+1}{w}_2^T\end{array}\right]& {\sigma }_{k_1+k_2+1}\end{array}\right].\end{array}$$

Proof. 

The proof is technical modifications of the proof in Section 4.3; therefore, it is omitted here.   □

Thus, we claim that the new similarity matrix $\left[\begin{array}{cc}I& 0\\ 0& L\end{array}\right]$, where L satisfies (8), can lead to a dimension reduction of an involved minimal irreducible web link matrix in its 4-level matrix partition form. After obtaining a smaller vector ${\widehat{\sigma }}^T$ of $G_2$, the PageRank vector can recover according to Theorem 5. Now, we present the output of the corresponding algorithm in Algorithm 1.

Algorithm 1 Lumping algorithm for a minimal irreducible PageRank model (5)

Input:  An initial nonnegative vector ${\widehat{\sigma }}^T=\left[\begin{array}{cccc}{\widehat{\sigma }}_{1:k_1}^T& {\widehat{\sigma }}_{k_1+1}& {\widehat{\sigma }}_{k_1+2}& {\widehat{\sigma }}_{k_1+3}\end{array}\right]$,  ${\widehat{\sigma }}^T\ge 0$,  $\parallel {\widehat{\sigma }}^T\parallel =1$,  a prescribed tolerance $ϵ$. Output: The PageRank vector ${\pi }_n^T$.  Choose an initial vector ${\widehat{\sigma }}^T=\left[\begin{array}{cccc}{\widehat{\sigma }}_{1:k_1}^T& {\widehat{\sigma }}_{k_1+1}& {\widehat{\sigma }}_{k_1+2}& {\widehat{\sigma }}_{k_1+3}\end{array}\right]\in {\mathbb{R}}^{k_1+3}$,  ${\widehat{\sigma }}^T\ge 0$,  $\parallel {\widehat{\sigma }}^T\parallel =1$.  Set $\tau =1.$  while$\tau \ge ϵ$do      ${\tilde{\sigma }}_{1:k_1}^T=\frac{n}{n+1}{\widehat{\sigma }}_{1:k_1}^T{H}_{11}^{\left(11\right)}+\frac{n}{n+1}{\widehat{\sigma }}_{k_1+1}{w}_{k_1}^T+\frac{1}{n+1}·\frac{1}{n+1}{e}^T$;      ${\tilde{\sigma }}_{k_1+1}=\frac{n}{n+1}{\widehat{\sigma }}_{1:k_1}^T{H}_{12}^{\left(1\right)}e+\frac{n}{n+1}{w}_2^{T}e{\widehat{\sigma }}_{k_1+1}+\frac{n-k}{n+1}·\frac{1}{n+1}+\frac{n}{n+1}{\widehat{\sigma }}_{k_1+3}$;     % ${\widehat{\sigma }}_{k_1+2}=\frac{1}{n+1}$ (by direct computation);      ${\tilde{\sigma }}_{k_1+3}=1-{\widehat{\sigma }}_{1:k_1}^{T}e-{\widehat{\sigma }}_{k_1+1}-\frac{1}{n+1}$;      $\widehat{\sigma }=\tilde{\sigma }$;      $\tau =\parallel \tilde{\sigma }-\widehat{\sigma }{\parallel }_1$;  end while  Compute $x={\widehat{\sigma }}^T{\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{11}^{\left(12\right)}& \frac{n}{n+1}{w}_{k_2}^T& \frac{1}{n+1}{e}^T& 0\end{array}\right]}^T$;  Recover ${\sigma }^T$ by ${\sigma }^T=\left[\begin{array}{ccc}{\widehat{\sigma }}_{1:k_1+1}^T& x& {\widehat{\sigma }}_{k_1+2}\end{array}\right]$;  Compute $y={\sigma }^T{\left[\begin{array}{cccc}\frac{n}{n+1}{H}_{12}^{\left(1\right)}& \frac{n}{n+1}{H}_{12}^{\left(2\right)}& \frac{1}{n+1}{e}^T& \frac{n}{n+1}{w}_2^T\end{array}\right]}^T$;  Obtain the PageRank vector ${\pi }_{n+1}=\left[\begin{array}{ccc}{\sigma }_{1:k_1+k_2}^T& y& {\sigma }_{k_1+k_2+1}\end{array}\right]$.

The power method applied to $G_2$ involves a sparse matrix vector multiplied by a small matrix of order $k_1+3$ as well as several vector operations. The final step in Algorithm 1 recovers minimal irreducible PageRank vector according to Theorem 5. As the dangling nodes are further excluded from each iteration of the power method, Algorithm 1 has the same convergence rate as that of the power method applied to G but is much faster due to a reduced matrix computation.

5.2. Numerical Experiments

In this subsection, the web link matrix “wiki-Vote” which has 8297 Web pages and 103689 hyperlinks is used in our numerical example. There are 2187 dangling nodes and 905 “weakly nondangling” nodes in this web link matrix. We compare the power method, LDNA [20], and Algorithm 1 for computing (5) as follows:

• The original method [17], i.e., the power method applied to a full matrix G in (12).
• LDNA algorithm in [20]. Lumping all dangling nodes into a single node, the power method is applied to the $(k+2)\times (k+2)$ matrix ${\widehat{S}}^{\left(1\right)}$ in Theorem 2.
• Algorithm 1 (called as Algorithm 1). Lumping two classes of nodes, the power method applied to the $(k_1+3)\times (k_1+3)$ matrix $G_2$ in (13).

The parameters v and w are chosen as $v=w=\frac{1}{n}e$ in the above algorithms, where e is a vector of all ones. The overall termination criterion is triggered once the residual norm is below $ϵ=10-10$. Suppose that three algorithms all need N iterations until they reach the convergence criterion.

Table 1. Comparison of residues for three algorithms.

Iteration	Original	LDNA	Algorithm 1
10	$3.0192e-04$	$1.9117e-04$	$1.2928e-04$
20	$1.2539e-06$	$7.0788e-07$	$4.5348e-07$
30	$6.0013e-09$	$3.3144e-09$	$1.9865e-09$
36	$2.4952e-10$	$1.3619e-10$	$7.8191e-11$

and

Table 2. Comparison of operation costs for three algorithms.

Algorithms	Bounds for Operations
Original	$\mathcal{O}\left(\right(nnz\left(H\right)+n\left)N\right)$
LDNA	$\mathcal{O}\left((nnz\left(H_{11}\right)+k)N\right)+O(nnz\left(H_{12}\right)+k)$
Algorithm 1	$\mathcal{O}\left((nnz\left(\left[H_{11}^{\left(11\right)}{H}_{12}^{\left(1\right)}\right]\right)+k_1)N\right)+\mathcal{O}(nnz\left(\left[H_{11}^{\left(12\right)}{H}_{12}\right]\right)+k_1)$

give the residues and operation costs of three algorithms, respectively. Here, nnz(H) denotes the number of nonzero entries of matrix H. A sparse matrix-vector product requires $\mathcal{O}$(nnz(H)) operations. From Table 1, we can observe that Algorithm 1 produces the least residual norms compared with the other two algorithms. In addition, we also obtain the fact that the above three algorithms have almost the same convergence rate. We can find that the LDNA algorithm saves about $\mathcal{O}\left(\right(n-k\left)\right(N-1\left)\right)$ operations, and Algorithm 1 saves about $\mathcal{O}\left((n-k_1)(N-1)\right)$ operations from Table 2. Because Algorithm 1 computes the PageRank vector by lumping the dangling and “weakly nondangling” nodes and applies the power method to the smallest matrix, it needs the least operations.

6. Conclusions

In this paper, we have presented some new proofs and provided a novel efficient algorithm for computing a kind of minimal irreducible PageRank. Firstly, the spectral distribution of the new Google matrix is also validated by a similarity transformation method except for the determinant method. The simple and generalized similarity transformation matrix method is easier for validating Theorems 2 and 3 in the new PageRank model. Secondly, the new Google matrix of an $4\times 4$ block partition is further lumped to reduce the order of the involved computation matrix. Some theoretical results are discussed. Thirdly, as one real application of our results, the power method can operate on a smaller matrix than before. Therefore, the computational cost is reduced. For further work, we can consider how to choose an extrapolation method operating on a reduced matrix to accelerate the computation of web information retrieval models. The extrapolation method combined with a lumping method is also worth studying.