Identifying the rank of species in a complex ecosystem is a difficult task since the rank of each species invariably depends on the interactions stipulated with other species through the network’s adjacency matrix. A common ranking method in economic and ecological networks is to sort the nodes such that the layout of the reordered adjacency matrix looks maximally nested with all nonzero entries packed in the upper left corner, called Nestedness Maximization Problem (NMP). Here we solve this problem by defining a suitable cost-energy function for the NMP, which reveals the equivalence between the NMP and the Quadratic Assignment Problem, one of the most important combinatorial optimization problems, and use statistical physics techniques to derive a set of self-consistent equations whose fixed point represents the optimal nodes’ rankings in an arbitrary bipartite mutualistic network. Concurrently, we present an efficient algorithm to solve the NMP that outperforms state-of-the-art network-based metrics and genetic algorithms. Eventually, our theoretical framework may be easily generalized to study the relationship between ranking and network structure beyond pairwise interactions, e.g. in higher-order networks.

Authors

• Manuel Sebastian Mariani,
• Dario Mazzilli,
• Aurelio Patelli,
• Dries Sels &
• Flaviano Morone

Communications Physics volume7, Article number: 102 (2024) Cite this article

https://www.nature.com/articles/s42005-024-01588-8