Google PageRank as mean playing time for pinball on the reverse web

It is known that the output from Google’s PageRank algorithm may be interpreted as (a) the limiting value of a linear recurrence relation that is motivated by interpreting links as votes of confidence, and (b) the invariant measure of a teleporting random walk that follows links except for occasional uniform jumps. Here, we show that, for a sufficiently frequent jump rate, the PageRank score may also be interpreted as a mean finishing time for a reverse random walk. At a general step this new process either (i) remains at the current page, (ii) moves to a page that points to the current page, or (iii) terminates. The process is analogous to a game of pinball where a ball bounces between pages before eventually dropping down the exit chute. This new interpretation of PageRank gives another view of the principle that highly ranked pages will be those that are linked into by highly ranked pages that have relatively few outgoing links.     

Google矩阵和它的性质

网页等级(PageRank)是一个反映网页重要性的数值.当一个网页A连向另一个网页B的时候,A就等于给网页B投了有效的一票.一个网页接受的票越多,这个网页就越重要.同时,给网页B投票的网页本身的等级也决定了该选票的重要性.Google通过每张选票本身重要性和得票多少来计算一个网页的级别(重要性).Google的核心就是计算每一个网页的等级(即PageRank).本文主要介绍Google矩阵的定义和产生,解释PageRank的一些相关概念,证明Google矩阵及其第二特征值具有的一些性质,并简要介绍这些性质的应用.     

PageRank的改进算法——调整阻尼因子

Google将PageRank定义成某个非周期不可约Markov转移概率矩阵的平稳分布,于是对PageRank算法的改进所得到的矩阵一定要是非周期不可约Markov转移概率矩阵,结合RageRank算法和林共进修正算法思想,以及修正算法存在的问题,本文给出了改进算法,并通过简单试验对改进算法进行调整,调整后的改进算既满足Google的初衷又解决其算法的问题,也没有增加算法的复杂度.     

Rational extrapolation for the PageRank vector

An important problem in web search is to determine the importance of each page. From the mathematical point of view, this problem consists in finding the nonnegative left eigenvector of a matrix corresponding to its dominant eigenvalue 1. Since this matrix is neither stochastic nor irreducible, the power method has convergence problems. So, the matrix is replaced by a convex combination, depending on a parameter , with a rank one matrix. Its left principal eigenvector now depends on , and it is the PageRank vector we are looking for. However, when is close to 1, the problem is ill-conditioned, and the power method converges slowly. So, the idea developed in this paper consists in computing the PageRank vector for several values of , and then to extrapolate them, by a conveniently chosen rational function, at a point near 1. The choice of this extrapolating function is based on the mathematical expression of the PageRank vector as a function of . Numerical experiments end the paper.

     

On computing PageRank via lumping the Google matrix

Computing Google’s PageRank via lumping the Google matrix was recently analyzed in [I.C.F. Ipsen, T.M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl. 29 (2007) 1281–1296]. It was shown that all of the dangling nodes can be lumped into a single node and the PageRank could be obtained by applying the power method to the reduced matrix. Furthermore, the stochastic reduced matrix had the same nonzero eigenvalues as the full Google matrix and the power method applied to the reduced matrix had the same convergence rate as that of the power method applied to the full matrix. Therefore, a large amount of operations could be saved for computing the full PageRank vector.     

网页排序中的随机模型及算法

随着互联网规模的日益增长, 搜索引擎已经成为互联网上有效的信息获取工具. 而在众多搜索引擎的背后, 是信息检索技术, 也即网页排序算法在起作用. 网页排序包括重要性排序和相关性排序. 通过我们研究发现, 尽管这两类排序所依据的准则不同, 但是都可以通过建立适当的随机过程模型来研究. 对于网页重要性排序, 我们通过分析用户浏览网页的行为建立了Markov 骨架过程的框架. 基于该框架我们分析了三种不同的随机过程模型对用户行为模拟的合理程度, 并设计了名为BrowseRank 的一组新算法, 该算法可以根据用户上网行为来计算网页的重要性. 在网页相关性排序中, 我们主要针对排序结果联合问题建立了一个基于Markov 链的监督学习框架. 通过将传统方法的监督化, 使原来难于解决的问题变的易于学习, 将原来的NP- 难问题转化为一个半正定规划问题, 提高了效率.     

