{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:11Z","timestamp":1750221371779,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T00:00:00Z","timestamp":1542240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["ME3619\/3-1"],"award-info":[{"award-number":["ME3619\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for graph data sets. A complex network model gaining considerable popularity builds random hyperbolic graphs, generated by distributing points within a disk in the hyperbolic plane and then adding edges between points with a probability depending on their hyperbolic distance.<\/jats:p>\n          <jats:p>\n            We present a dynamic extension to model gradual network change, while preserving at each step the point position probabilities. To process the dynamic changes efficiently, we formalize the concept of a\n            <jats:italic>probabilistic neighborhood<\/jats:italic>\n            : Let\n            <jats:italic>P<\/jats:italic>\n            be a set of\n            <jats:italic>n<\/jats:italic>\n            points in Euclidean or hyperbolic space,\n            <jats:italic>q<\/jats:italic>\n            a query point, dist a distance metric, and\n            <jats:italic>f<\/jats:italic>\n            : R\n            <jats:sup>+<\/jats:sup>\n            \u2192 [0, 1] a monotonically decreasing function. Then, the probabilistic neighborhood\n            <jats:italic>N<\/jats:italic>\n            (\n            <jats:italic>q<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            ) of\n            <jats:italic>q<\/jats:italic>\n            with respect to\n            <jats:italic>f<\/jats:italic>\n            is a random subset of\n            <jats:italic>P<\/jats:italic>\n            and each point\n            <jats:italic>p<\/jats:italic>\n            \u2208\n            <jats:italic>P<\/jats:italic>\n            belongs to\n            <jats:italic>N<\/jats:italic>\n            (\n            <jats:italic>q<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            ) with probability\n            <jats:italic>f<\/jats:italic>\n            (dist(\n            <jats:italic>p<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )). We present a fast, sublinear-time query algorithm to sample probabilistic neighborhoods from planar point sets. For certain distributions of planar\n            <jats:italic>P<\/jats:italic>\n            , we prove that our algorithm answers a query in\n            <jats:italic>O<\/jats:italic>\n            ((|\n            <jats:italic>N<\/jats:italic>\n            (\n            <jats:italic>q<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            )| + \u221a\n            <jats:italic>n<\/jats:italic>\n            ) log\n            <jats:italic>n<\/jats:italic>\n            ) time with high probability. This enables us to process a node movement in random hyperbolic graphs in sublinear time, resulting in a speedup of about one order of magnitude in practice compared to the fastest previous approach. Apart from that, our query algorithm is also applicable to Euclidean geometry, making it of independent interest for other sampling or probabilistic spreading scenarios.\n          <\/jats:p>","DOI":"10.1145\/3195635","type":"journal-article","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T13:02:09Z","timestamp":1542286929000},"page":"1-30","source":"Crossref","is-referenced-by-count":3,"title":["Updating Dynamic Random Hyperbolic Graphs in Sublinear Time"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5697-7142","authenticated-orcid":false,"given":"Moritz Von","family":"Looz","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Cologne, Germany"}]},{"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Cologne, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,11,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465219"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2367574.2367575"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02458840"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.036113"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2016.1177802"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) (Leibniz International Proceedings in Informatics (LIPIcs\u201916)","volume":"57","author":"Bl\u00e4sius Thomas","year":"2016"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20626"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-88-7642-475-5_68"},{"key":"e_1_2_1_9_1","volume-title":"Leibniz International Proceedings in Informatics (LIPIcs\u201917)","volume":"87","author":"Bringmann Karl","year":"2017"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_49"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_51"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594545"},{"volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994)","year":"1994","author":"Kamel Ibrahim","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790216.2790219"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.221"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914218"},{"volume-title":"Advances in Databases: Concepts, Systems and Applications","author":"Kriegel Hans-Peter","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.036106"},{"volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"volume-title":"Popularity versus similarity in growing networks. Nature 489, 7417","year":"2012","author":"Papadopoulos Fragkiskos","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833893"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376774"},{"volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"Samet Hanan","key":"e_1_2_1_26_1"},{"volume-title":"Generating Scaled Replicas of Real-World Complex Networks","author":"Staudt Christian L.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"volume-title":"Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently","author":"von Looz Moritz","key":"e_1_2_1_29_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-44543-4_35"},{"volume-title":"Generating random hyperbolic graphs in subquadratic time. ArXiv Preprint arXiv:1501.03545 (Sept","year":"2015","author":"von Looz Moritz","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761644"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_40"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3195635","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3195635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:35Z","timestamp":1750213595000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3195635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,15]]},"references-count":32,"alternative-id":["10.1145\/3195635"],"URL":"https:\/\/doi.org\/10.1145\/3195635","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2018,11,15]]}}}