Andrew McGregor
ABSTRACT
The problem of estimating the number of cycles in a graph is one of the most widely studied graph problems in the data stream model. Three relevant variants of the data stream model include: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order, the random order model in which the edges are randomly permuted, and the adjacency list order model in which all edges incident to the same vertex appear consecutively. In this paper, we focus on the problem of triangle and four-cycle counting in these models. We improve over the state-of-the-art results as follows, where n is the number of vertices, m is the number of edges and T is the number of triangles/four-cycles in the graph (i.e., the quantity being estimated): Random Order Model: We present a single-pass algorithm that (1+ε)-approximates the number of triangles using ~O(ε-2 m/√T) space and prove that this is optimal in the range T ≤ √m. The best previous result, a (3+ε)-approximation using ~O(ε-4.5 m/√T) space, was presented by Cormode and Jowhari~(Theor. Comput. Sci. 2017). Adjacency List Model: We present an algorithm that returns a (1+ε)-approximation of the number of 4-cycles using two passes and ~O(ε-4 m/√T) space. The best previous result, a constant approximation using ~O(m/T3/8) space, was presented by Kallaugher et al. (PODS~2019). We also show that (1+ε)-approximation in a single pass is possible in a) polylog(n) space if T=Ω(n2) and b) ~O(n) space if T=Ω(n). Arbitrary Order Model: We present a three-pass algorithm that (1+ε)-approximates the number of 4-cycles using ~O(ε-2 m/T1/4) space and a one-pass algorithm that uses ~O(ε-2 n) space when T=Ω(n2). The best existing result, a (1+ε)-approximation using ~O(ε-2 m2/T) space, was presented by Bera and Chakrabarti (STACS~2017). We also show a multi-pass lower bound and another algorithm for distinguishing graphs with no four cycles and graphs with many 4-cycles.
- Lars Arge, Michael T. Goodrich, and Nodari Sitchinava. 2010. Parallel external memory graph algorithms. In 24th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2010, Atlanta, Georgia, USA, 19--23 April 2010 - Conference Proceedings. 1--11. https://doi.org/10.1109/IPDPS.2010.5470440Google Scholar
Cross Ref
- Shaikh Arifuzzaman, Maleq Khan, and Madhav V. Marathe. 2013. PATRIC: a parallel algorithm for counting triangles in massive networks. In 22nd ACM International Conference on Information and Knowledge Management, CIKM'13, San Francisco, CA, USA, October 27 - November 1, 2013. 529--538. https://doi.org/10.1145/2505515.2505545Google ScholarDigital Library
- Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6--8, 2002, San Francisco, CA, USA. 623--632. http://dl.acm.org/citation.cfm?id=545381.545464Google ScholarDigital Library
- Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. 2008. 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). ACM, New York, NY, USA, 16--24. https://doi.org/10.1145/1401890.1401898Google ScholarDigital Library
- Suman K. Bera and Amit Chakrabarti. 2017. Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (Leibniz International Proceedings in Informatics (LIPIcs)),, Heribert Vollmer and Brigitte Vallée (Eds.), Vol. 66. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 11:1--11:14. https://doi.org/10.4230/LIPIcs.STACS.2017.11Google ScholarCross Ref
- Jonathan W. Berry, Bruce Hendrickson, Simon Kahan, and Petr Konecny. 2007. Software and Algorithms for Graph Queries on Multithreaded Architectures. In 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), Proceedings, 26--30 March 2007, Long Beach, California, USA. 1--14. https://doi.org/10.1109/IPDPS.2007.370685Google ScholarCross Ref
- Jonathan W. Berry, Bruce Hendrickson, Randall A. LaViolette, and Cynthia A. Phillips. 2011. Tolerating the community detection resolution limit with edge weighting. Phys. Rev. E, Vol. 83 (May 2011), 056119. Issue 5. https://doi.org/10.1103/PhysRevE.83.056119Google ScholarCross Ref
- J. Bondy and M. Simonovits. 1974. Cycles of even length in graphs. Journal of Combinatorial Theory, Series B (1974), 97--105.Google Scholar
- Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. 2013. How Hard Is Counting Triangles in the Streaming Model?. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8--12, 2013, Proceedings, Part I. 244--254. https://doi.org/10.1007/978--3--642--39206--1_21Google ScholarCross Ref
- Joshua Brody and Amit Chakrabarti. 2008. Sublinear communication protocols for multi-party pointer jumping and a related lower bound. arXiv preprint arXiv:0802.2843 (2008).Google Scholar
- Joshua Brody and Mario Sanchez. 2015. Dependent Random Graphs and Multiparty Pointer Jumping. CoRR, Vol. abs/1506.01083 (2015). arxiv: 1506.01083Google Scholar
- Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. 2006. Counting triangles in data streams. In Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26--28, 2006, Chicago, Illinois, USA. 253--262. https://doi.org/10.1145/1142351.1142388Google ScholarDigital Library
- Graham Cormode and Hossein Jowhari. 2014. A second look at counting triangles in graph streams. Theor. Comput. Sci., Vol. 552 (2014), 44--51. https://doi.org/10.1016/j.tcs.2014.07.025Google ScholarCross Ref
- Jean-Pierre Eckmann and Elisha Moses. 2002. Curvature of co-links uncovers hidden thematic layers in the World Wide Web. Proceedings of the National Academy of Sciences, Vol. 99, 9 (2002), 5825--5829. https://doi.org/10.1073/pnas.032093399Google ScholarCross Ref
- emab (http://math.stackexchange.com/users/74964/emab). 2014. Number of triangles in a graph based on number of edges. Mathematics Stack Exchange. URL:http://math.stackexchange.com/q/823650 (version: 2014-06-07).Google Scholar
- David García-Soriano and Konstantin Kutzkov. [n. d.]. Triangle counting in streamed graphs via small vertex covers. In Proceedings of the 2014 SIAM International Conference on Data Mining. 352--360. https://doi.org/10.1137/1.9781611973440.40Google ScholarCross Ref
- Hossein Jowhari and Mohammad Ghodsi. 2005. New Streaming Algorithms for Counting Triangles in Graphs. In Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16--29, 2005, Proceedings. 710--716. https://doi.org/10.1007/11533719_72Google ScholarCross Ref
- John Kallaugher and Eric Price. 2017. A Hybrid Sampling Scheme for Triangle Counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '17). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1778--1797. http://dl.acm.org/citation.cfm?id=3039686.3039802Google ScholarDigital Library
- B. Kalyanasundaram and G. Schintger. 1992. The Probabilistic Communication Complexity of Set Intersection. SIAM Journal on Discrete Mathematics, Vol. 5, 4 (1992), 545--557. https://doi.org/10.1137/0405044Google ScholarDigital Library
- Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. 2012. Counting Arbitrary Subgraphs in Data Streams. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II (ICALP'12). Springer-Verlag, Berlin, Heidelberg, 598--609. https://doi.org/10.1007/978--3--642--31585--5_53Google ScholarDigital Library
- Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, and Charalampos E. Tsourakakis. 2012. Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning. Internet Mathematics, Vol. 8, 1--2 (2012), 161--185. https://doi.org/10.1080/15427951.2012.625260Google ScholarCross Ref
- Ilan Kremer, Noam Nisan, and Dana Ron. 1995. On Randomized One-round Communication Complexity. In Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing (STOC '95). ACM, New York, NY, USA, 596--605. https://doi.org/10.1145/225058.225277Google ScholarDigital Library
- Konstantin Kutzkov and Rasmus Pagh. 2014. Triangle Counting in Dynamic Graph Streams. In Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2--4, 2014. Proceedings. 306--318. https://doi.org/10.1007/978--3--319-08404--6_27Google ScholarCross Ref
- Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. 2008. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, August 24--27, 2008. 462--470. https://doi.org/10.1145/1401890.1401948Google ScholarDigital Library
- Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun. 2011. Approximate Counting of Cycles in Streams. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrü cken, Germany, September 5--9, 2011. Proceedings. 677--688. https://doi.org/10.1007/978--3--642--23719--5_57Google ScholarCross Ref
- Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. 2016. Better Algorithms for Counting Triangles in Data Streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016. 401--411. https://doi.org/10.1145/2902251.2902283Google ScholarDigital Library
- Rasmus Pagh and Charalampos E. Tsourakakis. 2012. Colorful triangle counting and a MapReduce implementation. Inf. Process. Lett., Vol. 112, 7 (2012), 277--281. https://doi.org/10.1016/j.ipl.2011.12.007Google ScholarDigital Library
- A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. 2013. Counting and Sampling Triangles from a Graph Stream. PVLDB, Vol. 6, 14 (2013), 1870--1881. http://www.vldb.org/pvldb/vol6/p1870-aduri.pdfGoogle ScholarDigital Library
- A. A. Razborov. 1992. On the Distributional Complexity of Disjointness. Theor. Comput. Sci., Vol. 106, 2 (Dec. 1992), 385--390. https://doi.org/10.1016/0304--3975(92)90260-MGoogle ScholarDigital Library
- Alexander A. Sherstov. 2014. Communication Lower Bounds Using Directional Derivatives. J. ACM, Vol. 61, 6, Article 34 (Dec. 2014), 71 pages. https://doi.org/10.1145/2629334Google ScholarDigital Library
- Alexander A Sherstov. 2016. The multiparty communication complexity of set disjointness. SIAM J. Comput., Vol. 45, 4 (2016), 1450--1489.Google ScholarDigital Library
- Siddharth Suri and Sergei Vassilvitskii. 2011. Counting triangles and the curse of the last reducer. In Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 - April 1, 2011. 607--614. https://doi.org/10.1145/1963405.1963491Google ScholarDigital Library
- Charalampos E. Tsourakakis, Mihail N. Kolountzakis, and Gary L. Miller. 2011. Triangle Sparsifiers. J. Graph Algorithms Appl., Vol. 15, 6 (2011), 703--726. https://doi.org/10.7155/jgaa.00245Google ScholarCross Ref
- Emanuele Viola and Avi Wigderson. 2009. One-way multiparty communication lower bound for pointer jumping with applications. Combinatorica, Vol. 29, 6 (01 Nov 2009), 719--743. https://doi.org/10.1007/s00493-009--2667-zGoogle ScholarDigital Library
Index Terms
- Triangle and Four Cycle Counting in the Data Stream Model
Recommendations
Contractible elements in k-connected graphs not containing some specified graphs
In [15], Thomassen proved that any triangle-free k-connected graph has a contractible edge. Starting with this result, there are several results concerning the existence of contractible elements in k-connected graphs which do not contain specified ...
Contractible Edges and Triangles in k-Connected Graphs
It is proved that if G is a k-connected graph which does not contain K 4, then G has an edge e or a triangle T such that the graph obtained from G by connecting e or by contracting T is still k-connected. By using this theorem, we prove some theorems ...
On Vertex-Disjoint Triangles in Tripartite Graphs and Multigraphs
AbstractLet G be a tripartite graph with tripartition , where . It is proved that if for every pair of nonadjacent vertices with , then G contains k vertex-disjoint triangles. As a ...
Comments