A note on the PageRank of undirected graphs

Grolmusz, Vince (2015) A note on the PageRank of undirected graphs. INFORMATION PROCESSING LETTERS, 115 (6-8). pp. 633-634. ISSN 0020-0190

Text undirected_pagerank.pdf Restricted to Registered users only Download (154kB) | Request a copy

Abstract

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.

Actions (login required)

Edit Item