{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T19:51:06Z","timestamp":1768074666004,"version":"3.49.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>In this work, we propose, analyze and empirically validate a lazy-update approach to maintain accurate approximations of the 2-hop neighborhoods of dynamic graphs resulting from sequences of edge insertions.<\/jats:p>\n          <jats:p>\n            We first show that under random input sequences, our algorithm exhibits an optimal trade-off between accuracy and insertion cost: it only performs [EQUATION] (amortized) updates per edge insertion, while the estimated size of any vertex's 2-hop neighborhood is at most a factor \u03b5 away from its true value in most cases,\n            <jats:italic toggle=\"yes\">regardless<\/jats:italic>\n            of the underlying graph topology and for any \u03b5 &gt; 0.\n          <\/jats:p>\n          <jats:p>\n            As a further theoretical contribution, we explore adversarial scenarios that can force our approach into a worst-case behavior at any given time\n            <jats:italic toggle=\"yes\">t<\/jats:italic>\n            of interest. We show that while worst-case input sequences do exist, a necessary condition for them to occur is that the\n            <jats:italic toggle=\"yes\">girth<\/jats:italic>\n            of the graph released up to time\n            <jats:italic toggle=\"yes\">t<\/jats:italic>\n            be at most 4.\n          <\/jats:p>\n          <jats:p>Finally, we conduct extensive experiments on a collection of real, incremental social networks of different sizes, which typically have low girth. Empirical results are consistent with and typically better than our theoretical analysis anticipates. This further supports the robustness of our theoretical findings: forcing our algorithm into a worst-case behavior not only requires topologies characterized by a low girth, but also carefully crafted input sequences that are unlikely to occur in practice.<\/jats:p>\n          <jats:p>Combined with standard sketching techniques, our lazy approach proves an effective and efficient tool to support key neighborhood queries on large, incremental graphs, including neighborhood size, Jaccard similarity between neighborhoods and, in general, functions of the union and\/or intersection of 2-hop neighborhoods.<\/jats:p>","DOI":"10.14778\/3749646.3749665","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"3937-3950","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate 2-hop Neighborhoods on Incremental Graphs: An Efficient Lazy Approach"],"prefix":"10.14778","volume":"18","author":[{"given":"Luca","family":"Becchetti","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Clementi","sequence":"additional","affiliation":[{"name":"Tor Vergata University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luciano","family":"Gual\u00e1","sequence":"additional","affiliation":[{"name":"Tor Vergata University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca Pep\u00e8","family":"Sciarria","sequence":"additional","affiliation":[{"name":"Tor Vergata University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Straziota","sequence":"additional","affiliation":[{"name":"Tor Vergata University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matteo","family":"Stromieri","sequence":"additional","affiliation":[{"name":"Tor Vergata University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601412"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380718.2380723"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2024.3450506"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326561.1326563"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2502.19205"},{"key":"e_1_2_1_9_1","volume-title":"Computing top-k closeness centrality faster in unweighted graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 13, 5","author":"Bergamini Elisabetta","year":"2019","unstructured":"Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, and Henning Meyerhenke. 2019. Computing top-k closeness centrality faster in unweighted graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 13, 5 (2019), 1\u201340."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963493"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.865686"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0307625100"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/829502.830043"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45123-4_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/370982.370985"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2916858"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374470"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551868"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3701551.3703491"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_2_1_22_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel. 2017. Graph Theory (5th ed.). Springer Publishing Company, Incorporated, New York City, United States.","edition":"5"},{"key":"e_1_2_1_23_1","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"Dubhashi Devdatt","unstructured":"Devdatt Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms (1st ed.). Cambridge University Press, USA.","edition":"1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620180804"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760037"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_29_1","first-page":"238","article-title":"Centrality in social networks: Conceptual clarification. Social network: critical concepts in sociology. Londres","volume":"1","author":"Freeman Linton C","year":"2002","unstructured":"Linton C Freeman et al. 2002. Centrality in social networks: Conceptual clarification. Social network: critical concepts in sociology. Londres: Routledge 1, 3 (2002), 238\u2013263.","journal-title":"Routledge"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555806"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555806"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00172"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634129"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.04.006"},{"key":"e_1_2_1_36_1","volume-title":"Yon Dohn Chung, and Bongki Moon","author":"Lee Kyong-Ha","year":"2012","unstructured":"Kyong-Ha Lee, Yoon-Joon Lee, Hyunsik Choi, Yon Dohn Chung, and Bongki Moon. 2012. Parallel data processing with MapReduce: a survey. AcM sIGMoD record 40, 4 (2012), 11\u201320."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557077"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_39_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.131"},{"key":"e_1_2_1_43_1","volume-title":"Bipartite graphs in systems biology and medicine: a survey of methods and applications. GigaScience 7, 4","author":"Pavlopoulos Georgios A","year":"2018","unstructured":"Georgios A Pavlopoulos, Panagiota I Kontou, Athanasia Pavlopoulou, Costas Bouyioukos, Evripides Markou, and Pantelis G Bagos. 2018. Bipartite graphs in systems biology and medicine: a survey of methods and applications. GigaScience 7, 4 (2018), giy014."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175462"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220361"},{"key":"e_1_2_1_46_1","volume-title":"ASNA, Z\u00fcrich, August 26\u201328","author":"Rochat Yannick","year":"2009","unstructured":"Yannick Rochat. 2009. Closeness Centrality Extended to Unconnected Graphs: the Harmonic Centrality Index. In ASNA, Z\u00fcrich, August 26\u201328, 2009. Institute of Applied Mathematics, Switzerland, 1\u201315."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-010-9401-5"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI'15)","author":"Ryan","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI'15). AAAI Press, Austin, Texas, 4292\u20134293."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606031"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Xu-Wen Wang Lorenzo Madeddu Kerstin Spirohn Leonardo Martini Adriano Fazzone Luca Becchetti Thomas P Wytock Istv\u00e1n A Kov\u00e1cs Oliv\u00e9r M Balogh Bettina Benczik et al. 2023. Assessment of community efforts to advance network-based prediction of protein-protein interactions. Nature communications 14 1 (2023) 1582.","DOI":"10.1038\/s41467-023-37079-7"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2023.3275809"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_55_1","volume-title":"Similarity-based link prediction in social networks using latent relationships between the users. Scientific reports 10, 1","author":"Zareie Ahmad","year":"2020","unstructured":"Ahmad Zareie and Rizos Sakellariou. 2020. Similarity-based link prediction in social networks using latent relationships between the users. Scientific reports 10, 1 (2020), 20137."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551840"},{"key":"e_1_2_1_57_1","volume-title":"Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms. Physica A: Statistical Mechanics and its Applications 564","author":"Zhou Tao","year":"2021","unstructured":"Tao Zhou, Yan-Li Lee, and Guannan Wang. 2021. Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms. Physica A: Statistical Mechanics and its Applications 564 (2021), 125532."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:02:15Z","timestamp":1757041335000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749665"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":57,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749665"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749665","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}