RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK

DOI10.1142/S0218127407018439MaRDI QIDQ3511043zbMATH OpenOpenAlexFDO

Authors Santo Fortunato, Alessandro Flammini

Publication date 4 July 2008

Published in International Journal of Bifurcation and Chaos in Applied Sciences and Engineering (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Paths and cycles (05C38) Sums of independent random variables; random walks (60G50) Network design and communication in computer systems (68M10) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Abstract: PageRank, the prestige measure for Web pages used by Google, is the stationary probability of a peculiar random walk on directed graphs, which interpolates between a pure random walk and a process where all nodes have the same probability of being visited. We give some exact results on the distribution of PageRank in the cases in which the damping factor q approaches the two limit values 0 and 1. When q -> 0 and for several classes of graphs the distribution is a power law with exponent 2, regardless of the in-degree distribution. When q -> 1 it can always be derived from the in-degree distribution of the underlying graph, if the out-degree is the same for all nodes.

Recommendations

• PageRank in Scale-Free Random Graphs
• PageRank on inhomogeneous random digraphs
• Generalized PageRank on directed configuration networks
• PageRank in Undirected Random Graphs
• PageRank of Scale-Free Growing Networks

Cites work

• Complex networks: structure and dynamics
• scientific article; zbMATH DE number 742629 (Why is no real title available?)
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks

Cited in

(25)

• PageRank on inhomogeneous random digraphs
• Pagerank asymptotics on directed preferential attachment networks
• The PageRank vector of a scale-free web network growing by preferential attachment
• Local weak convergence for PageRank
• Traditional and Lazy PageRanks for a line of nodes connected with complete graphs
• A note on the PageRank of undirected graphs
• PageRank in Scale-Free Random Graphs
• \texttt{PageRank} and random walks on graphs
• Random walks in directed modular networks
• PageRank in Undirected Random Graphs
• Probabilistic Relation between In-Degree and PageRank
• scientific article; zbMATH DE number 5722222 (Why is no real title available?)
• Asymptotic analysis for personalized web search
• A model of self-avoiding random walks for searching complex networks
• Rethinking centrality: the role of dynamical processes in social network analysis
• Analysis of node2vec random walks on networks
• Generalized PageRank on directed configuration networks
• Distribution of PageRank Mass Among Principle Components of the Web
• Determining Factors Behind the PageRank Log-Log Plot
• Limit of PageRank with damping factor
• PageRank of Scale-Free Growing Networks
• PageRank Nibble on the sparse directed stochastic block model
• On the initial value of PageRank
• Google PageRank as mean playing time for pinball on the reverse web
• Quasi-stationary distributions as centrality measures for the giant strongly connected component of a reducible graph

This page was built for publication: RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK

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