8 citations · 10 across the 5 of their papers we have counts for
5 papers
On approximating the stationary distribution of time-reversible Markov chains
Marco Bressan, Enoch Peserico, Luca Pretto
Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches requi…
The Power of Local Information in PageRank
Marco Bressan, Enoch Peserico, Luca Pretto
How large a fraction of a graph must one explore to rank a small set of nodes according to their PageRank scores? We show that the answer is quite nuanced, and depends crucially on…
Simple set cardinality estimation through random sampling
Marco Bressan, Enoch Peserico, Luca Pretto
We present a simple algorithm that estimates the cardinality of a set when allowed to sample elements of uniformly and independently at random. Our algorithm with proba…
Sublinear algorithms for local graph centrality estimation
Marco Bressan, Enoch Peserico, Luca Pretto
We study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of…
The rank convergence of HITS can be slow
Enoch Peserico, Luca Pretto
We prove that HITS, to "get right" h of the top k ranked nodes of an N>=2k node graph, can require h^(Omega(N h/k)) iterations (i.e. a substantial Omega(N h log(h)/k) matrix multip…