The Mathematics of Internet Search Engines

This article presents a survey of techniques for ranking results in search engines, with emphasis on link-based ranking methods and the PageRank algorithm. The problem of selecting, in relation to a user search query, the most relevant documents from an unstructured source such as the WWW is discussed in detail. The need for extending classical information retrieval techniques such as boolean searching and vector space models with link-based ranking methods is demonstrated. The PageRank algorithm is introduced, and its numerical and spectral properties are discussed. The article concludes with an alternative means of computing PageRank, along with some example applications of this new method.     

Equivalence of two linear programming relaxations for broadcast scheduling

A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.     

On PageRank versatility for multiplex networks: properties and some useful bounds

In this paper, some results concerning the PageRank versatility measure for multiplex networks are given. This measure extends to the multiplex setting the well-known classic PageRank. Particularly, we focus on some spectral properties of the Laplacian matrix of the multiplex and on obtaining boundaries for the ranking value of a given node when some personalization vector is added, as in the classic setting.     

Least-Squares Solution of Inverse Problem for Hermitian Anti-reflexive Matrices and Its Appoximation

In this paper, we first consider the least-squares solution of the matrix inverse problem as follows： Find a hermitian anti-reflexive matrix corresponding to a given generalized reflection matrix J such that for given matrices X, B we have minA ｜｜AX - B｜｜. The existence theorems are obtained, and a general representation of such a matrix is presented. We denote the set of such matrices by SE. Then the matrix nearness problem for the matrix inverse problem is discussed. That is： Given an arbitrary A^＊, find a matrix A E SE which is nearest to A^＊ in Frobenius norm. We show that the nearest matrix is unique and provide an expression for this nearest matrix.     

项目网络中考虑支配与扩散关系的组合决策

单纯侧重项目自身属性而不考虑项目关联性以及由项目衍生而来的技术、经验/信息扩散对项目组合决策时的影响,易导致决策偏差,低估具有潜在技术先导性项目的价值。对此,引用复杂网络理论,以项目关联性的视角,将项目间支配和扩散关系分别抽象为有向加权网络,运用K-shell分解方法构建项目组合网络中基于支配关系的项目影响力模型以及技术、经验/信息在项目间扩散传播的模型。然后,基于PageRank算法,综合考虑项目间支配与扩散关系,建立了项目优先级排序决策模型。最后,通过算例分析说明了该模型与算法的可行性与有效性,为企业项目组合决策提供了有益的参考。     

A Power–Arnoldi algorithm for computing PageRank

The PageRank algorithm plays an important role in modern search engine technology. It involves using the classical power method to compute the principle eigenvector of the Google matrix representing the web link graph. However, when the largest eigenvalue is not well separated from the second one, the power method may perform poorly. This happens when the damping factor is sufficiently close to 1. Therefore, it is worth developing new techniques that are more sophisticated than the power method. The approach presented here, called Power–Arnoldi, is based on a periodic combination of the power method with the thick restarted Arnoldi algorithm. The justification for this new approach is presented. Numerical tests illustrate the efficiency and convergence behaviour of the new algorithm. Copyright © 2007 John Wiley & Sons, Ltd.     

The PageRank model of minimal irreducible adjustment and its lumping method

In this paper, based on the original PageRank model with usual adjustment and computation, we propose a minimal irreducible adjustment model of PageRank. It is proved that the solution of this model is unique. Furthermore, an effective blocking and lumping algorithm is used for speeding up the process of obtaining this solution. Three numerical examples are given to verify the argues being correct and proper.     

Practical acceleration for computing the HITS ExpertRank vectors

