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 insert-only streams. We present a new algorithm estimating the number of triangles in 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.
This work is supported by the Danish National Research Foundation under the Sapere Aude program.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: PODS 2012, pp. 5–14 (2012)
Aiello, W., Chung, F.R.K., Lu, L.: A random graph model for massive graphs. In: STOC 2000, pp. 171–180 (2000)
Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
Alon, N., Yuster, R., Zwick, U.: Finding and Counting Given Length Cycles. Algorithmica 17(3), 209–223 (1997)
Arbitman, Y., Naor, M., Segev, G.: Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation. In: FOCS 2010, pp. 787–796 (2010)
Backstrom, L., Boldi, P., Rosa, M., Ugander, J., Vigna, S.: Four degrees of separation. In: WebSci 2012, pp. 33–42 (2012)
Berry, J.W., Hendrickson, B., LaViolette, R., Phillips, C.A.: Tolerating the Community Detection Resolution Limit with Edge Weighting. Phys. Rev. E 83(5)
Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: PODS 2006, pp. 253–262 (2006)
Carter, L., Wegman, M.N.: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979)
Dietzfelbinger, M.: Design Strategies for Minimal Perfect Hash Functions. In: Hromkovič, J., Královič, R., Nunkesser, M., Widmayer, P. (eds.) SAGA 2007. LNCS, vol. 4665, pp. 2–17. Springer, Heidelberg (2007)
Frahling, G., Indyk, P., Sohler, C.: Sampling in dynamic data streams and applications. In: Symposium on Computational Geometry 2005, pp. 142–149 (2005)
Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for Lp samplers, finding duplicates in streams, and related problems. In: PODS 2011, pp. 49–58 (2011)
Kane, D.M., Mehlhorn, K., Sauerwald, T., Sun, H.: Counting Arbitrary Subgraphs in Data Streams. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 598–609. Springer, Heidelberg (2012)
Kolountzakis, M.N., Miller, G.L., Peng, R., Tsourakakis, C.E.: Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning. Internet Mathematics 8(1-2), 161–185 (2012)
Leonardi, S.: List of Open Problems in Sublinear Algorithms: Problem 11, http://sublinear.info/11
Manjunath, M., Mehlhorn, K., Panagiotou, K., Sun, H.: Approximate Counting of Cycles in Streams. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 677–688. Springer, Heidelberg (2011)
Muthukrishnan, S.: Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science 1(2) (2005)
Pagh, A., Pagh, R.: Uniform Hashing in Constant Time and Optimal Space. SIAM J. Comput. 38(1), 85–96 (2008)
Pagh, R., Tsourakakis, C.E.: Colorful triangle counting and a MapReduce implementation. Inf. Process. Lett. 112(7), 277–281 (2012)
Pǎtraşcu, M., Thorup, M.: The Power of Simple Tabulation Hashing. J. ACM 59(3), 14 (2012)
Thorup, M., Zhang, Y.: Tabulation based 4-universal hashing with applications to second moment estimation. In: SODA 2004, pp. 615–624 (2004)
Tsourakakis, C.E., Kang, U., Miller, G.L., Faloutsos, C.: DOULION: Counting triangles in massive graphs with a coin. In: KDD 2009, pp. 837–846 (2009)
Tsourakakis, C.E., Kolountzakis, M.N., Miller, G.L.: Triangle Sparsifiers. J. of Graph Algorithms and Appl. 15(6), 703–726 (2011)
Vassilevska Williams, V.: Multiplying matrices faster than Coppersmith-Winograd. In: STOC 2012, pp. 887–898 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Kutzkov, K., Pagh, R. (2014). Triangle Counting in Dynamic Graph Streams. In: Ravi, R., Gørtz, I.L. (eds) Algorithm Theory – SWAT 2014. SWAT 2014. Lecture Notes in Computer Science, vol 8503. Springer, Cham. https://doi.org/10.1007/978-3-319-08404-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-08404-6_27
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08403-9
Online ISBN: 978-3-319-08404-6
eBook Packages: Computer ScienceComputer Science (R0)