A note on the PageRank of undirected graphs
A note on the PageRank of undirected graphs
复制标题
DOI：
10.1016/j.ipl.2015.02.015
复制
发表时间：
2015-06-01
影响因子：
0.5
通讯作者：
Grolmusz, Vince
中科院分区：
文献类型：
--
作者：
Grolmusz, Vince
PageRank是一种广泛使用的网络评分函数，尤其是万维网图表。PageRank是为有向图定义的，但在某些特殊情况下会出现无向图的应用程序。在文献中，广泛但不是唯一地注意到无向图的PageRank与图的顶点的度成正比。我们证明了PageRank定义中关于特定个性化向量的这一说法，并且我们还证明了一般而言，无向图的PageRank与图的度分布并不完全成比例：我们的主要定理给出了PageRank和度分布向量之差的L-1范数的上下界。给出了PageRank与度成正比的充要条件。(C)2015爱思唯尔B.V.保留所有权利。
The PageRank is a widely used scoring function of networks in general and of the World Wide Web graph in particular. The PageRank is defined for directed graphs, but in some special cases applications for undirected graphs occur. In the literature it is widely but not exclusively - noted that the PageRank for undirected graphs is proportional to the degrees of the vertices of the graph. We prove that statement for a particular personalization vector in the definition of the PageRank, and we also show that in general, the PageRank of an undirected graph is not exactly proportional to the degree distribution of the graph: our main theorem gives an upper and a lower bound to the L-1 norm of the difference of the PageRank and the degree distribution vectors. A necessary and sufficient condition is also given for the PageRank for being proportional to the degree. (c) 2015 Elsevier B.V. All rights reserved.