{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T12:40:34Z","timestamp":1752669634136,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T00:00:00Z","timestamp":1670889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MIUR under PRIN","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}]},{"name":"University of Florence under Project GRANTED"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            A weighted link stream is a pair (\n            <jats:italic>V<\/jats:italic>\n            , \ud835\udd3c)  comprising\n            <jats:italic>V<\/jats:italic>\n            , the set of nodes, and \ud835\udd3c, the list of temporal edges (\n            <jats:italic>u,v,t<\/jats:italic>\n            ,\u03bb) , where\n            <jats:italic>u,v<\/jats:italic>\n            are two nodes in\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>t<\/jats:italic>\n            is the starting time of the temporal edge, and\n            <jats:italic>\u03bb<\/jats:italic>\n            is its travel time. By making use of this model, different notions of diameter can be defined, which refer to the following distances: earliest arrival time, latest departure time, fastest time, and shortest time. After proving that any of these diameters cannot be computed in time sub-quadratic with respect to the number of temporal edges, we propose different algorithms (inspired by the approach used for computing the diameter of graphs) that allow us to compute, in practice very efficiently, the diameter of quite large real-world weighted link stream for several definitions of the diameter. In the case of the fastest time distance and of the shortest time distance, we introduce the notion of pivot-diameter, to deal with the fact that temporal paths cannot be concatenated in general. The pivot-diameter is the diameter restricted to the set of pair of nodes connected by a path that passes through a pivot (that is, a node at a given time instant). We prove that the problem of finding an optimal set of pivots, in terms of the number of pairs connected, is NP-hard, and we propose and experimentally evaluate several simple and fast heuristics for computing \u201cgood\u201d pivot sets. All the proposed algorithms (for computing either the diameter or the pivot-diameter) require very often a very low number of single source (or target) best path computations. We verify the effectiveness of our approaches by means of an extensive set of experiments on real-world link streams. We also experimentally prove that the temporal version of the well-known 2-sweep technique, for computing a lower bound on the diameter of a graph, is quite effective in the case of weighted link stream, by returning very often tight bounds.\n          <\/jats:p>","DOI":"10.1145\/3569168","type":"journal-article","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T11:48:04Z","timestamp":1666957684000},"page":"1-28","source":"Crossref","is-referenced-by-count":6,"title":["On Computing the Diameter of (Weighted) Link Streams"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4399-5530","authenticated-orcid":false,"given":"Marco","family":"Calamai","sequence":"first","affiliation":[{"name":"Dipartimento di Statistica, Informatica, Applicazioni, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8789-3195","authenticated-orcid":false,"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9854-7885","authenticated-orcid":false,"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[{"name":"Dipartimento di Statistica, Informatica, Applicazioni, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,13]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties","author":"Ausiello G.","year":"2012","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. 2012. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. Springer, Berlin."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<125::AID-NET1>3.0.CO;2-P"},{"key":"e_1_3_2_4_2","first-page":"215","volume-title":"23rd Annual European Symposium on Algorithms","author":"Borassi M.","year":"2015","unstructured":"M. Borassi, D. Coudert, P. Crescenzi, and A. Marino. 2015. On computing the hyperbolicity of real-world graphs. In 23rd Annual European Symposium on Algorithms. Springer, 215\u2013226."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.005"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.02.033"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.106086"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.04.004"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.018"},{"key":"e_1_3_2_10_2","first-page":"302","volume-title":"18th Annual European Symposium on Algorithms","author":"Crescenzi P.","year":"2010","unstructured":"P. Crescenzi, R. Grossi, C. Imbrenda, L. Lanzi, and A. Marino. 2010. Finding the diameter in real-world graphs\u2014Experimentally turning a lower bound into an upper bound. In 18th Annual European Symposium on Algorithms. Springer, 302\u2013313."},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/978-3-642-30850-5_10","volume-title":"11th International Symposium on Experimental Algorithms","author":"Crescenzi P.","year":"2012","unstructured":"P. Crescenzi, R. Grossi, L. Lanzi, and A. Marino. 2012. On computing the diameter of real-world directed (weighted) graphs. In 11th International Symposium on Experimental Algorithms. Springer, 99\u2013110."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.3390\/a12100211"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13090211"},{"key":"e_1_3_2_14_2","article-title":"Graph Mining Report","author":"Cruciani A.","year":"2021","unstructured":"A. Cruciani and M. A. Prado-Romero. 2021. Graph Mining Report. Private Communication.","journal-title":"Private Communication"},{"key":"e_1_3_2_15_2","unstructured":"IMDb. 2021. IMDb Datasets. Retrieved from http:\/\/www.imdb.com\/interfaces."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1038\/sdata.2018.89"},{"key":"e_1_3_2_19_2","unstructured":"J. Kunegis. 2021. The KONECT Project. Retrieved from http:\/\/konect.cc."},{"key":"e_1_3_2_20_2","article-title":"Weighted, bipartite, or directed stream graphs for the modeling of temporal networks","volume":"1906","author":"Latapy Matthieu","year":"2019","unstructured":"Matthieu Latapy, Cl\u00e9mence Magnien, and Tiphaine Viard. 2019. Weighted, bipartite, or directed stream graphs for the modeling of temporal networks. CoRR abs\/1906.04840 (2019).","journal-title":"CoRR"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-018-0537-7"},{"key":"e_1_3_2_22_2","unstructured":"J. Leskovec. 2021. Stanford Large Network Dataset Collection (SNAP). Retrieved from http:\/\/snap.stanford.edu\/data\/."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687577"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_3_2_25_2","first-page":"475","volume-title":"29th Annual ACM Symposium on the Theory of Computing","author":"Raz R.","year":"1997","unstructured":"R. Raz and S. Safra. 1997. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In 29th Annual ACM Symposium on the Theory of Computing. ACM, 475\u2013484."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063748"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.3390\/a6010100"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_3_2_29_2","first-page":"645","volume-title":"51st Annual IEEE Annual Symposium on Foundations of Computer Science","author":"Williams V. Vassilevska","year":"2010","unstructured":"V. Vassilevska Williams and R. Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In 51st Annual IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 645\u2013654."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2594065"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001728"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569168","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:41Z","timestamp":1750182701000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,13]]},"references-count":31,"alternative-id":["10.1145\/3569168"],"URL":"https:\/\/doi.org\/10.1145\/3569168","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,12,13]]}}}