{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:08:05Z","timestamp":1743152885784,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319639628"},{"type":"electronic","value":"9783319639628"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-63962-8_59-1","type":"book-chapter","created":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T05:21:16Z","timestamp":1519795276000},"page":"1-7","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Degrees of Separation and Diameter in Large Graphs"],"prefix":"10.1007","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,14]]},"reference":[{"key":"59-1_CR1","doi-asserted-by":"crossref","unstructured":"Abboud A, Williams VV, Wang JR (2016) Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, 10\u201312 Jan, pp 377\u2013391","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"59-1_CR2","doi-asserted-by":"crossref","unstructured":"Akiba T, Iwata Y, Kawata Y (2015) An exact algorithm for diameters of large real directed graphs. In: Experimental algorithms \u2013 proceedings of 14th international symposium, SEA 2015, Paris, 29 June\u20131 July 2015, pp 56\u201367","DOI":"10.1007\/978-3-319-20086-6_5"},{"key":"59-1_CR3","doi-asserted-by":"crossref","unstructured":"Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S (2012) Four degrees of separation. In: Web science 2012, WebSci\u201912, Evanston, 22\u201324 June 2012, pp 33\u201342","DOI":"10.1145\/2380718.2380723"},{"key":"59-1_CR4","first-page":"595","volume-title":"Proceedings of the 13th international world wide web conference","author":"P Boldi","year":"2003","unstructured":"Boldi P, Vigna S (2003) The webgraph framework I: compression techniques. In: Proceedings of the 13th international world wide web conference. ACM, Manhattan, pp 595\u2013601"},{"key":"59-1_CR5","doi-asserted-by":"crossref","unstructured":"Boldi P, Rosa M, Vigna S (2011) Hyperanf: approximating the neighbourhood function of very large graphs on a budget. In: Proceedings of the 20th international conference on world wide web, WWW 2011, Hyderabad, 28 Mar\u20131 Apr 2011, pp 625\u2013634","DOI":"10.1145\/1963405.1963493"},{"key":"59-1_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.tcs.2015.02.033","volume":"586","author":"M Borassi","year":"2015","unstructured":"Borassi M, Crescenzi P, Habib M, Kosters WA, Marino A, Takes FW (2015) Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: with an application to the six degrees of separation games. Theor Comput Sci 586:59\u201380","journal-title":"Theor Comput Sci"},{"key":"59-1_CR7","doi-asserted-by":"crossref","unstructured":"Borassi M, Crescenzi P, Trevisan L (2017) An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. In: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Hotel Porta Fira, 16\u201319 Jan, pp 920\u2013939","DOI":"10.1137\/1.9781611974782.58"},{"key":"59-1_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/b106453","volume-title":"Network analysis: methodological foundations","author":"U Brandes","year":"2005","unstructured":"Brandes U (2005) Network analysis: methodological foundations, vol 3418. Springer Science & Business Media, Berlin"},{"issue":"7","key":"59-1_CR9","doi-asserted-by":"publisher","first-page":"2303","DOI":"10.1142\/S0218127407018403","volume":"17","author":"U Brandes","year":"2007","unstructured":"Brandes U, Pich C (2007) Centrality estimation in large networks. Int J Bifurcation Chaos 17(7):2303\u20132318","journal-title":"Int J Bifurcation Chaos"},{"key":"59-1_CR10","unstructured":"Broder AZ (1997) On the resemblance and containment of documents. In: In compression and complexity of sequences (SEQUENCES\u201997). IEEE Computer Society, pp 21\u201329"},{"key":"59-1_CR11","doi-asserted-by":"crossref","unstructured":"Cairo M, Grossi R, Rizzi R (2016) New bounds for approximating extremal distances in undirected graphs. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, 10\u201312 Jan 2016, pp 363\u2013376","DOI":"10.1137\/1.9781611974331.ch27"},{"key":"59-1_CR12","first-page":"190","volume":"35","author":"E Cohen","year":"1994","unstructured":"Cohen E (1994) Estimating the size of the transitive closure in linear time. Annu IEEE Symp Found Comput Sci 35:190\u2013200","journal-title":"Annu IEEE Symp Found Comput Sci"},{"issue":"3","key":"59-1_CR13","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E Cohen","year":"1997","unstructured":"Cohen E (1997) Size-estimation framework with applications to transitive closure and reachability. J Comput Syst Sci 55(3):441\u2013453","journal-title":"J Comput Syst Sci"},{"issue":"9","key":"59-1_CR14","doi-asserted-by":"publisher","first-page":"2320","DOI":"10.1109\/TKDE.2015.2411606","volume":"27","author":"E Cohen","year":"2015","unstructured":"Cohen E (2015) All-distances sketches, revisited: HIP estimators for massive graphs analysis. IEEE Trans Knowl Data Eng 27(9):2320\u20132334","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"59-1_CR15","doi-asserted-by":"crossref","unstructured":"Cohen E, Kaplan H (2007a) Bottom-k sketches: better and more efficient estimation of aggregates. In: ACM SIGMETRICS performance evaluation review, vol 35. ACM, pp 353\u2013354","DOI":"10.1145\/1269899.1254926"},{"key":"59-1_CR16","first-page":"225","volume-title":"Summarizing data using bottom-k sketches","author":"E Cohen","year":"2007","unstructured":"Cohen E, Kaplan H (2007b) Summarizing data using bottom-k sketches. In: PODC, pp 225\u2013234"},{"issue":"1","key":"59-1_CR17","first-page":"213","volume":"1","author":"E Cohen","year":"2008","unstructured":"Cohen E, Kaplan H (2008) Tighter estimation using bottom k sketches. PVLDB 1(1):213\u2013224","journal-title":"PVLDB"},{"key":"59-1_CR18","unstructured":"Crescenzi P, Grossi R, Imbrenda C, Lanzi L, Marino A (2010) Finding the diameter in real-world graphs: experimentally turning a lower bound into an upper bound. In: Proceeding ESA. LNCS, vol 6346, pp 302\u2013313"},{"key":"59-1_CR19","doi-asserted-by":"crossref","unstructured":"Crescenzi P, Grossi R, Lanzi L, Marino A (2011) A comparison of three algorithms for approximating the distance distribution in real-world graphs. In: Theory and practice of algorithms in (computer) systems \u2013 proceedings of first international ICST conference, TAPAS 2011, Rome, 18\u201320 Apr 2011, pp 92\u2013103","DOI":"10.1007\/978-3-642-19754-3_11"},{"key":"59-1_CR20","doi-asserted-by":"crossref","unstructured":"Crescenzi P, Grossi R, Lanzi L, Marino A (2012) On computing the diameter of real-world directed (weighted) graphs. In: Experimental algorithms \u2013 proceedings of 11th international symposium, SEA 2012, Bordeaux, 7\u20139 June 2012, pp 99\u2013110","DOI":"10.1007\/978-3-642-30850-5_10"},{"key":"59-1_CR21","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.tcs.2012.09.018","volume":"514","author":"P Crescenzi","year":"2013","unstructured":"Crescenzi P, Grossi R, Habib M, Lanzi L, Marino A (2013) On computing the diameter of real-world undirected graphs. Theor Comput Sci 514:84\u201395","journal-title":"Theor Comput Sci"},{"key":"59-1_CR22","first-page":"228","volume-title":"Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms, SODA\u201901","author":"D Eppstein","year":"2001","unstructured":"Eppstein D, Wang J (2001) Fast approximation of centrality. In: Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms, SODA\u201901. Society for Industrial and Applied Mathematics, Philadelphia, pp 228\u2013229"},{"issue":"2","key":"59-1_CR23","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P Flajolet","year":"1985","unstructured":"Flajolet P, Martin G (1985) Probabilistic counting algorithms for data base applications. J Comput Syst Sci 31(2):182\u2013209","journal-title":"J Comput Syst Sci"},{"key":"59-1_CR24","doi-asserted-by":"crossref","unstructured":"Flajolet P, \u00c9ric Fusy, Gandouet O et al (2007) Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In: Proceedings of the 2007 international conference on analysis of algorithms, INAOFA\u201907","DOI":"10.46298\/dmtcs.3545"},{"issue":"301","key":"59-1_CR25","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Am Stat Assoc 58(301):13\u201330","journal-title":"J Am Stat Assoc"},{"issue":"4","key":"59-1_CR26","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512\u2013530","journal-title":"J Comput Syst Sci"},{"key":"59-1_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1412228.1455266","volume":"13","author":"C Magnien","year":"2009","unstructured":"Magnien C, Latapy M, Habib M (2009) Fast computation of empirically tight bounds for the diameter of massive graphs. J Exp Algorithmics 13:1\u201310","journal-title":"J Exp Algorithmics"},{"key":"59-1_CR28","doi-asserted-by":"crossref","unstructured":"Palmer CR, Gibbons PB, Faloutsos C (2002) ANF: a fast and scalable tool for data mining in massive graphs. In: Proceedings of the 8th ACM SIGKDD international conference on knowledge discovery and data mining, pp 81\u201390","DOI":"10.1145\/775047.775059"},{"key":"59-1_CR29","doi-asserted-by":"crossref","unstructured":"Roditty L, Williams VV (2013) Fast approximation algorithms for the diameter and radius of sparse graphs. In: Symposium on theory of computing conference, STOC\u201913, Palo Alto, 1\u20134 June 2013, pp 515\u2013524","DOI":"10.1145\/2488608.2488673"}],"container-title":["Encyclopedia of Big Data Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-63962-8_59-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T00:01:13Z","timestamp":1660521673000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-63962-8_59-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319639628","9783319639628"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-63962-8_59-1","relation":{},"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"14 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}