Quasi-stationary distributions as centrality measures for the giant strongly connected component of a reducible graph

A random walk can be used as a centrality measure of a directed graph. However, if the graph is reducible the random walk will be absorbed in some subset of nodes and will never visit the rest of the graph. In Google PageRank the problem was solved by the introduction of uniform random jumps with some probability. Up to the present, there is no final answer to the question about the choice of this probability. We propose to use a parameter-free centrality measure which is based on the notion of a quasi-stationary distribution. Specifically, we suggest four quasi-stationary based centrality measures, analyze them and conclude that they produce approximately the same ranking.     

Effective vaccination strategies for realistic social networks

We consider the effectiveness of targeted vaccination at preventing the spread of infectious disease in a realistic social network. We compare vaccination strategies based on no information (random vaccination) to complete information (PageRank) about the network. The most effective strategy we find is to vaccinate those people with the most unvaccinated contacts. However, this strategy requires considerable information and computational effort which may not be practical. The next best strategies vaccinate people with many contacts who in turn have few contacts.     

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.     

Comparison of Three Web Search Algorithms

In this paper we discuss three important kinds of Markov chains used in Web search algorithms-the maximal irreducible Markov chain, the miuimal irreducible Markov chain and the middle irreducible Markov chain, We discuss the stationary distributions, the convergence rates and the Maclaurin series of the stationary distributions of the three kinds of Markov chains. Among other things, our results show that the maximal and minimal Markov chains have the same stationary distribution and that the stationary distribution of the middle Markov chain reflects the real Web structure more objectively. Our results also prove that the maximal and middle Markov chains have the same convergence rate and that the maximal Markov chain converges faster than the minimal Markov chain when the damping factor α 〉1/√2.     

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.     

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

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

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.     

解线性方程组的松弛方法及其应用

线性方程组在科学和工程领域中有着重要的应用,松弛方法是求解线性方程组的有效算法之一.本文在著名的Gauss-Seidel迭代法的基础上,研究了一种有效的松弛方法.理论分析表明,该方法能收敛到线性方程组的唯一解.此外,我们还将该方法应用在鞍点问题和PageRank问题的求解上,并得出了相应的数值结果.结果表明该方法比现有的松弛方法更有效.     

两种万维网搜索算法的比较

Google 创始人sergey Brin 和Lawrence Page 把万维网搜索算法PageRank 定义成某个非周期不可约马氏链的唯一平稳分布.本文讨论了万维网搜索算法中使用的两个重要的马氏链-maximal 不可约马氏链和minimal 不可约马氏链-收敛到平稳分布的收敛速度.结果表明,在阻尼因子α>1/2~(1/2)时,maximal 马氏链比minimal 马氏链的收敛速度快.本文也给出了minimal 马氏链k 步转移矩阵的表达式,及其平稳分布关于参数α的各阶导数和Maclaurin 级数展开.