{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:25Z","timestamp":1763468245033,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662448991"},{"type":"electronic","value":"9783662449004"}],"license":[{"start":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T00:00:00Z","timestamp":1414972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T00:00:00Z","timestamp":1414972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-44900-4_3","type":"book-chapter","created":{"date-parts":[[2014,11,21]],"date-time":"2014-11-21T16:26:19Z","timestamp":1416587179000},"page":"39-54","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sublinear Algorithms for Extreme-Scale Data Analysis"],"prefix":"10.1007","author":[{"given":"C.","family":"Seshadhri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Thompson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Janine C.","family":"Bennett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,3]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Abbasi, H., Eisenhauer, G., Wolf, M., Schwan, K., Klasky, S.: Just in time: adding value to the IO pipelines of high performance applications with JIT staging. In: Proc. of 20th International Symposium on High Performance Distributed Computing (HPDC\u201911) (2011)","DOI":"10.1145\/1996130.1996137"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Arifuzzaman, S.M., Khan, M., Marathe, M.: PATRIC: A parallel algorithm for counting triangles and computing clustering coefficients in massive networks. NDSSL Technical Report 12-042, Network Dynamics and Simulation Science Laboratory, Virginia Polytechnic Institute and State University (2012)","DOI":"10.1109\/SC.Companion.2012.250"},{"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\u201908, pp. 16\u201324 (2008)","DOI":"10.1145\/1401890.1401898"},{"issue":"12","key":"3_CR4","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1109\/TVCG.2011.199","volume":"17","author":"J. Bennett","year":"2011","unstructured":"Bennett, J., Krishnamoorthy, V., Liu, S., Grout, R., Hawkes, E.R., Chen, J.H., Shepherd, J.,\u00a0Pascucci, V., Bremer, P.-T.: Feature-based statistical analysis of combustion simulation data. IEEE Trans. Vis. Comput. Graph. 17(12), 1822\u20131831 (2011)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Bennett, J.C., Abbasi, H., Bremer, P.-T., Grout, R., Gyulassy, A., Jin, T., Klasky, S., Kolla, H., Parashar, M., Pascucci, V., Pebay, P., Thompson, D., Yu, H., Zhang, F., Chen, J.: Combining in-situ and in-transit processing to enable extreme-scale scientific analysis. In: Hollingsworth, J. (ed.) SC \u201912: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Salt Lake Convention Center, Salt Lake City, 10\u201316 November 2012, pp. 49:1\u201349:9, pub-IEEE:adr. IEEE Computer Society Press (2012)","DOI":"10.1109\/SC.2012.31"},{"key":"3_CR6","volume-title":"Why do simple algorithms for triangle enumeration work in the real world? In: Innovations in Theoretical Computer Science (ITCS)","author":"J. Berry","year":"2014","unstructured":"Berry, J., Fostvedt, L., Nordman, D., Phillips, C., Seshadhri, C., Wilson, A.: Why do simple algorithms for triangle enumeration work in the real world? In: Innovations in Theoretical Computer Science (ITCS) (2014)"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The web graph framework I: compression techniques. In: Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), Manhattan,, pp. 595\u2013601. ACM Press, New York (2004)","DOI":"10.1145\/988672.988752"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., Santini, M., Vigna, S.: Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In: Proceedings of the 20th International Conference on World Wide Web. ACM Press, Madrid (2011)","DOI":"10.1145\/1963405.1963488"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Buriol, L., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: PODS\u201906, pp. 253\u2013262 (2006)","DOI":"10.1145\/1142351.1142388"},{"issue":"2","key":"3_CR10","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1086\/421787","volume":"110","author":"R.S. Burt","year":"2004","unstructured":"Burt, R.S.: Structural holes and good ideas. Am. J. Sociol. 110(2), 349\u2013399 (2004)","journal-title":"Am. J. Sociol."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1088\/1749-4699\/2\/1\/015001","volume":"2","author":"J.H. Chen","year":"2009","unstructured":"Chen, J.H., Choudhary, A., de\u00a0Supinski, B., DeVries, M., Hawkes, E.R., Klasky, S., Liao, W.K., Ma, K.L., Mellor-Crummey, J., Podhorski, N., Sankaran, R., Shende, S., Yoo, C.S.: Terascale direct numerical simulations of turbulent combustion using s3d. Comput. Sci. Discov. 2, 1\u201331 (2009)","journal-title":"Comput. Sci. Discov."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1109\/MCSE.2009.120","volume":"11","author":"J. Cohen","year":"2009","unstructured":"Cohen, J.: Graph twiddling in a MapReduce world. Comput. Sci. Eng. 11, 29\u201341 (2009)","journal-title":"Comput. Sci. Eng."},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"S95","DOI":"10.1086\/228943","volume":"94","author":"J.S. Coleman","year":"1988","unstructured":"Coleman, J.S.: Social capital in the creation of human capital. Am. J. Sociol. 94, S95\u2013S120 (1988)","journal-title":"Am. J. Sociol."},{"key":"3_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D. Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York (2009)"},{"issue":"9","key":"3_CR15","doi-asserted-by":"publisher","first-page":"5825","DOI":"10.1073\/pnas.032093399","volume":"99","author":"J.-P. Eckmann","year":"2002","unstructured":"Eckmann, J.-P., Moses, E.: Curvature of co-links uncovers hidden thematic layers in the World Wide Web. PNAS 99(9), 5825\u20135829 (2002)","journal-title":"PNAS"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Fabian, N., Moreland, K., Thompson, D., Bauer, A.C., Marion, P., Gevecik, B., Rasquin, M., Jansen, K.E.: The paraview coprocessing library: a scalable, general purpose in situ visualization library. In: Proc. of IEEE Symposium on Large Data Analysis and Visualization (LDAV), pp. 89\u201396 (2011)","DOI":"10.1109\/LDAV.2011.6092322"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"026107","DOI":"10.1103\/PhysRevE.76.026107","volume":"76","author":"G. Fagiolo","year":"2007","unstructured":"Fagiolo, G.: Clustering in complex directed networks. Phys. Rev. E 76, 026107 (2007)","journal-title":"Phys. Rev. E"},{"key":"3_CR18","unstructured":"Favre, J.M., Whitlock, B., Meredith, J.S.: Parallel in situ coupling of simulation with a fully featured visualization system. In: Proc. of 11th Eurographics Symposium on Parallel Graphics and Visualization (EGPGV\u201911) (2011)"},{"key":"3_CR19","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: a primer to property testing. Bull. EATCS 75, 97\u2013126 (2001)","journal-title":"Bull. EATCS"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Foucault\u00a0Welles, B., Van\u00a0Devender, A., Contractor, N.: Is a friend a friend?: Investigating the structure of friendship networks in virtual worlds. In: CHI-EA\u201910, pp. 4027\u20134032 (2010)","DOI":"10.1145\/1753846.1754097"},{"key":"3_CR21","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. ECCC, TR00-020 (2000)"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Gonen, M., Ron, D., Shavitt, Y.: Counting stars and other small subgraphs in sublinear time. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 99\u2013116 (2010)","DOI":"10.1137\/1.9781611973075.10"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1086\/224954","volume":"76","author":"P.W. Holland","year":"1970","unstructured":"Holland, P.W., Leinhardt, S.: A method for detecting structure in sociometric data. Am. J.\u00a0Sociol. 76, 492\u2013513 (1970)","journal-title":"Am. J. Sociol."},{"key":"3_CR25","unstructured":"Kolda, T.G., Pinar, A., Plantenga, T., Seshadhri, C., Task, C.: Counting triangles in massive graphs with mapreduce. Technical Report 1301.5887, arxiv (2013)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Kolountzakis, M., Miller, G., Peng, R., Tsourakakis, C.: Efficient triangle counting in large graphs via degree-based vertex partitioning. In: WAW\u201910 (2010)","DOI":"10.1007\/978-3-642-18009-5_3"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-15014-2_19","volume-title":"Topological Methods in Data Analysis and Visualization. Mathematics and Visualization","author":"A. Mascarenhas","year":"2011","unstructured":"Mascarenhas, A., Grout, R.W., Bremer, P.-T., Hawkes, E.R., Pascucci, V., Chen, J.H.: Topological feature extraction for comparison of terascale combustion simulation data. In: Pascucci, V., Tricoche, X., Hagen, H., Tierny, J. (eds.) Topological Methods in Data Analysis and Visualization. Mathematics and Visualization, pp. 229\u2013240. Springer, Berlin\/Heidelberg (2011)"},{"issue":"5594","key":"3_CR28","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R. Milo","year":"2011","unstructured":"Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: Simple building blocks of complex networks. Science 298(5594), 824\u2013827 (2011)","journal-title":"Science"},{"issue":"2","key":"3_CR29","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D. Ron","year":"2009","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci. 5(2), 73\u2013205 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"3_CR30","volume-title":"Sublinear time algorithms","author":"R. Rubinfeld","year":"2006","unstructured":"Rubinfeld, R.: Sublinear time algorithms. In: International Conference of Mathematicians (2006)"},{"key":"3_CR31","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25, 647\u2013668 (1996)","journal-title":"SIAM J. Comput."},{"key":"3_CR32","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. J. Graph Algorithms Appl. 9, 265\u2013275 (2005)","journal-title":"J. Graph Algorithms Appl."},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Schank, T., Wagner, D.: Finding, counting and listing all triangles in large graphs, an experimental study. In: Experimental and Efficient Algorithms, pp. 606\u2013609. Springer, Berlin (2005)","DOI":"10.1007\/11427186_54"},{"key":"3_CR34","unstructured":"Seshadhri, C., Pinar, A., Durak, N., Kolda, T.G.: Directed closure measures for networks with reciprocity. arXiv:1302.6220 (2013)"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Seshadhri, C., Pinar, A., Kolda, T.G.: Triadic measures on graphs: the power of wedge sampling. In: Proceedings of the SIAM Conference on Data Mining (SDM) (2013)","DOI":"10.1137\/1.9781611972832.2"},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"Seshadhri, C., Pinar, A., Kolda, T.G.: Wedge sampling for computing clustering coefficients and triangle counts on large graphs. arXiv:1309.3321 (2013)","DOI":"10.1002\/sam.11224"},{"issue":"4","key":"3_CR37","doi-asserted-by":"publisher","first-page":"e33918","DOI":"10.1371\/journal.pone.0033918","volume":"7","author":"S. Son","year":"2012","unstructured":"Son, S., Kang, A., Kim, H., Kwon, T., Park, J., Kim, H.: Analysis of context dependence in social interaction networks of a massively multiplayer online role-playing game. PLoS ONE 7(4), e33918 (2012)","journal-title":"PLoS ONE"},{"key":"3_CR38","doi-asserted-by":"crossref","unstructured":"Suri, S., Vassilvitskii, S.: Counting triangles and the curse of the last reducer. In: WWW\u201911, pp. 607\u2013614 (2011)","DOI":"10.1145\/1963405.1963491"},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.socnet.2010.06.001","volume":"32","author":"M. Szell","year":"2010","unstructured":"Szell, M., Thurner, S.: Measuring social dynamics in a massive multiplayer online game. Soc. Netw. 32, 313\u2013329 (2010)","journal-title":"Soc. Netw."},{"key":"3_CR40","doi-asserted-by":"publisher","first-page":"13636","DOI":"10.1073\/pnas.1004008107","volume":"107","author":"M. Szell","year":"2010","unstructured":"Szell, M., Lambiotte, R., Thurner, S.: Multirelational organization of large-scale social networks in an online world. Proc. Natl. Acad. Sci 107, 13636\u201313641 (2010)","journal-title":"Proc. Natl. Acad. Sci"},{"key":"3_CR41","doi-asserted-by":"crossref","unstructured":"Thompson, D., Bennett, J., Seshadhri, C., Pinar, A.: A provably-robust sampling method for generating colormaps of large data. In: Proceedings of the IEEE Symposium on Large Data Analysis and Visualization (LDAV), Atlanta (2013)","DOI":"10.1109\/LDAV.2013.6675161"},{"key":"3_CR42","first-page":"608","volume":"2008","author":"C.E. Tsourakakis","year":"2008","unstructured":"Tsourakakis, C.E.: Fast counting of triangles in large real networks, without counting: algorithms and laws. In: ICDM 2008, pp. 608\u2013617 (2008)","journal-title":"In: ICDM"},{"key":"3_CR43","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C., Drineas, P., Michelakis, E., Koutis, I., Faloutsos, C.: Spectral counting of triangles in power-law networks via element-wise sparsification. In: ASONAM\u201909, pp. 66\u201371 (2009)","DOI":"10.1109\/ASONAM.2009.32"},{"key":"3_CR44","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 \u201909, pp. 837\u2013846 (2009)","DOI":"10.1145\/1557019.1557111"},{"key":"3_CR45","doi-asserted-by":"publisher","first-page":"703","DOI":"10.7155\/jgaa.00245","volume":"15","author":"C. Tsourakakis","year":"2011","unstructured":"Tsourakakis, C., Kolountzakis, M.N., Miller, G.: Triangle sparsifiers. J. Graph Algorithms Appl. 15, 703\u2013726 (2011)","journal-title":"J. Graph Algorithms Appl."},{"key":"3_CR46","doi-asserted-by":"crossref","unstructured":"Vishwanath, V., Hereld, M., Papka, M.E.: Toward simulation-time data analysis and i\/o acceleration on leadership-class systems. In: Proc. of IEEE Symposium on Large Data Analysis and Visualization (LDAV) (2011)","DOI":"10.1109\/LDAV.2011.6092178"},{"key":"3_CR47","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis: Methods and Applications","author":"S. Wasserman","year":"1994","unstructured":"Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge (1994)"},{"key":"3_CR48","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D. Watts","year":"1998","unstructured":"Watts, D., Strogatz, S.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 440\u2013442 (1998)","journal-title":"Nature"},{"key":"3_CR49","first-page":"45","volume":"30","author":"W. Yu","year":"2010","unstructured":"Yu, W., Wang, C., Grout, R.W., Chen, J.H., Ma, K.-L.: In-situ visualization for large-scale combustion simulations. IEEE Comput. Graph. Appl. 30, 45\u201357 (2010)","journal-title":"IEEE Comput. Graph. Appl."}],"container-title":["Mathematics and Visualization","Topological and Statistical Methods for Complex Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44900-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T15:49:50Z","timestamp":1674834590000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-44900-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,3]]},"ISBN":["9783662448991","9783662449004"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44900-4_3","relation":{},"ISSN":["1612-3786","2197-666X"],"issn-type":[{"type":"print","value":"1612-3786"},{"type":"electronic","value":"2197-666X"}],"subject":[],"published":{"date-parts":[[2014,11,3]]},"assertion":[{"value":"3 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}