Information ranking and power laws on trees
From MaRDI portal
Publication:3074494
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5902453 (Why is no real title available?)
- scientific article; zbMATH DE number 193660 (Why is no real title available?)
- scientific article; zbMATH DE number 4000257 (Why is no real title available?)
- scientific article; zbMATH DE number 2119076 (Why is no real title available?)
- A stochastic fixed point equation related to weighted branching with deterministic weights
- Applied Probability and Queues
- Approximating the limiting quicksort distribution
- Asymptotic analysis for personalized web search
- Asymptotics of randomly stopped sums in the presence of heavy tails
- Authoritative sources in a hyperlinked environment
- Convergence conditions for weighted branching processes
- Determining Factors Behind the PageRank Log-Log Plot
- Elementary fixed points of the BRW smoothing transforms with infinite number of summands
- Estimates for the distribution of sums and maxima of sums of random variables without the Cramér condition
- Fixed points of a generalized smoothing transformation and applications to the branching random walk
- Implicit renewal theory and tails of solutions of random equations
- In-Degree and PageRank: why do they follow similar power laws?
- Information ranking and power laws on trees
- Large Deviations of Square Root Insensitive Random Sums
- Limit theorems for semi-Markov processes and renewal theory for Markov chains
- Modulated branching processes, origins of power laws, and queueing duality
- On generalized multiplicative cascades
- On the Asymptotic Behavior of One-Sided Large Deviation Probabilities
- On the asymptotic behaviour of the distributions of the busy period and service time in M/G/1
- On weighted branching processes in random environment.
- Random difference equations and renewal theory for products of random matrices
- Regularly varying functions
- Subexponential asymptotics for stochastic processes: Extremal behavior, stationary distributions and first passage probabilities
- Tail asymptotics for the busy period in the \(GI/G/1\) queue.
- Tail behaviour of the busy period of a GI/GI/1 queue with subexponential service times
- The contraction method for recursive algorithms
- The stochastic equation Yn+1=AnYn + Bn with stationary coefficients
- The supremum of a negative drift random walk with dependent heavy-tailed steps.
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
- Regular variation in a fixed-point problem for single- and multi-class branching processes and queues
- Connectivity of random graphs after centrality-based vertex removal
- 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
- scientific article; zbMATH DE number 2151257 (Why is no real title available?)
- On fixed points of a generalized multidimensional affine recursion
- Extremal independence in discrete random systems
- Implicit renewal theorem for trees with general weights
- Local weak convergence for PageRank
- PageRank's behavior under degree correlations
- Precise tail asymptotics of fixed points of the smoothing transform with general weights
- Asymptotics for Weighted Random Sums
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)
