Scalable Uniform Graph Sampling by Local Computation

DOI10.1137/080716086MaRDI QIDQ3006147zbMATH OpenOpenAlexFDO

Authors Satu Elisa Schaeffer

Publication date 10 June 2011

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/c0a225ea0d9f4971d97305766a54b37c9c20c4ac

zbMATH Keywords

graphMarkov chainrandom walkrapid mixingsampling uniform distribution

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Sampling theory, sample surveys (62D05)

Recommendations

• On the Complexity of Sampling Vertices Uniformly from a Graph
• Graph sampling
• Graph sampling
• Uniform sampling of directed and undirected graphs conditional on vertex connectivity
• Uniform random sampling of planar graphs in linear time
• Guided sampling for large graphs
• Sampling regular graphs and a peer-to-peer network
• Sampling Regular Graphs and a Peer-to-Peer Network
• Efficient and near-optimal algorithms for sampling connected subgraphs
• scientific article; zbMATH DE number 2102755

Cited in

(6)

• On Local Distributed Sampling and Counting
• Uniform sampling of directed and undirected graphs conditional on vertex connectivity
• Edge sampling using local network information
• What can be sampled locally?
• Guided sampling for large graphs
• A fair-cost analysis of the random neighbor sampling method

Describes a project that uses

Uses Software

• Walksat
• ARPACK
• Octave

This page was built for publication: Scalable Uniform Graph Sampling by Local Computation

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