{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:26:15Z","timestamp":1743110775743,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031434174"},{"type":"electronic","value":"9783031434181"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-43418-1_40","type":"book-chapter","created":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T09:02:26Z","timestamp":1694854946000},"page":"671-688","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["propagate: A Seed Propagation Framework to\u00a0Compute Distance-Based Metrics on\u00a0Very Large Graphs"],"prefix":"10.1007","author":[{"given":"Giambattista","family":"Amati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Cruciani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Pasquini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paola","family":"Vocca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simone","family":"Angelini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,17]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18\u201321 October 2014. IEEE Computer Society (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"40_CR2","doi-asserted-by":"publisher","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167\u20131181 (1999). https:\/\/doi.org\/10.1137\/S0097539796303421","DOI":"10.1137\/S0097539796303421"},{"key":"40_CR3","unstructured":"Amati, G., Angelini, S., Capri, F., Gambosi, G., Rossi, G., Vocca, P.: Modelling the temporal evolution of the retweet graph. IADIS Int. J. Comput. Sci. Inf. Syst. 11(2), 19\u201330 (2016). ISSN 1646-3692"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Amati, G., Angelini, S., Gambosi, G., Rossi, G., Vocca, P.: Estimation of distance-based metrics for very large graphs with minhash signatures. In: Proceedings of 2017 IEEE International Conference on Big Data. IEEE (2017)","DOI":"10.1109\/BigData.2017.8257969"},{"key":"40_CR5","doi-asserted-by":"publisher","unstructured":"Amati, G., Cruciani, A., Pasquini, D., Vocca, P., Angelini, S.: Propagate: a seed propagation framework to compute distance-based metrics on very large graphs. CoRR (2023). https:\/\/doi.org\/10.48550\/arXiv.2301.06499","DOI":"10.48550\/arXiv.2301.06499"},{"key":"40_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45726-7_1","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"Z Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D., Trevisan, L.: Counting distinct elements in a data stream. In: Rolim, J.D.P., Vadhan, S. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 1\u201310. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45726-7_1"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., Vigna, S.: HyperANF: approximating the neighbourhood function of very large graphs on a budget. In: Proceedings of 20th International Conference on World Wide Web, Hyderabad, India, pp. 625\u2013634 (2011)","DOI":"10.1145\/1963405.1963493"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The WebGraph framework I: compression techniques. In: Proceedings of the Thirteenth International World Wide Web Conference (WWW 2004), Manhattan, USA, pp. 595\u2013601. ACM Press (2004)","DOI":"10.1145\/988672.988752"},{"key":"40_CR9","unstructured":"Boldi, P., Vigna, S.: LAW datasets: laboratory for web algorithmics (2022). https:\/\/law.di.unimi.it\/datasets.php"},{"key":"40_CR10","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, W.A., Marino, A., Takes, F.W.: Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs. Theor. Comput. Sci. 586, 59\u201380 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"40_CR11","unstructured":"Casella, G., Berger, R.: Statistical Inference. Duxbury Resource Center (2001)"},{"key":"40_CR12","doi-asserted-by":"publisher","unstructured":"Ceccarello, M., Pietracaprina, A., Pucci, G., Upfal, E.: Distributed graph diameter approximation. Algorithms 13, 216 (2020). https:\/\/doi.org\/10.3390\/a13090216","DOI":"10.3390\/a13090216"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Chechik, S., Larkin, D.H., Roditty, L., Schoenebeck, G., Tarjan, R.E., Williams, V.V.: Better approximation algorithms for the graph diameter. In: Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 1041\u20131052. Society for Industrial and Applied Mathematics, Philadelphia (2014). https:\/\/dl.acm.org\/citation.cfm?id=2634074.2634152","DOI":"10.1137\/1.9781611973402.78"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Epasto, A., Kumar, R., Lattanzi, S., Mirrokni, V.S.: Efficient algorithms for public-private social networks. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 10\u201313 August 2015 (2015)","DOI":"10.1145\/2783258.2783354"},{"issue":"3","key":"40_CR15","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E Cohen","year":"1997","unstructured":"Cohen, E.: Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. 55(3), 441\u2013453 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Cohen, E.: All-distances sketches, revisited: hip estimators for massive graphs analysis. In: Proceedings of 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Snowbird, Utah, USA, pp. 88\u201399 (2014)","DOI":"10.1145\/2594538.2594546"},{"issue":"3","key":"40_CR17","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"40_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-642-19754-3_11","volume-title":"Theory and Practice of Algorithms in (Computer) Systems","author":"P Crescenzi","year":"2011","unstructured":"Crescenzi, P., Grossi, R., Lanzi, L., Marino, A.: A comparison of three algorithms for approximating the distance distribution in real-world graphs. In: Marchetti-Spaccamela, A., Segal, M. (eds.) TAPAS 2011. LNCS, vol. 6595, pp. 92\u2013103. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19754-3_11"},{"key":"40_CR19","doi-asserted-by":"publisher","unstructured":"Cygan, M., Gabow, H.N., Sankowski, P.: Algorithmic applications of baur-strassen\u2019s theorem: shortest cycles, diameter, and matchings. J. ACM 62(4), 28:1\u201328:30 (2015). https:\/\/doi.org\/10.1145\/2736283. https:\/\/doi.acm.org\/10.1145\/2736283","DOI":"10.1145\/2736283"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Dalirrooyfard, M., Wein, N.: Tight conditional lower bounds for approximating diameter in directed graphs. In: STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, 21\u201325 June 2021. ACM (2021)","DOI":"10.1145\/3406325.3451130"},{"key":"40_CR21","doi-asserted-by":"crossref","unstructured":"Durand, M., Flajolet, P.: Loglog counting of large cardinalities (extended abstract). In: Proceedings of 11th Annual European Symposium (ESA), Budapest, pp. 605\u2013617 (2003)","DOI":"10.1007\/978-3-540-39658-1_55"},{"key":"40_CR22","unstructured":"Eppstein, D., Wang, J.: Fast approximation of centrality. In: Proceedings of 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, D.C., USA, pp. 228\u2013229 (2001)"},{"key":"40_CR23","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Fusy, \u00c9., Gandouet, O., Meunier, F.: Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In: Analysis of Algorithms, pp. 137\u2013156. Discrete Mathematics and Theoretical Computer Science (2007)","DOI":"10.46298\/dmtcs.3545"},{"issue":"2","key":"40_CR24","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.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31(2), 182\u2013209 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"40_CR25","doi-asserted-by":"publisher","unstructured":"Fortunato, S., Latora, V., Marchiori, M.: Method to find community structures based on information centrality. Phys. Rev. E 70(5 Pt 2), 056104 (2004). https:\/\/doi.org\/10.1103\/PhysRevE.70.056104","DOI":"10.1103\/PhysRevE.70.056104"},{"key":"40_CR26","doi-asserted-by":"crossref","unstructured":"Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821\u20137826 (2002)","DOI":"10.1073\/pnas.122653799"},{"key":"40_CR27","doi-asserted-by":"crossref","unstructured":"Heule, S., Nunkesser, M., Hall, A.: Hyperloglog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. In: Proceedings of the 16th International Conference on Extending Database Technology (EDBT), Genoa, pp. 683\u2013692 (2013)","DOI":"10.1145\/2452376.2452456"},{"key":"40_CR28","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-1-4612-0865-5_26","volume-title":"The collected works of Wassily Hoeffding","author":"W Hoeffding","year":"1994","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. In: Fisher, N.I., Sen, P.K. (eds.) The collected works of Wassily Hoeffding, pp. 409\u2013426. Springer, New York (1994). https:\/\/doi.org\/10.1007\/978-1-4612-0865-5_26"},{"key":"40_CR29","doi-asserted-by":"publisher","unstructured":"Kleinberg, J.: The small-world phenomenon: an algorithmic perspective. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000, pp. 163\u2013170. ACM, New York (2000). https:\/\/doi.org\/10.1145\/335305.335325. https:\/\/doi.acm.org\/10.1145\/335305.335325","DOI":"10.1145\/335305.335325"},{"key":"40_CR30","doi-asserted-by":"crossref","unstructured":"Kumar, R., Novak, J., Tomkins, A.: Structure and evolution of online social networks. In: Proc. 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, pp. 611\u2013617 (2006)","DOI":"10.1145\/1150402.1150476"},{"key":"40_CR31","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: KONECT - The Koblenz Network Collection. In: Proceedings of International Conference on World Wide Web Companion (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"40_CR32","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Faloutsos, C.: Sampling from large graphs. In: Proceedings of 12th International Conference on ACM SIGKDD, Philadelphia, PA, USA, pp. 631\u2013636 (2006)","DOI":"10.1145\/1150402.1150479"},{"key":"40_CR33","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of 11th International Conference on ACM SIGKDD, Chicago, IL, USA, pp. 177\u2013187 (2005)","DOI":"10.1145\/1081870.1081893"},{"key":"40_CR34","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection (2014). http:\/\/snap.stanford.edu\/data"},{"key":"40_CR35","unstructured":"Palmer, C., Siganos, G., Faloutsos, M., Faloutsos, C., Gibbons, P.: The connectivity and fault-tolerance of the internet topology. In: Proceedings of Workshop on Network-Related Data Management, vol. 25, S. Barbara, USA (2001)"},{"key":"40_CR36","doi-asserted-by":"crossref","unstructured":"Palmer, C.R., Gibbons, P.B., Faloutsos, C.: ANF: a fast and scalable tool for data mining in massive graphs. In: Proceedings of 8th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 81\u201390. ACM (2002)","DOI":"10.1145\/775047.775059"},{"key":"40_CR37","doi-asserted-by":"crossref","unstructured":"Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of 45th Symposium on Theory of Computing (STOC), Palo Alto, CA, USA, pp. 515\u2013524 (2013)","DOI":"10.1145\/2488608.2488673"},{"key":"40_CR38","unstructured":"Tauro, L., Palmer, C., Siganos, G., Faloutsos, M.: A simple conceptual model for the Internet topology. In: Global Internet, San Antonio, TX, USA (2001)"},{"issue":"2","key":"40_CR39","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1145\/78922.78925","volume":"15","author":"KY Whang","year":"1990","unstructured":"Whang, K.Y., Vander-Zanden, B.T., Taylor, H.M.: A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst. 15(2), 208\u2013229 (1990)","journal-title":"ACM Trans. Database Syst."},{"key":"40_CR40","doi-asserted-by":"publisher","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19\u201322 May 2012, pp. 887\u2013898 (2012). https:\/\/doi.org\/10.1145\/2213977.2214056. https:\/\/doi.acm.org\/10.1145\/2213977.2214056","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases: Research Track"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43418-1_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T05:54:00Z","timestamp":1730094840000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43418-1_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031434174","9783031434181"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43418-1_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"17 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2023.ecmlpkdd.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"829","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"196","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.63","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Applied Data Science Track: 239 submissions, 58 accepted papers; Demo Track: 31 submissions, 16 accepted papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}