Published on Sun Sep 03 2017

A physical model for efficient ranking in networks

Caterina De Bacco, Daniel B. Larremore, Cristopher Moore

We present a physically-inspired model and an efficient algorithm to infer rankings of nodes in directed networks. The ranking is obtained by solving a linear system of equations, which is sparse if the network is. We show that our method often outperforms a variety of others, in both speed and accuracy.

0
0
0
Abstract

We present a physically-inspired model and an efficient algorithm to infer hierarchical rankings of nodes in directed networks. It assigns real-valued ranks to nodes rather than simply ordinal ranks, and it formalizes the assumption that interactions are more likely to occur between individuals with similar ranks. It provides a natural statistical significance test for the inferred hierarchy, and it can be used to perform inference tasks such as predicting the existence or direction of edges. The ranking is obtained by solving a linear system of equations, which is sparse if the network is; thus the resulting algorithm is extremely efficient and scalable. We illustrate these findings by analyzing real and synthetic data, including datasets from animal behavior, faculty hiring, social support networks, and sports tournaments. We show that our method often outperforms a variety of others, in both speed and accuracy, in recovering the underlying ranks and predicting edge directions.

Wed Jul 09 2014
Machine Learning
RankMerging: A supervised learning-to-rank framework to predict links in large social network
Uncovering unknown or missing links in social networks is a difficult task because of their sparsity. We define a simple yet efficient supervised learning-to-rank framework, called RankMerging. We illustrate our method on three different kinds of social networks.
0
0
0
Fri Nov 07 2008
Machine Learning
Statistical ranking and combinatorial Hodge theory
We propose a number of techniques for obtaining a global ranking from data that may be incomplete and imbalanced. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. We show that every edge flow representing pairwise ranking can be resolved into two orthogonal components.
1
23
92
Wed Jun 06 2018
Machine Learning
TopRank: A practical algorithm for online stochastic ranking
Online learning to rank is a sequential decision-making problem. Many sample-efficient algorithms have been proposed for this problem that assume a specific click model. We propose a generalized click model that encompasses many existing models.
0
0
0
Sun Feb 10 2008
Artificial Intelligence
Network as a computer: ranking paths to find flows
We explore a simple mathematical model of network computation, based on Markov chains. Similar models apply to a broad range of computationalphenomena, arising in networks of computers.
0
0
0
Wed Dec 01 2004
Artificial Intelligence
Ranking Pages by Topology and Popularity within Web Sites
0
0
0
Mon Nov 08 2010
Machine Learning
Least Squares Ranking on Graphs
ranking is a least squares computation on a graph. This formulation was first described by Leake in 1976 for ranking football teams. The underlying ideas are easy to explain, requiring only four fundamental subspaces from elementary linear algebra.
0
0
0