The statistical physics of ranking and partial orders

Ranking things is a common and natural task that is performed across a wide variety of contexts, from sports fandom to scheduling. More generally, ranking is simply one form of ordering, i.e. finding permutations of objects that satisfy constraints. Other than ranking, ordering tasks include reconstructing the temporal dynamics of disease propagation from contact traces, or fitting network growth models.  On the basis of partial information, these tasks are computationally complex – #P-hard in the worst case, making them even harder than NP-complete problems. To make matters worse, real data is usually noisy: some observations are “wrong”, although we don’t know which.

In this study we attack these problems using tools from statistical physics and network science. By mapping permutations onto a spin model defined on a complex network, we develop a message passing algorithm to solve ranking problems. Among other things, our methods can be used to efficiently rank objects from partial information; fit models such as the Bradley-Terry-Luce model of preferences, or ordinal regression models; recover the evolution of spreading processes in networks; estimate the volume of high-dimensional polytopes; and compute complex order statistics of arbitrary distributions.