Belief propagation for permutations, rankings, and partial orders

Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA Many datasets give partial information about an ordering or ranking by indicating which team won a game, which item a user prefers, or who infected whom. We define a continuous spin system whose Gibbs distribution is the posterior distribution on permutations, given a probabilistic model of these interactions. Using the cavity method we derive a belief propagation algorithm that computes the marginal distribution of each node's position. In addition, the Bethe free energy lets us approximate the number of linear extensions of a partial order and perform model selection. Ranking or ordering objects is a natural problem in In this case, the energy H(π) is the number of violations, many contexts.