Document Open Access Logo

An Optimal Algorithm for Triangle Counting in the Stream

Authors Rajesh Jayaram, John Kallaugher

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.11.pdf
  • Filesize: 0.62 MB
  • 11 pages

Document Identifiers

Author Details

Rajesh Jayaram
  • Carnegie Mellon University, Pittsburgh, PA, USA
John Kallaugher
  • The University of Texas at Austin, Austin, TX, USA

Funding

  • Jayaram, Rajesh: Rajesh Jayaram would like to acknowledge partial support from the Office of Naval Research (ONR) under grant Number N00014-18-1-2562, and the National Science Foundation (NSF) under Grant Number CCF-1815840.
  • Kallaugher, John: John Kallaugher would like to acknowledge support from the National Science Foundation (NSF) under Grant Number CCF-1751040 (CAREER).

Cite As Get BibTex

Rajesh Jayaram and John Kallaugher. An Optimal Algorithm for Triangle Counting in the Stream. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 11:1-11:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.11

Abstract

We present a new algorithm for approximating the number of triangles in a graph G whose edges arrive as an arbitrary order stream. If m is the number of edges in G, T the number of triangles, Δ_E the maximum number of triangles which share a single edge, and Δ_V the maximum number of triangles which share a single vertex, then our algorithm requires space: 
Õ(m/T⋅(Δ_E + √{Δ_V}))
Taken with the Ω((m Δ_E)/T) lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the Ω((m √{Δ_V})/T) lower bound of Kallaugher and Price (SODA 2017), our algorithm is optimal up to log factors, resolving the complexity of a classic problem in graph streaming.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
Keywords
  • Triangle Counting
  • Streaming
  • Graph Algorithms
  • Sampling
  • Sketching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 6:1-6:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  2. Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '02, pages 623-632, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=545381.545464.
  3. Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '08, pages 16-24, New York, NY, USA, 2008. ACM. URL: https://doi.org/10.1145/1401890.1401898.
  4. Suman K. Bera and Amit Chakrabarti. Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1-11:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  5. Jonathan W. Berry, Bruce Hendrickson, Randall A. LaViolette, and Cynthia A. Phillips. Tolerating the community detection resolution limit with edge weighting. Phys. Rev. E, 83:056119, May 2011. URL: https://doi.org/10.1103/PhysRevE.83.056119.
  6. Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In Automata, Languages, and Programming, pages 244-254. Springer, 2013. Google Scholar
  7. Luciana S Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 253-262. ACM, 2006. Google Scholar
  8. J Lawrence Carter and Mark N Wegman. Universal classes of hash functions. Journal of computer and system sciences, 18(2):143-154, 1979. Google Scholar
  9. Graham Cormode and Hossein Jowhari. A second look at counting triangles in graph streams. Theoretical Computer Science, 552:44-51, 2014. Google Scholar
  10. Graham Cormode and Hossein Jowhari. L_p samplers and their applications: A survey. ACM Comput. Surv., 52(1), 2019. URL: https://doi.org/10.1145/3297715.
  11. Jean-Pierre Eckmann and Elisha Moses. Curvature of co-links uncovers hidden thematic layers in the world wide web. Proceedings of the National Academy of Sciences, 99(9):5825-5829, 2002. URL: https://doi.org/10.1073/pnas.032093399.
  12. Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles in sublinear time. In Proceedings of the 56th FOCS, pages 614-633. IEEE, 2015. Google Scholar
  13. Talya Eden, Dana Ron, and C. Seshadhri. On approximating the number of k-cliques in sublinear time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 722–734, New York, NY, USA, 2018. Association for Computing Machinery. Google Scholar
  14. Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In Computing and Combinatorics, pages 710-716. Springer, 2005. Google Scholar
  15. John Kallaugher, Michael K10.1145/3188745.3188810oapralov, and Eric Price. The sketching complexity of graph and hypergraph counting. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 556-567. IEEE, 2018. Google Scholar
  16. John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of counting cycles in the adjacency list streaming model. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 119-133. ACM, 2019. URL: https://doi.org/10.1145/3294052.3319706.
  17. John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1778-1797. SIAM, 2017. Google Scholar
  18. John Kallaugher and Eric Price. Separations and equivalences between turnstile streaming and linear sketching. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1223-1236. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384278.
  19. Mihail N Kolountzakis, Gary L Miller, Richard Peng, and Charalampos E Tsourakakis. Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Mathematics, 8(1-2):161-185, 2012. Google Scholar
  20. Yi Li, Huy L. Nguyễn, and David P. Woodruff. Turnstile streaming algorithms might as well be linear sketches. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 174-183, 2014. URL: https://doi.org/10.1145/2591796.2591812.
  21. Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '16, pages 401-411, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2902251.2902283.
  22. Rasmus Pagh and Charalampos E Tsourakakis. Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112(7):277-281, 2012. Google Scholar
  23. A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proc. VLDB Endow., 6(14):1870-1881, 2013. URL: https://doi.org/10.14778/2556549.2556569.
  24. Charalampos E Tsourakakis, U Kang, Gary L Miller, and Christos Faloutsos. Doulion: counting triangles in massive graphs with a coin. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 837-846. ACM, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact