In systems of many individual entities, interactions and their outcomes are often defined by hierarchies or rankings. While in most cases these rankings are hidden from us, their presence is nevertheless revealed in the asymmetric patterns of interactions that we observe. For example, social groups of birds, primates, and elephants are organized according to dominance hierarchies in which more powerful animals assert themselves over those less powerful. Social positions are not directly visible to researchers, but we can infer each animal’s position in social space by observing a sufficient number of interactions. Similar latent hierarchies exist in systems of endorsement in which status is due to prestige or reputation. For example, in academia, universities are more likely to hire faculty candidates from equally or more prestigious universities.

I will present a principled model and algorithm called SpringRank to infer such latent hierarchies directly from data. By mapping a network of directed interactions to a physical system, this ranking process becomes as fast as your favorite sparse linear solver. Unlike other methods such as minimum violation ranking, SpringRank assigns real-valued scores 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 framework for a statistical significance test for distinguishing when the inferred hierarchy is due to the network topology or is instead due to random chance, and it can be used to perform inference tasks such as predicting the existence or direction of edges. I'll illustrate these findings by analyzing real and synthetic data and show that our method outperforms others, in both speed and accuracy, in recovering the underlying ranks and predicting edge directions. This work is a collaboration with Caterina De Bacco and Cris Moore.

Free and Open to the Public
Light Refreshments
Please contact cscs@umich.edu if accommodations are necessary.