A note on the PageRank of undirected graphs

DOI10.1016/J.IPL.2015.02.015zbMATH Open1328.68149arXiv1205.1960OpenAlexW1995853580WikidataQ56815220 ScholiaQ56815220MaRDI QIDQ2345872FDOQ2345872

Authors: Vince Grolmusz 

Publication date: 21 May 2015

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

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.

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

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

zbMATH Keywords

analysis of algorithmsundirected graphsPageRank

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Adaptive methods for the computation of PageRank
• Fast distributed PageRank computation
• Title not available (Why is that?)

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
• Axiomatic characterization of PageRank
• PageRank in Scale-Free Random Graphs
• PageRank, Connecting a Line of Nodes with a Complete Graph
• On the relationship between PageRank and automorphisms of a graph
• Probabilistic Relation between In-Degree and PageRank
• 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)