A note on the PageRank of undirected graphs

DOI10.1016/J.IPL.2015.02.015MaRDI QIDQ2345872zbMATH OpenOpenAlexWikidataFDO

Authors Vince Grolmusz

Publication date 21 May 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.1960

zbMATH Keywords

analysis of algorithmsundirected graphsPageRank

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Internet topics (68M11)

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 noted that the PageRank for undirected graphs are 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.

Recommendations

• PageRank in Undirected Random Graphs
• RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
• Local weak convergence for PageRank
• PageRank in Scale-Free Random Graphs
• PageRank's behavior under degree correlations

Cites work

• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Adaptive methods for the computation of PageRank
• Fast distributed PageRank computation

Cited in

(15)

• PageRank on inhomogeneous random digraphs
• Pagerank asymptotics on directed preferential attachment networks
• PageRank regular digraphs with prime out-degrees
• Network Capacity Bound for Personalized PageRank in Multimodal Networks
• PageRank in Scale-Free Random Graphs
• Axiomatic characterization of PageRank
• PageRank, Connecting a Line of Nodes with a Complete Graph
• Probabilistic Relation between In-Degree and PageRank
• On the relationship between PageRank and automorphisms of a graph
• PageRank Nibble on the sparse directed stochastic block model
• PageRank in Undirected Random Graphs
• PageRank for networks, graphs, and Markov chains
• On the edges’ PageRank and line graphs
• On the initial value of PageRank
• Degree sequences of PageRank uniform graphs and digraphs with prime outdegrees

This page was built for publication: A note on the PageRank of undirected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345872)