Fast Low-Cost Estimation of Network Properties Using Random Walks

DOI10.1080/15427951.2016.1164100zbMath1465.05169OpenAlexW19046872MaRDI QIDQ5856437

Yiannis Siantos, Colin Cooper, Tomasz Radzik

Publication date: 26 March 2021

Published in: Internet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/15427951.2016.1164100

zbMATH Keywords

cycle formula of regenerative processeslarge connected undirected graphsweighted random walks with edge weights

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

Related Items (max. 100)

Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation ⋮ Multiple random walks on graphs: mixing few to cover many

Cites Work

• Unnamed Item
• Unnamed Item
• Chernoff-type bound for finite Markov chains
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• A probability inequality for the occupation measure of a reversible Markov chain
• Peer counting and sampling in overlay networks based on random walks
• Quick Detection of Nodes with Large Degrees
• Fast Low-Cost Estimation of Network Properties Using Random Walks
• Emergence of Scaling in Random Networks
• Tail Estimates for Sums of Variables Sampled by a Random Walk
• Peer counting and sampling in overlay networks
• The Cover Time of Random Regular Graphs

This page was built for publication: Fast Low-Cost Estimation of Network Properties Using Random Walks