2026-07-22T03:56:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25201 2026-03-19T12:59:32Z ddc:004 open_access

Demand-Aware Small-World Networks on Clustered Demands Avin, Chen Elsässer, Robert Figiel, Aleksander Melnyk, Darya Schmid, Stefan Small-world networks demand-aware network designs algorithms and analysis clustering Small-world networks are attractive for the efficient routing they provide, requiring only a low link density. They have hence also been considered for the design of distributed systems, such as peer-to-peer networks. However, existing small-world network designs are oblivious to the actual traffic they serve. In this paper, we initiate the study of demand-aware small-world networks. In particular, we extend the Kleinberg graph model, by allowing the nodes to choose the distribution of long-range links according to the traffic demand. We present a formal analysis of the weighted route lengths for the important case of clustered demands. We show both in theory and in simulations, using real-world traffic workloads, that demand-aware small-world graphs can significantly outperform their demand-oblivious counterparts. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chen Avin and Robert Elsässer and Aleksander Figiel and Darya Melnyk and Stefan Schmid 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.28 urn:nbn:de:0030-drops-252017 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.28 eng https://creativecommons.org/licenses/by/4.0/legalcode