A meaningful rank as well as efficient methods for computing such a rank are necessary in many areas of applications. Major methodologies for ranking often exploit principal eigenvectors. Kleinberg’s HITS model is one of such methodologies. The standard approach for computing the HITS rank is the power method. Unlike the PageRank calculations where many acceleration schemes have been proposed, relatively few works on accelerating HITS rank calculation exist. This is mainly because the power method often works quite well in the HITS setting. However, there are cases where the power method is ineffective, moreover, a systematic acceleration over the power method is desirable even when the power method works well. We propose a practical acceleration scheme for HITS rank calculations based on the filtered power method by adaptive Chebyshev polynomials. For cases where the gap-ratio is below 0.85 for which the power method works well, our scheme is about twice faster than the power method. For cases where gap-ratio is unfavorable for the power method, our scheme can provide significant speedup. When the ranking problems are of very large scale, even a single matrix–vector product can be expensive, for which accelerations are highly necessary. The scheme we propose is desirable in that it provides consistent reduction in number of matrix–vector products as well as CPU time over the power method, with little memory overhead.     

Matrix analysis for associated consistency in cooperative game theory

Hamiache axiomatized the Shapley value as the unique solution verifying the inessential game property, continuity and associated consistency. Driessen extended Hamiache’s axiomatization to the enlarged class of efficient, symmetric, and linear values. In this paper, we introduce the notion of row (resp. column)-coalitional matrix in the framework of cooperative game theory. The Shapley value as well as the associated game are represented algebraically by their coalitional matrices called the Shapley standard matrix M^Sh and the associated transformation matrix M_λ, respectively. We develop a matrix approach for Hamiache’s axiomatization of the Shapley value. The associated consistency for the Shapley value is formulated as the matrix equality M^Sh = M^Sh · M_λ. The diagonalization procedure of M_λ and the inessential property for coalitional matrices are fundamental tools to prove the convergence of the sequence of repeated associated games as well as its limit game to be inessential. In addition, a similar matrix approach is applicable to study Driessen’s axiomatization of a certain class of linear values. In summary, it is illustrated that matrix analysis is a new and powerful technique for research in the field of cooperative game theory.     

Symplectic homology of Lefschetz fibrations and Floer homology of the monodromy map

We construct a spectral sequence converging to symplectic homology of a Lefschetz fibration whose E ¹ page is related to Floer homology of the monodromy symplectomorphism and its iterates. We use this to show the existence of fixed points of certain symplectomorphisms.     

Normal dilatation of triangular matrices

LetR be a (real or complex) triangular matrix of ordern, say, an upper triangular matrix. Is it true that there exists a normaln×n matrixA whose upper triangle coincides with the upper triangle ofR? The answer to this question is “yes” and is obvious in the following cases: (1)R is real; (2)R is a complex matrix with a real or a pure imaginary main diagonal, and moreover, all the diagonal entries ofR belong to a straight line. The answer is also in the affirmative (although it is not so obvious) for any matrixR of order 2. However, even forn=3 this problem remains unsolved. In this paper it is shown that the answer is in the affirmative also for 3×3 matrices.     

求解PageRank问题的重启GMRES修正的多分裂迭代法

PageRank算法已经成为网络搜索引擎的核心技术。针对PageRank问题导出的线性方程组,首先将Krylov子空间方法中的重启GMRES(generalized minimal residual)方法与多分裂迭代(multi-splitting iteration,MSI)方法相结合,提出了一种重启GMRES修正的多分裂迭代法;然后,给出了该算法的详细计算流程和收敛性分析;最后,通过数值实验验证了该算法的有效性。     

About the Power Law of the PageRank Vector Component Distribution. Part 2. The Buckley–Osthus Model,Verification of the Power Law for This Model,and Setup of Real Search Engines

This paper continues article [13]. Here we consider the Buckley–Osthus model for formation of an Internet network. We numerically calculate the PageRank vector for networks generated by this model.We show that the components of this vector are distributed according to a power law. We also discuss the computational aspects of this model with respect to the numerical methods for calculation of the PageRank vector, which were presented in the first part of the work. Finally, we describe a more general model for web-page ranking and some approaches to solve the optimization problem arising in this model learning.     

A preconditioned and extrapolation-accelerated GMRES method for PageRank

In this paper, we propose and analyze GMRES-type methods for the PageRank computation. However, GMRES may converge very slowly or sometimes even diverge or break down when the damping factor is close to 1 and the dimension of the search subspace is low. We propose two strategies: preconditioning and vector extrapolation accelerating, to improve the convergence rate of the GMRES method. Theoretical analysis demonstrate the efficiency of the proposed strategies and numerical experiments show that the performance of the proposed methods is very much better than that of the traditional methods for PageRank problems.