Assigning entities to teams as a hypergraph discovery problem

Ferraz de Arruda, Guilherme ; He, Wan ; Heydaribeni, Nasimeh ; Javidi, Tara ; Moreno, Yamir (Universidad de Zaragoza) ; Eliassi-Rad, Tina

Resumen: Assigning agents to teams under strict task and effort constraints is crucial in business, science, and engineering, where disruptions can cause significant losses. Current methods do not explore
hypergraph-based solutions that explicitly optimize algebraic connectivity under constraints, leaving unresolved how to systematically form robust, recoverable teams. We present a hypergraph-based
team assignment algorithm where nodes represent agents and hyperedges represent tasks. The search is guided by input constraints and aims to optimize resilience and diffusion by maximizing the algebraic connectivity of an edge-dependent, vertex-weighted hypergraph. We employ constrained simulated annealing to find a satisfactory hypergraph by enforcing both the minimum effort required for task completion and the maximum effort agents can exert. We evaluate robustness by assessing solution recovery after node removal attacks. Our results demonstrate that the hypergraph formulation yields more robust solutions than the bipartite formulation and the greedy approach.

Idioma: Inglés

DOI: 10.1038/s42005-025-02474-7

Año: 2026

Publicado en: Communications Physics 9, 1 (2026), [15 pp.]
ISSN: 2399-3650

Financiación: info:eu-repo/grantAgreement/ES/DGA/E36-23R-FENOL
Financiación: info:eu-repo/grantAgreement/ES/MICINN/PID2023-149409NB-I00

Tipo y forma: Article (Published version)

Área (Departamento): Área Física Teórica (Dpto. Física Teórica)