Sublinear-time algorithms for counting star subgraphs via edge sampling

DOI10.1007/s00453-017-0287-3zbMath1391.68120arXiv1601.04233OpenAlexW2586277680MaRDI QIDQ1709591

Maryam Aliakbarpour, John Peebles, Ronitt Rubinfeld, Themis Gouleakis, Anak Yodpinyanee, Amartya Shankha Biswas

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmsapproximate countingsubgraphssublinear-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (7)

Motif estimation via subgraph sampling: the fourth-moment phenomenon ⋮ Estimating the number of connected components in a graph via subgraph sampling ⋮ Unnamed Item ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Unnamed Item ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling

Uses Software

• QPath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faster algorithms for finding and counting subgraphs
• Finding and counting given length cycles
• Property testing lower bounds via communication complexity
• Tracking join and self-join sizes in limited storage
• Motifs in evolving cooperative networks look like protein structure networks
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• A sublinear-time approximation scheme for bin packing
• The space complexity of approximating the frequency moments
• Selectivity and cost estimation for joins based on random sampling
• Finding, Minimizing, and Counting Weighted Subgraphs
• Approximate Counting of Cycles in Streams
• Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
• Counting Arbitrary Subgraphs in Data Streams
• Counting Stars and Other Small Subgraphs in Sublinear-Time
• Approximating average parameters of graphs
• Optimal approximations of the frequency moments of data streams
• Simpler algorithm for estimating frequency moments of data streams
• Balanced Hashing, Color Coding and Approximate Counting
• Approximately Counting Triangles in Sublinear Time
• The Parameterized Complexity of Counting Problems
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Discovering and Exploiting Statistical Properties for Query Optimization in Relational Databases: A Survey
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Testing Probability Distributions Underlying Aggregated Data
• Local Graph Partitions for Approximation and Testing
• Approximating the Number of Network Motifs
• Estimating Sum by Weighted Sampling
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Research in Computational Molecular Biology
• Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
• Counting Subgraphs via Homomorphisms

This page was built for publication: Sublinear-time algorithms for counting star subgraphs via edge sampling