Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

DOI10.1145/3596495MaRDI QIDQ6051991zbMATH OpenOpenAlexFDO

Authors Marco Bressan

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.12102

zbMATH Keywords

random walkssubgraph samplingsublinear algorithms

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: We study the following problem: given an integer $kge3$ and a simple graph $G$, sample a connected induced $k$-node subgraph of $G$ uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, and more. Surprisingly, no efficient algorithm is known for uniform sampling; the only somewhat efficient algorithms available yield samples that are only approximately uniform, with running times that are unclear or suboptimal. In this work we provide: (i) a near-optimal mixing time bound for a well-known random walk technique, (ii) the first efficient algorithm for truly uniform graphlet sampling, and (iii) the first sublinear-time algorithm for $epsilon$-uniform graphlet sampling.

Recommendations

• Efficient and near-optimal algorithms for sampling connected subgraphs
• The hardness of sampling connected subgraphs
• Estimating the number of connected components in a graph via subgraph sampling
• scientific article; zbMATH DE number 2102755
• Tight Bounds on Vertex Connectivity Under Sampling
• A linear-time algorithm for sampling graphs with given degrees
• Tight bounds on vertex connectivity under vertex sampling
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds

Cites work

• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Approximately counting triangles in sublinear time
• Arboricity and Subgraph Listing Algorithms
• Color-coding
• Counting Subgraphs in Degenerate Graphs
• Efficient and near-optimal algorithms for sampling connected subgraphs
• Faster algorithms for counting subgraphs in sparse graphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing time bounds for graphlet random walks
• Networks, crowds and markets. Reasoning about a highly connected world.
• On approximating the number of k-cliques in sublinear time
• On sampling edges almost uniformly
• On the triangle clique cover and \(K_t\) clique cover problems
• Sampling Multiple Edges Efficiently
• Smallest-last ordering and clustering and graph coloring algorithms
• Tight Bounds for Testing Bipartiteness in General Graphs
• Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time

Cited in

(4)

• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• Tight Bounds on Vertex Connectivity Under Sampling

This page was built for publication: Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

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