PageRank in Scale-Free Random Graphs

DOI10.1007/978-3-319-13123-8_10MaRDI QIDQ2945278zbMATH OpenOpenAlexFDO

Authors Ningyuan Chen, Nelly Litvak, Mariana Olvera-Cravioto

Publication date 9 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distribution of PageRank on a directed configuration modeltree approximation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Internet topics (68M11) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We analyze the distribution of PageRank on a directed configuration model and show that as the size of the graph grows to infinity it can be closely approximated by the PageRank of the root node of an appropriately constructed tree. This tree approximation is in turn related to the solution of a linear stochastic fixed point equation that has been thoroughly studied in the recent literature.

Recommendations

• PageRank in Undirected Random Graphs
• PageRank on inhomogeneous random digraphs
• PageRank of Scale-Free Growing Networks
• PageRank for networks, graphs, and Markov chains
• \texttt{PageRank} and random walks on graphs
• A note on the PageRank of undirected graphs
• Pagerank asymptotics on directed preferential attachment networks
• RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
• The PageRank vector of a scale-free web network growing by preferential attachment

Cites work

• Asymptotic analysis for personalized web search
• Determining Factors Behind the PageRank Log-Log Plot
• Directed random graphs with given degree distributions
• Fixed points of the smoothing transform: two-sided solutions
• Generalized PageRank on directed configuration networks
• Google's PageRank and beyond. The science of search engine rankings
• scientific article; zbMATH DE number 2089988 (Why is no real title available?)
• Implicit renewal theorem for trees with general weights
• Implicit renewal theory and power tails on trees
• In-Degree and PageRank: why do they follow similar power laws?
• Information ranking and power laws on trees
• PageRank of Scale-Free Growing Networks
• Precise tail index of fixed points of the two-sided smoothing transform
• Random graphs and complex networks. Volume 1
• Tail behavior of solutions of linear recursions on trees

Cited in

(37)

• 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
• Maxima and sums of non-stationary random length sequences
• PageRank's behavior under degree correlations
• A note on the PageRank of undirected graphs
• PageRank regular digraphs with prime out-degrees
• \texttt{PageRank} and random walks on graphs
• Random alpha PageRank
• Distributing antidote using PageRank vectors
• Information ranking and power laws on trees
• Nonparametric analysis of extremes on web graphs: PageRank versus max-linear model
• Using PageRank to Characterize Web Structure
• PageRank in Undirected Random Graphs
• RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
• Probabilistic Relation between In-Degree and PageRank
• How to improve the PageRank of a tree
• Robustness of power-law behavior in cascading line failure models
• PageRank as a discrete Green's function
• On the edges’ PageRank and line graphs
• PageRank for networks, graphs, and Markov chains
• scientific article; zbMATH DE number 2089988 (Why is no real title available?)
• A Dynamical System for PageRank with Time-Dependent Teleportation
• Statistical Clustering of a Random Network by Extremal Properties
• Generalized PageRank on directed configuration networks
• Using Polynomial Chaos to Compute the Influence of Multiple Random Surfers in the PageRank Model
• PageRank of Scale-Free Growing Networks
• On Local Estimations of PageRank: A Mean Field Approach
• PageRank Nibble on the sparse directed stochastic block model
• Mixing time of PageRank surfers on sparse random digraphs
• Rankings in directed configuration models with heavy tailed in-degrees
• Stochastic recursions on directed random graphs
• Extremal properties of evolving networks: local dependence and heavy tails
• Connectivity of random graphs after centrality-based vertex removal
• Tail asymptotics and precise large deviations for some Poisson cluster processes
• Mixing cutoff for simple random walks on the Chung-Lu digraph

This page was built for publication: PageRank in Scale-Free Random Graphs

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