Metraipolis › archive › dc_ebe1be68cd32

Efficient generation of networks with minimal average shortest-path distance — arXiv:2608.04131

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.04131
License (as archived): CC0-1.0
Archived: 2026-10-31T12:03:43.230Z
SHA-256 of the archived text: f7038bf2089d7a73ea935de497add24a312f1c46f1667cf6cd59b29885fa17d6
Stable URL of this page: https://metraipolis.com/documento/dc_ebe1be68cd32

How to cite

Efficient generation of networks with minimal average shortest-path distance — arXiv:2608.04131 — arXiv (en), https://arxiv.org/abs/2608.04131 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ebe1be68cd32 (Metraipolis archive dc_ebe1be68cd32, sha256 f7038bf2089d7a73ea935de497add24a312f1c46f1667cf6cd59b29885fa17d6)

BibTeX

@misc{dcebe1be68cd32,
  title = {Efficient generation of networks with minimal average shortest-path distance — arXiv:2608.04131},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.04131},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ebe1be68cd32; sha256 f7038bf2089d7a73ea935de497add24a312f1c46f1667cf6cd59b29885fa17d6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04131. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Designing networks that minimize distances and satisfy structural constraints is a fundamental task across transportation, communication, and biological systems. Here, we consider the problem of finding, for a given degree sequence, the network structure displaying the smallest possible average shortest-path length. While exact solutions are available in linear time for trees, such an optimization problem becomes computationally infeasible as soon as loops are allowed in the networks. We propose a fast algorithm to construct approximate solutions to such a degree-constrained distance-minimization problem. Accordingly, edges are first created between high-degree nodes; then, additional connections are placed following the rules of the standard configuration model. In spite of its simplicity, the algorithm displays outstanding performance as demonstrated in our systematic experiments on both synthetic and real degree sequences. Our method is particularly effective on synthetic degree sequences displaying medium levels of heterogeneity. When applied to degree sequences of real networks, the proposed algorithm is able to reduce the all-pair shortest path of real structures by 20%, on average. We perform a validation on small-sized networks, where we compare the shortest-path distance of the networks generated with our algorithm against those obtained via simulated annealing optimization. Although simulated annealing yields slightly better structures, our proposed algorithm provides nearly identical solutions at a substantially lower computational cost, making it a solid method in applications concerning large-scale systems.

Tema degli esploratori: governance digitale e beni comuni (retro-catalogo arXiv: annunci del 2026-08-06 in physics.soc-ph).
Categorie arXiv: Physics and Society (physics.soc-ph).
Pagina del lavoro: https://arxiv.org/abs/2608.04131 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T11:52:16.045Z dalla pagina https://arxiv.org/catchup/physics.soc-ph/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).