A Note on the PageRank of Undirected Graphs

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.

References in corpus (1)

• Spectral centrality measures in complex networks

Cited by in corpus (13)

• Navigating the massive world of reddit: Using backbone networks to map user interests in social media
• Fast Distributed PageRank Computation
• Efficient Algorithms for Personalized PageRank
• Kemeny-based testing for COVID-19
• Centrality Measures in Complex Networks: A Survey
• Fair Augmentation for Graph Collaborative Filtering
• Bidirectional PageRank Estimation: From Average-Case to Worst-Case
• Line Artist: A Multiple Style Sketch to Painting Synthesis Scheme
• PageRank and The K-Means Clustering Algorithm
• The Multiple Instances of Node Centrality and their Implications on the Vulnerability of ISP Networks
• Multiple seed structure and disconnected networks in respondent-driven sampling
• On the initial value of PageRank
• Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal