Math Models of Hierarchy: Dominance, Dynamics, and Data

Complex Networks Winter Workshop | Dec 15th, 2025

Phil Chodrow
Department of Computer Science
Middlebury College

Hi! I’m Phil Chodrow

I like…

• Mathematics of complex systems
• Network science
• Ethics and technology
• Traditional martial arts
• Tea
• Star Trek: Deep Space 9
• Effective teaching

I’m a new-ish professor in the department of computer science at Middlebury College in Middlebury, Vermont.

I teach machine learning, discrete math, introductory computing, and network science.

My Journey

$$

$$

This is a talk about hierarchy

the classification of a group of people according to ability or to economic, social, or professional standing

a graded or ranked series

- Merriam Webster

Examples of hierarchies

Standings in competitions

Rankings of colleges, PhD programs, etc.

Popularity

Dominance in animal societies

Some hierarchies are helpful

Others are…different. ttttttt ttttttt ttttt

1. Can hierarchies sustain themselves on the basis of nothing but prestige?

2. Can we infer how agents interact with hierarchies from data?

3. What makes science joyful (for me)?

Collaboration Origin Story

Complex Networks Winter Workshop 2019

18 Months Later…

Mari Kawakatsu
UPenn, UMich
Nicole Eikmeier
Grinnell
Dan Larremore
CU Boulder

Ranking and Networks

For today, we’re going to consider a weighted directed network on \(n\) agents, which we represent via a (not-necessarily symmetric) weighted adjacency matrix \(\mathbf{A} \in \mathbb{R}^{n\times n}\).

A ranking is a function that assigns a score to each agent. We can represent a ranking as a function which assigns to matrix \(\mathbf{A}\) a vector \(\mathbf{r} = \mathbf{r}(\mathbf{A})\).

Here, \(\mathbf{r} = (r_1,r_2,\ldots, r_n)\) where \(r_i\) is the score of agent \(i\).

Image credit: De Bacco, Larremore + Moore, Science Advances (2018)

From networks to ranking…and back?

A model of prestige-based hierarchy

We have \(n\) agents.

These agents can “endorse” each other.

When agent \(i\) endorses agent \(j\), we interpret this as agent \(i\) signaling that agent \(j\) is of high prestige.

“Endorsements:”

• Player \(i\) loses a match to player \(j\).
• University \(i\) hires a scholar trained at university \(j\).
• Individual \(i\) claims that \(j\) is their friend.
• …

A model of prestige-based hierarchy

A state of the model is a matrix \(\mathbf{A}^{(t)} \in \mathbb{R}^{n\times n}\) of endorsements.

\(a_{ij}^{(t)}\) is the weighted number times that \(i\) has endorsed \(j\).

At each timestep, we update \(\mathbf{A}^{(t)}\): \[ \mathbf{A}^{(t+1)} = \lambda \mathbf{A}^{(t)} + (1-\lambda) \Delta^{(t)} \] where \(\Delta^{(t)}\) is the matrix of new endorsements.

\(\lambda\) acts as the rate of exponentially decaying system memory.

Here, our idea is that the updates \(\Delta^{(t)}\) are sensitive to agents’ current perceptions of ranks in the network \(\mathbf{A}^{(t)}\).

New Endorsements

Agents endorse other agents that they perceive as being of high prestige.

Prestige is measured by a score function \(\sigma: \mathbf{A}^{(t)} \mapsto \mathbf{r}^{(t)} \in \mathbb{R}^n\).

Each agent \(i\) computes a utility of endorsing agent \(j\) in terms of the score vector \(\mathbf{r}^{(t)}\). Our utility is: \[ u_{ij}(\mathbf{r}) = \beta_1 r_j + \beta_2 (r_i - r_j)^2. \]

Agent \(i\) endorses \(j\) at time \(t+1\) w. p.  \[ p_{ij}^{(t)} = \frac{e^{u_{ij}(\mathbf{r}^{(t)})}}{\sum_j e^{u_{ij}(\mathbf{r}^{(t)})}} \]

(\(m\in \mathbb{Z}\) endorsements per round.)

New Endorsements

Agents endorse other agents that they perceive as being of high prestige.

Prestige is measured by a score function \(\sigma: \mathbf{A}^{(t)} \mapsto \mathbf{r}^{(t)} \in \mathbb{R}^n\).

Each agent \(i\) computes a utility of endorsing agent \(j\) in terms of the score vector \(\mathbf{r}^{(t)}\). Our utility is: \[ u_{ij}(\mathbf{r}) = \color{#FFD447}{\beta_1} r_j + \color{#59C9A5}{\beta_2} (r_i - r_j)^2. \]

Agent \(i\) endorses \(j\) at time \(t+1\) w. p.  \[ p_{ij}^{(t)} = \frac{e^{u_{ij}(\mathbf{r}^{(t)})}}{\sum_j e^{u_{ij}(\mathbf{r}^{(t)})}} \]

(\(m\in \mathbb{Z}\) endorsements per round.)

\(\beta_1\) encodes a preference to endorse high-prestige agents. Higher value: more likely for endorsements to concentrate at the top.

\(\beta_2\) encodes a preference to endorse agents that are similar in prestige to you. Negative value: more likely for endorsements to “travel” only a little way up the hierarchy.

The score function \(\sigma\) maps the matrix of endorsements \(\mathbf{A} \in \mathbb{R}^{n\times n}\) to a vector of scores \(\mathbf{s} \in \mathbb{R}^n\). There are lots of choices!

In-Degree

\(s_i\) is the number of times that agent \(i\) h as been endorsed: \(\mathbf{r} = \mathbb{1}^T\mathbf{A}\)

PageRank

\(\mathbf{r}\) is the eigenvector with eigenvalue \(1\) of the matrix \(\mathbf{P}\) with entries \[ p_{ij} = (1-\alpha)\frac{a_{ij}}{d_i} + \frac{\alpha}{n} \]

SpringRank

\(\mathbf{r}\) is the unique solution of the system \[ \left[\mathbf{L} - \alpha \mathbf{I}\right]\mathbf{r} = \mathbf{D}^{\mathrm{in}} - \mathbf{D}^{\mathrm{out}} \]

\(\mathbf{D}^{\mathrm{in}} = \mathrm{diag}(\mathbb{1}^T\mathbf{A})\) and \(\mathbf{D}^{\mathrm{out}} = \mathrm{diag}(\mathbf{A}\mathbb{1})\)

1. Can hierarchies sustain themselves on the basis of nothing but prestige?

Yes, and there is a bifurcation (qualitative behavior shift) depending on the parameters.

What does this model do?

\(\beta_1\) preference for prestige.

• \(\beta_1\) small: fluctuating egalitarianism.
• \(\beta_1\) large: emergence of time-varying hierarchies.

\(\beta_2\) preference for proximity.

• \(\beta_2 < 0\): stabilization of hierarchical ranks.

Two math problems

Dynamics: can we mathematically characterize when we observe egalitarianism and when we observe hierarchy in terms of the score function, \(\beta_1\), and \(\beta_2\)?

Data science: can we determine which score functions and parameters best describe the behavior of real systems?

Theorem: KCEL ’21

Consider the deterministic function \[\mathbf{f}(\mathbf{r}, \mathbf{A}) = \lim_{\lambda \rightarrow 1} \frac{\mathbb{E}[\mathbf{r}|\mathbf{A}] - \mathbf{r}}{1 - \lambda}\;.\]

This function has an egalitarian fixed point, where all ranks are the same. This point fixed point is linearly stable iff \(\beta_1 < \beta_1^c\):

\[\beta_1^c = \begin{cases} 2\sqrt{\frac{n}{m}} &\quad \text{Root-Degree} \\ 1/\alpha_p &\quad \text{PageRank} \\ 2 + \alpha_s\frac{n}{m} &\quad \text{SpringRank}. \end{cases}\]

Theorem: KCEL ’21

Consider the deterministic function \[\mathbf{f}(\mathbf{r}, \mathbf{A}) = \lim_{\lambda \rightarrow 1} \frac{\mathbb{E}[\mathbf{r}|\mathbf{A}] - \mathbf{r}}{1 - \lambda}\;.\]

This function has an egalitarian fixed point, where all ranks are the same. This point fixed point is linearly stable iff \(\beta_1 < \beta_1^c\):

\[\beta_1^c = \begin{cases} 2\sqrt{\frac{n}{m}} &\quad \text{Root-Degree} \\ 1/\alpha_p &\quad \text{PageRank} \\ 2 + \alpha_s\frac{n}{m} &\quad \text{SpringRank}. \end{cases}\]

Linear Stability

Heuristically, a fixed point \(\mathbf{x}_0\) of some dynamics is stable if, when you perturb the the system to some nearby point, it eventually comes back to \(\mathbf{x}_0\).

Image credit: Desmond Winterborne

Theorem: KCEL ’21

Consider the deterministic function \[\mathbf{f}(\mathbf{r}, \mathbf{A}) = \lim_{\lambda \rightarrow 1} \frac{\mathbb{E}[\mathbf{r}|\mathbf{A}] - \mathbf{r}}{1 - \lambda}\;.\]

This function has an egalitarian fixed point, where all ranks are the same. This point fixed point is linearly stable iff \(\beta_1 < \beta_1^c\):

\[\beta_1^c = \begin{cases} 2\sqrt{\frac{n}{m}} &\quad \text{Root-Degree} \\ 1/\alpha_p &\quad \text{PageRank} \\ 2 + \alpha_s\frac{n}{m} &\quad \text{SpringRank}. \end{cases}\]

Linear Stability

Here, stability of the egalitarian fixed point of \(\mathbf{f}\) is governed by the Jacobian matrix of partial derivatives:

\[\mathbf{J} = \left[\begin{matrix}\frac{\partial f_1}{\partial r_1} & \frac{\partial f_1}{\partial r_2} & \cdots & \frac{\partial f_1}{\partial r_n} \\ \frac{\partial f_2}{\partial r_1} & \frac{\partial f_2}{\partial r_2} & \cdots & \frac{\partial f_2}{\partial r_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial r_1} & \frac{\partial f_n}{\partial r_2} & \cdots & \frac{\partial f_n}{\partial r_n} \end{matrix}\right]\]

Fixed point is linearly stable if \(\mathbf{J}\) only has eigenvalues with negative real part.

So, we can assess the stability of egalitarianism in this system with calculus + linear algebra.

Theorem: KCEL ’21

Consider the deterministic function \[\mathbf{f}(\mathbf{r}, \mathbf{A}) = \lim_{\lambda \rightarrow 1} \frac{\mathbb{E}[\mathbf{r}|\mathbf{A}] - \mathbf{r}}{1 - \lambda}\;.\]

This function has an egalitarian fixed point, where all ranks are the same. This point fixed point is linearly stable iff \(\beta_1 < \beta_1^c\):

\[\beta_1^c = \begin{cases} 2\sqrt{\frac{n}{m}} &\quad \text{Root-Degree} \\ 1/\alpha_p &\quad \text{PageRank} \\ 2 + \alpha_s\frac{n}{m} &\quad \text{SpringRank}. \end{cases}\]

Theorem: KCEL ’21

Consider the deterministic function \[\mathbf{f}(\mathbf{r}, \mathbf{A}) = \lim_{\lambda \rightarrow 1} \frac{\mathbb{E}[\mathbf{r}|\mathbf{A}] - \mathbf{r}}{1 - \lambda}\;.\]

This function has an egalitarian fixed point, where all ranks are the same. This point fixed point is linearly stable iff \(\beta_1 < \beta_1^c\):

\[\beta_1^c = \begin{cases} 2\sqrt{\frac{n}{m}} &\quad \text{Root-Degree} \\ 1/\alpha_p &\quad \text{PageRank} \\ 2 + \alpha_s\frac{n}{m} &\quad \text{SpringRank}. \end{cases}\]

Theorem: KCEL ’21

Consider the deterministic function \[\mathbf{f}(\mathbf{r}, \mathbf{A}) = \lim_{\lambda \rightarrow 1} \frac{\mathbb{E}[\mathbf{r}|\mathbf{A}] - \mathbf{r}}{1 - \lambda}\;.\]

This function has an egalitarian fixed point, where all ranks are the same. This point fixed point is linearly stable iff \(\beta_1 < \beta_1^c\):

\[\beta_1^c = \begin{cases} 2\sqrt{\frac{n}{m}} &\quad \text{Root-Degree} \\ 1/\alpha_p &\quad \text{PageRank} \\ 2 + \alpha_s\frac{n}{m} &\quad \text{SpringRank}. \end{cases}\]

Learnings

1. The stability of egalitarianism depends on the prestige preference \(\beta_1\) but not on the proximity preference \(\beta_2\).
2. The stability of egalitarianism also depends on the score function used.
3. In some score functions, in some parameter regimes, egalitarianism and hierarchy are both possible (bistability).

2. Can we infer how agents interact with hierarchies from data?

Yes: we can find most likely parameters and score functions.

Because of the specific form of the probability \(p_{ij}^{(t)}\), this boils down to logistic regression.

Recall that we had this funny looking function that defined a probability of agent \(i\) endorsing agent \(j\):

\[ p_{ij}^{(t)} = \frac{e^{u_{ij}(\mathbf{r}^{(t)})}}{\sum_j e^{u_{ij}(\mathbf{r}^{(t)})}} \]

This lets us assign a likelihood to the observed data as a function of the parameters:

\[\mathcal{L}(\lambda, \beta) = \sum_{t = 0}\sum_{i, j \in \mathcal{N}}a_{ij}^{(t)} \log p_{ij}^{(t)}\]

Method of maximum-likelihood: find \(\lambda\) and \(\beta\) to make this function large.

Data:

Math PhD Exchange¹: University A “endorses” B by hiring a PhD trained at B, over 50 years.
Monk Parakeets²: Parakeet A “endorses” B by losing a fight to B, over 4 observation periods.
Newcomb Fraternity³: Fraternity brother A “endorses” B by stating that they like B on a survey, over a semester (15 weeks).

¹D. Taylor, S. A. Meyers, A. Clauset, M. A. Porter, P. J. Mucha, Eigenvector-based centrality measures for temporal networks. Multiscale Model. Simul. 15, 537–574 (2017).
North Dakota State University Department of Mathematics, Data from “The Mathematics Genealogy Project.” (link)
²E. A. Hobson, S. DeDeo, Social feedback and the emergence of rank in animal society. PLoS Comput. Biol. 11, e1004411 (2015)
³T. Newcomb, The Acquaintance Process (Holt, Reinhard, and Winston, New York, NY, 1961).

Recall that we had this funny looking function that defined a probability of agent \(i\) endorsing agent \(j\):

\[ p_{ij}^{(t)} = \frac{e^{u_{ij}(\mathbf{r}^{(t)})}}{\sum_j e^{u_{ij}(\mathbf{r}^{(t)})}} \]

This lets us assign a likelihood to the observed data as a function of the parameters:

\[\mathcal{L}(\lambda, \beta) = \sum_{t = 0}\sum_{i, j \in \mathcal{N}}a_{ij}^{(t)} \log p_{ij}^{(t)}\]

Method of maximum-likelihood: find \(\lambda\) and \(\beta\) to make this function large.

Data:

Math PhD Exchange¹: University A “endorses” B by hiring a PhD trained at B, over 50 years.
Monk Parakeets²: Parakeet A “endorses” B by losing a fight to B, over 4 observation periods.
Newcomb Fraternity³: Fraternity brother A “endorses” B by stating that they like B on a survey, over a semester (15 weeks).

¹D. Taylor, S. A. Meyers, A. Clauset, M. A. Porter, P. J. Mucha, Eigenvector-based centrality measures for temporal networks. Multiscale Model. Simul. 15, 537–574 (2017).
North Dakota State University Department of Mathematics, Data from “The Mathematics Genealogy Project.” (link)
²E. A. Hobson, S. DeDeo, Social feedback and the emergence of rank in animal society. PLoS Comput. Biol. 11, e1004411 (2015)
³T. Newcomb, The Acquaintance Process (Holt, Reinhard, and Winston, New York, NY, 1961).

Are we in the hierarchical regime?

Theorem from before: Egalitarianism is stable iff \(\beta_1 < \beta_1^c\), where

\[\beta_1^c = \begin{cases} 2\sqrt{\frac{n}{m}} &\quad \text{Root-Degree} \\ 1/\alpha_p &\quad \text{PageRank} \\ 2 + \alpha_s\frac{n}{m} &\quad \text{SpringRank}. \end{cases}\]

Math PhD exchange: bistable \(-\) both egalitarianism and hierarchy are possible.

Parakeets + Newcomb Frat: hierarchical.

It matters how we compute the ranks!

Placement share, Root-Degree, and PageRank: MIT dominates, esp. recently.

SpringRank: Favors Harvard, Stanford, Princeton, and Berkeley (based on prestigious placements of their graduates).

We have reason to prefer Root-Degree here – it’s a better predictor of observed behaviors!

Ranks ⟳ Decisions

We developed a simple math model of hierarchies emerging from feedback loops.

Feedback loops can generate stable hierarchies, even when are no meaningful differences between agents.

Some systems are near criticality: small interventions could help to promote equality and equity.

You Know You’ve Made It When…

Yang, X.; Wu, Z.; Javaid, S. RETRACTED: An Adaptive Hierarchical Network Model for Studying the Structure of Economic Network. Entropy 2022, 24, 702.

Two Ways to Start Projects

Idea First

“Here’s a cool idea!
What/who do I need to do in order to achieve this?”

People First

“Here are some people I like!
What cool things can we achieve together?”

I do both of these, but I have the most fun when I start with people.

Reflections on interdisciplinary applied math being a human in science

Find good people to work with.

Communicate with them honestly and often.

Embrace shenanigans.

Thanks!

Awesome Collaborators

Mari Kawakatsu
UPenn, UMich
Nicole Eikmeier
Grinnell
Dan Larremore
CU Boulder

Complex Networks Winter Workshop 2019

And Most Importantly…