Fast Low-Cost Estimation of Network Properties Using Random Walks

DOI10.1080/15427951.2016.1164100MaRDI QIDQ5856437zbMATH OpenOpenAlexFDO

Authors Colin Cooper, Tomasz Radzik, Yiannis Siantos

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

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

Recommendations

• Fast low-cost estimation of network properties using random walks
• Estimating graph parameters with random walks
• Fast distributed computation in dynamic networks via random walks
• Estimating graph parameters via random walks with restarts
• Estimating random walk centrality in networks
• Finding network communities using random walkers with improved accuracy

Cites work

• A probability inequality for the occupation measure of a reversible Markov chain
• Chernoff-type bound for finite Markov chains
• Emergence of Scaling in Random Networks
• Fast low-cost estimation of network properties using random walks
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Peer counting and sampling in overlay networks based on random walks
• Peer counting and sampling in overlay networks, random walk methods
• Quick detection of nodes with large degrees
• Tail Estimates for Sums of Variables Sampled by a Random Walk
• The Cover Time of Random Regular Graphs

Cited in

(11)

• Sampling online social networks by random walk with indirect jumps
• Estimating graph parameters with random walks
• Estimating random walk centrality in networks
• Quick detection of nodes with large degrees
• Fast low-cost estimation of network properties using random walks
• Quick detection of nodes with large degrees
• Estimating sizes of social networks via biased sampling
• Multiple random walks on graphs: mixing few to cover many
• The joint distribution of first return times and of the number of distinct sites visited by a 1d random walk before returning to the origin
• Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation
• Calculating statistics of complex networks through random walks with an application to the on-line social network bebo

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

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