Metraipolis › archive › dc_e00a418f0130

Exact computation of the network modularity with branch-and-bound — arXiv:2610.04668

Source: arXiv
Original: https://arxiv.org/abs/2610.04668
License (as archived): CC0-1.0
Archived: 2026-10-06T05:29:39.041Z
SHA-256 of the archived text: 46e379bd05c96f89ace75f75f6eacc191b97e21c4882df91c65a2ab4697d9583
Stable URL of this page: https://metraipolis.com/documento/dc_e00a418f0130

How to cite

Exact computation of the network modularity with branch-and-bound — arXiv:2610.04668 — arXiv, https://arxiv.org/abs/2610.04668 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e00a418f0130 (Metraipolis archive dc_e00a418f0130, sha256 46e379bd05c96f89ace75f75f6eacc191b97e21c4882df91c65a2ab4697d9583)

BibTeX

@misc{dce00a418f0130,
  title = {Exact computation of the network modularity with branch-and-bound — arXiv:2610.04668},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.04668},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e00a418f0130; sha256 46e379bd05c96f89ace75f75f6eacc191b97e21c4882df91c65a2ab4697d9583},
  year = {2026}
}

Archived text

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

We consider the computation of the network modularity, a common measure of the structure of networks or graphs that quantifies the division of a network into modules or clusters. The computation of the network modularity is an NP-hard problem, thus making its exact computation often infeasible in practice. This has resulted in the development of several heuristics in the literature. In this work, we consider the exact computation of the network modularity with the help of a branch-and-bound algorithm. Our algorithm is guaranteed to find the optimal clustering that maximizes the network modularity, however it achieves this without a full exploration of the search space. This is accomplished by bounding partial solutions and discarding them if it can be foreseen that a partial solution will not yield an improvement over an existing solution. We assess our algorithm with respect to accuracy and runtime and compare it to a brute-force approach as well as two state-of-the-art benchmarks, simulated annealing and the Louvain method.

Tema degli esploratori: governance digitale e beni comuni (elenco arXiv cs.SI, nuovi lavori del giorno).
Categorie arXiv: Social and Information Networks (cs.SI) ; Computation (stat.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.04668 — 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-06T05:26:20.290Z dalla pagina https://arxiv.org/list/cs.SI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).