{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T07:21:29Z","timestamp":1753600889306,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642180088"},{"type":"electronic","value":"9783642180095"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-18009-5_3","type":"book-chapter","created":{"date-parts":[[2010,12,2]],"date-time":"2010-12-02T10:31:28Z","timestamp":1291285888000},"page":"15-24","source":"Crossref","is-referenced-by-count":13,"title":["Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning"],"prefix":"10.1007","author":[{"given":"Mihail N.","family":"Kolountzakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charalampos E.","family":"Tsourakakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N. Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and Counting Given Length Cycles. Algorithmica\u00a017(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"unstructured":"Avron, H.: Counting triangles in large graphs using randomized matrix trace estimation. In: Proceedings of KDD-LDMTA 2010 (2010)","key":"3_CR2"},{"unstructured":"Bar-Yosseff, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA (2002)","key":"3_CR3"},{"doi-asserted-by":"crossref","unstructured":"Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient Semi-Streaming Algorithms for Local Triangle Counting in Massive Graphs. In: KDD (2008)","key":"3_CR4","DOI":"10.1145\/1401890.1401898"},{"doi-asserted-by":"crossref","unstructured":"Buriol, L., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting Triangles in Data Streams. In: PODS (2006)","key":"3_CR5","DOI":"10.1145\/1142351.1142388"},{"issue":"3","key":"3_CR6","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1214\/aop\/1176994428","volume":"9","author":"H. Chernoff","year":"1981","unstructured":"Chernoff, H.: A Note on an Inequality Involving the Normal Distribution. Annals of Probability\u00a09(3), 533\u2013535 (1981)","journal-title":"Annals of Probability"},{"key":"3_CR7","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/107","volume-title":"Complex Graphs and Networks","author":"F. Chung","year":"2006","unstructured":"Chung, F., Lu, L.: Complex Graphs and Networks, vol.\u00a0(107). American Mathematical Society, Providence (2006)"},{"doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: STOC (1987)","key":"3_CR8","DOI":"10.1145\/28395.28396"},{"unstructured":"Jeffrey, D., Ghemawat, S.: MapReduce: Simplified Data Processing on Large Clusters. In: OSDI (2004)","key":"3_CR9"},{"doi-asserted-by":"crossref","unstructured":"Eckmann, J.-P., Moses, E.: Curvature of co-links uncovers hidden thematic layers in the World Wide Web. In: PNAS (2002)","key":"3_CR10","DOI":"10.1073\/pnas.032093399"},{"issue":"395","key":"3_CR11","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1080\/01621459.1986.10478342","volume":"81","author":"O. Frank","year":"1986","unstructured":"Frank, O., Strauss, D.: Markov Graphs. Journal of the American Statistical Association\u00a081(395), 832\u2013842 (1986)","journal-title":"Journal of the American Statistical Association"},{"issue":"2","key":"3_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Journal of Theoretical Computer Science\u00a0348(2), 207\u2013216 (2005)","journal-title":"Journal of Theoretical Computer Science"},{"key":"3_CR13","first-page":"601","volume-title":"Combinatorial Theory and Its Applications","author":"A. Hajnal","year":"1970","unstructured":"Hajnal, A., Szemer\u00e9di, E.: Proof of a Conjecture of Erds. In: Combinatorial Theory and Its Applications, vol.\u00a02, pp. 601\u2013623. North-Holland, Amsterdam (1970)"},{"doi-asserted-by":"crossref","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. In: STOC (1977)","key":"3_CR14","DOI":"10.1145\/800105.803390"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. Johnson","year":"1984","unstructured":"Johnson, W., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/11533719_72","volume-title":"Computing and Combinatorics","author":"H. Jowhari","year":"2005","unstructured":"Jowhari, H., Ghodsi, M.: New Streaming Algorithms for Counting Triangles in Graphs. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 710\u2013716. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Kang, U., Tsourakakis, C., Appel, A.P., Faloutsos, C., Leskovec, J.: Radius Plots for Mining Tera-byte Scale Graphs: Algorithms, Patterns, and Observations. In: SIAM Data Mining, SDM 2010 (2010)","key":"3_CR17","DOI":"10.1137\/1.9781611972801.48"},{"doi-asserted-by":"crossref","unstructured":"Kang, U., Tsourakakis, C., Faloutsos, C.: PEGASUS: A Peta-Scale Graph Mining System. In: IEEE Data Mining, ICDM 2009 (2009)","key":"3_CR18","DOI":"10.1109\/ICDM.2009.14"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s004930070014","volume":"20","author":"J.H. Kim","year":"2000","unstructured":"Kim, J.H., Vu, V.H.: Concentration of multivariate polynomials and its applications. Combinatorica\u00a020(3), 417\u2013434 (2000)","journal-title":"Combinatorica"},{"key":"3_CR20","volume-title":"Seminumerical Algorithms","author":"D. Knuth","year":"1997","unstructured":"Knuth, D.: Seminumerical Algorithms, 3rd edn. Addison-Wesley Professional, Reading (1997)","edition":"3"},{"unstructured":"Kolountzakis, M., Miller, G.L., Peng, R., Tsourakakis, C.E.: Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning, \n                  \n                    http:\/\/arxiv.org\/abs\/1011.0468","key":"3_CR21"},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.tcs.2008.07.017","volume":"407","author":"M. Latapy","year":"2008","unstructured":"Latapy, M.: Main-memory triangle computations for very large (sparse (power-law)) graphs. Theor. Comput. Sci.\u00a0407, 458\u2013473 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/978-3-540-85363-3_41","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Magen","year":"2008","unstructured":"Magen, A., Zouzias, A.: Near Optimal Dimensionality Reductions That Preserve Volumes. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 523\u2013534. Springer, Heidelberg (2008)"},{"doi-asserted-by":"crossref","unstructured":"Mislove, A., Massimiliano, M., Gummadi, K., Druschel, P., Bhattacharjee, B.: Measurement and Analysis of Online Social Networks. In: IMC (2007)","key":"3_CR24","DOI":"10.1145\/1298306.1298311"},{"doi-asserted-by":"crossref","unstructured":"Newman, M.: The structure and function of complex networks (2003)","key":"3_CR25","DOI":"10.1137\/S003614450342480"},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(81)90041-7","volume":"13","author":"C. Papadimitriou","year":"1981","unstructured":"Papadimitriou, C., Yannakakis, M.: The clique problem for planar graphs. Information Processing Letters\u00a013, 131\u2013133 (1981)","journal-title":"Information Processing Letters"},{"key":"3_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/11427186_54","volume-title":"Experimental and Efficient Algorithms","author":"T. Schank","year":"2005","unstructured":"Schank, T., Wagner, D.: Finding, Counting and Listing all Triangles in Large Graphs, An Experimental Study. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 606\u2013609. Springer, Heidelberg (2005)"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"265","DOI":"10.7155\/jgaa.00108","volume":"9","author":"T. Schank","year":"2005","unstructured":"Schank, T., Wagner, D.: Approximating Clustering Coefficient and Transitivity. Journal of Graph Algorithms and Applications\u00a09, 265\u2013275 (2005)","journal-title":"Journal of Graph Algorithms and Applications"},{"doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E.: Fast Counting of Triangles in Large Real Networks, without counting: Algorithms and Laws. In: ICDM (2008)","key":"3_CR29","DOI":"10.1109\/ICDM.2008.72"},{"unstructured":"Tsourakakis, C.E.: Counting Triangles Using Projections. KAIS Journal (2010)","key":"3_CR30"},{"doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Kang, U., Miller, G.L., Faloutsos, C.: Doulion: Counting Triangles in Massive Graphs with a Coin. In: KDD (2009)","key":"3_CR31","DOI":"10.1145\/1557019.1557111"},{"unstructured":"Tsourakakis, C.E., Kolountzakis, M., Miller, G.L.: Approximate Triangle Counting (Preprint), \n                  \n                    http:\/\/arxiv.org\/abs\/0904.3761","key":"3_CR32"},{"doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Drineas, P., Michelakis, E., Koutis, I., Faloutsos, C.: Spectral Counting of Triangles via Element-Wise Sparsification and Triangle-Based Link Recommendation. In: ASONAM (2010)","key":"3_CR33","DOI":"10.1109\/ASONAM.2009.32"},{"issue":"4","key":"3_CR34","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1002\/1098-2418(200007)16:4<344::AID-RSA4>3.0.CO;2-5","volume":"16","author":"V.H. Vu","year":"2000","unstructured":"Vu, V.H.: On the concentration of multivariate polynomials with small expectation. Random Structures and Algorithms\u00a016(4), 344\u2013363 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"3_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis : Methods and Applications (Structural Analysis in the Social Sciences)","author":"S. Wasserman","year":"1994","unstructured":"Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences). Cambridge University Press, Cambridge (1994)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Models for the Web-Graph"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18009-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T19:20:41Z","timestamp":1558293641000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18009-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642180088","9783642180095"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18009-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}