Information ranking and power laws on trees

DOI10.1239/AAP/1293113151zbMATH Open1211.60026arXiv0905.1738OpenAlexW2963796237MaRDI QIDQ3074494FDOQ3074494

Authors: Predrag R. Jelenković, Mariana Olvera-Cravioto 

Publication date: 9 February 2011

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: We study the situations when the solution to a weighted stochastic recursion has a power law tail. To this end, we develop two complementary approaches, the first one extends Goldie's (1991) implicit renewal theorem to cover recursions on trees; and the second one is based on a direct sample path large deviations analysis of weighted recursive random sums. We believe that these methods may be of independent interest in the analysis of more general weighted branching processes as well as in the analysis of algorithms.

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

Recommendations

• Asymptotic analysis for personalized web search
• Generalized PageRank on directed configuration networks
• PageRank in Scale-Free Random Graphs
• In-Degree and PageRank: why do they follow similar power laws?
• Determining Factors Behind the PageRank Log-Log Plot

zbMATH Keywords

power lawlarge deviationregular variationstochastic recursionimplicit renewal theorystochastic fixed point equationweighted branching processinformation ranking

Mathematics Subject Classification ID

Large deviations (60F10) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Random operators and equations (aspects of stochastic analysis) (60H25) Renewal theory (60K05)

Cites Work

• Applied Probability and Queues
• Random difference equations and renewal theory for products of random matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Implicit renewal theory and tails of solutions of random equations
• The contraction method for recursive algorithms
• The supremum of a negative drift random walk with dependent heavy-tailed steps.
• Authoritative sources in a hyperlinked environment
• The stochastic equation Y_n+1=A_nY_n + B_n with stationary coefficients
• Estimates for the distribution of sums and maxima of sums of random variables without the Cramér condition
• Limit theorems for semi-Markov processes and renewal theory for Markov chains
• On weighted branching processes in random environment.
• Regularly varying functions
• Tail behaviour of the busy period of a GI/GI/1 queue with subexponential service times
• On generalized multiplicative cascades
• Asymptotics of randomly stopped sums in the presence of heavy tails
• Information ranking and power laws on trees
• Tail asymptotics for the busy period in the \(GI/G/1\) queue.
• Large Deviations of Square Root Insensitive Random Sums
• Elementary fixed points of the BRW smoothing transforms with infinite number of summands
• Title not available (Why is that?)
• Title not available (Why is that?)
• Subexponential asymptotics for stochastic processes: Extremal behavior, stationary distributions and first passage probabilities
• In-Degree and PageRank: why do they follow similar power laws?
• Approximating the limiting quicksort distribution
• Asymptotic analysis for personalized web search
• Determining Factors Behind the PageRank Log-Log Plot
• Fixed points of a generalized smoothing transformation and applications to the branching random walk
• A stochastic fixed point equation related to weighted branching with deterministic weights
• On the asymptotic behaviour of the distributions of the busy period and service time in M/G/1
• On the Asymptotic Behavior of One-Sided Large Deviation Probabilities
• Convergence conditions for weighted branching processes
• Modulated branching processes, origins of power laws, and queueing duality

Cited In (34)

• PageRank on inhomogeneous random digraphs
• Pagerank asymptotics on directed preferential attachment networks
• Statistical analysis of the end-to-end delay of packet transfers in a peer-to-peer network
• Asymptotics for randomly weighted and stopped dependent sums
• Equity trees and graphs via information theory
• Approximations for finite-time ruin probability in a dependent discrete-time risk model with CMC simulations
• Tail behavior of solutions of linear recursions on trees
• PageRank in Scale-Free Random Graphs
• Nonparametric analysis of extremes on web graphs: PageRank versus max-linear model
• Max-linear models in random environment
• Extremal properties of evolving networks: local dependence and heavy tails
• Maxima and sums of non-stationary random length sequences
• Linear stochastic equations in the critical case
• Implicit renewal theory and power tails on trees
• Information ranking and power laws on trees
• Connectivity of random graphs after centrality-based vertex removal
• Regular variation in a fixed-point problem for single- and multi-class branching processes and queues
• Stochastic recursions on directed random graphs
• Convergence of the population dynamics algorithm in the Wasserstein metric
• Asymptotic analysis for personalized web search
• Maximums on trees
• Fixed points of the smoothing transform: two-sided solutions
• The smoothing transform: a review of contraction results
• Fixed points of inhomogeneous smoothing transforms
• Mean field analysis of personalized PageRank with implications for local graph clustering
• Convergence rates in the implicit renewal theorem on trees
• Title not available (Why is that?)
• Extremal independence in discrete random systems
• On fixed points of a generalized multidimensional affine recursion
• Implicit renewal theorem for trees with general weights
• Local weak convergence for PageRank
• PageRank's behavior under degree correlations
• Asymptotics for Weighted Random Sums
• Precise tail asymptotics of fixed points of the smoothing transform with general weights

This page was built for publication: Information ranking and power laws on trees

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