A note on the PageRank of undirected graphs

作者：Grolmusz Vince^*

来源：Information Processing Letters, 2015, 115(6-8): 633-634.

DOI：10.1016/j.ipl.2015.02.015

• Analysis of algorithms
• PageRank
• Undirected graphs

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.

• 出版日期2015-8