Triangle counting in dynamic graph streams
From MaRDI portal
Publication:334947
DOI10.1007/978-3-319-08404-6_27zbMATH Open1348.68294arXiv1404.4696OpenAlexW1608198436MaRDI QIDQ334947FDOQ334947
Authors: Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, Rasmus Pagh 
Publication date: 1 November 2016
Published in: Algorithmica, Algorithm Theory – SWAT 2014 (Search for Journal in Brave)
Abstract: Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However, with a few exceptions, the algorithms have considered {em insert-only} streams. We present a new algorithm estimating the number of triangles in {em dynamic} graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach combining sampling of vertex triples and sparsification of the input graph. In the course of the analysis of the algorithm we present a lower bound on the number of pairwise independent 2-paths in general graphs which might be of independent interest. At the end of the paper we discuss lower bounds on the space complexity of triangle counting algorithms that make no assumptions on the structure of the graph.
Full work available at URL: https://arxiv.org/abs/1404.4696
Recommendations
- Triangle counting in dynamic graph streams
- A second look at counting triangles in graph streams
- A second look at counting triangles in graph streams (corrected)
- Computing and Combinatorics
- scientific article; zbMATH DE number 2119719
- An Optimal Algorithm for Triangle Counting in the Stream
- scientific article; zbMATH DE number 6862103
- Counting triangles in massive graphs with MapReduce
- Efficient triangle counting in large graphs via degree-based vertex partitioning
Cites Work
- Statistical mechanics of complex networks
- Universal classes of hash functions
- Sampling in dynamic data streams and applications
- Multiplying matrices faster than coppersmith-winograd
- Finding and counting given length cycles
- Data streams: algorithms and applications.
- Uniform Hashing in Constant Time and Optimal Space
- The Power of Simple Tabulation Hashing
- Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
- A random graph model for massive graphs
- On randomized one-round communication complexity
- Triangle sparsifiers
- Approximate counting of cycles in streams
- Counting arbitrary subgraphs in data streams
- Colorful triangle counting and a \textsc{MapReduce} implementation
- Computing and Combinatorics
- Efficient triangle counting in large graphs via degree-based vertex partitioning
Cited In (20)
- On triangle estimation using tripartite independent set queries
- FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams
- Counting Triangles under Updates in Worst-Case Optimal Time
- Dynamic set intersection
- Triangle sparsifiers
- Densest subgraph in dynamic graph streams
- A hybrid sampling scheme for triangle counting
- Efficient triangle counting in large graphs via degree-based vertex partitioning
- Title not available (Why is that?)
- On Estimating Path Aggregates over Streaming Graphs
- Computing and Combinatorics
- Title not available (Why is that?)
- Triangle counting in dynamic graph streams
- How hard is counting triangles in the streaming model?
- Corrigendum to: ``A second look at counting triangles in graph streams
- Efficient triangle counting in large graphs via degree-based vertex partitioning
- A second look at counting triangles in graph streams
- Approximate counting of cycles in streams
- Counting arbitrary subgraphs in data streams
- Parameterized aspects of triangle enumeration
Uses Software
This page was built for publication: Triangle counting in dynamic graph streams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334947)
