4 papers
Linking PageRank, Time Reversal, and Policy Evaluation
Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak
We establish a connection between policy evaluation in Markov decision processes and PageRank in network analysis. For a fixed policy, we show that the value function of a discount…
Planted clique recovery in random geometric graphs
Konstantin Avrachenkov, Andrei Bobu, Nelly Litvak +1
We investigate the problem of identifying planted cliques in random geometric graphs, focusing on two distinct algorithmic approaches: the first based on vertex degrees (VD) and th…
Computing Stationary Distribution via Dirichlet-Energy Minimization by Coordinate Descent
Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak
We present an optimization-based formulation of the Red Light Green Light (RLGL) algorithm for computing stationary distributions of large Markov chains. This perspective clarifies…
The friendship paradox for trees
Rajat Subhra Hazra, Frank den Hollander, Nelly Litvak +1
We analyse the friendship paradox on finite and infinite trees. In particular, we monitor the vertices for which the friendship-bias is positive, neutral and negative, respectively…