class: center, middle, inverse, title-slide # Emergence of Hierarchy in Networked Endorsement Dynamics ## SIAM DS 21: Minisymposium on Mathematics of Inequity and Inequality ###
Mari Kawakatsu,
Princeton Applied and Computational Mathematics
Phil Chodrow
,
UCLA Mathematics
Nicole Eikmeier,
Grinnell Computer Science
Dan Larremore,
CU Boulder Computer Science and BioFrontiers Institute
--- exclude: true <style type="text/css"> code.r{ font-size: 16px; } pre { font-size: 16px !important; } </style> --- class: split-50 bg-main1 layout: false .row[ .split-four[ .column[.image-caption-right[ <br> ## .alert2[<nobr>Mari Kawakatsu</nobr>] .font_large[Applied + Computational Mathematics <br> Princeton University <br> .alert2[MS144, 3pm Wed.]] ] ] .column[.image-bottom[ <img src="img/mari_portrait.jpeg" width=100%> ]] .column[ .image-bottom[ <img src="img/phil_portrait.jpeg" width=100%> ] ] .column[.image-caption-left[ <br> ## .alert[<nobr>Phil Chodrow</nobr>] .font_large[Mathematics <br><br> UCLA] ] ] ] ] .row[ .split-four[ .column[.image-caption-right[ ## .alert[<nobr>Nicole Eikmeier</nobr>] .font_large[Computer Science<br><br>Grinnell College] ] ] .column[ <img src="img/nicole_portrait.jpeg" width=100%> ] .column[ <img src="img/dan_portrait.jpeg" width=100%> ] .column[.image-caption-left[ ## .alert[<nobr>Dan Larremore</nobr>] .font_large[Computer Science + BioFrontiers Inst. <br> CU Boulder ] ] ] ] ] --- class: split-two bg-main1 .column[.font_large[.font_large[.font_large[ .center[Ranks .alert2[⟳] Decisions] ]] We propose a simple .alert[math model] of social hierarchies emerging from feedback loops. Feedback loops can generate stable hierarchies, even when are .alert[no meaningful differences] between agents. Some social systems are .alert[near criticality] -- small interventions could help to promote equality and equity. ] ] .column.bg-main4[.content.vmiddle[ <img src="img/pnas.png" width=100%> ]] --- layout: true class: split-two .column[ .split-four[ .row.bg-main1[.content.font3[ .alert[Directed] Networks ]] .row.bg-main1[.content.font_large[ .alert2[Competitions] (sports, animal dominance...) <br> .color-main1[tab] Nodes are competitors/individuals. <br> .color-main1[tab] `\(A \rightarrow B\)` `\(\implies\)` `\(B\)` beats `\(A\)`. ]] .row.bg-main1[.content.font_large[ .alert2[Internet] (Google, Facebook) <br> .color-main1[tab] Nodes are webpages. <br> .color-main1[tab] `\(A\rightarrow B\)` `\(\implies\)` `\(A\)` links to `\(B\)`. ]] .row.bg-main1[.content.font_large[ .alert2[Endorsements] (politics, Twitter) <br> .color-main1[tab] Nodes are people. <br> .color-main1[tab] `\(A\rightarrow B\)` `\(\implies\)` `\(A\)` thinks `\(B\)` is good. ]] ]] .column[.content.center.hmiddle[<br> <img src="img/digraph.png" width=70%><br> ***Image credit:*** *Wikipedia* {{content}} ]] --- class: hide-row2-col1 hide-row3-col1 hide-row4-col1 --- class: hide-row3-col1 hide-row4-col1 <img src="img/magnus.jpeg" width=70%> --- class:hide-row4-col1 <img src="img/how-pagerank-works.png" width=70%> --- class: <img src="img/lamberson-social-network.jpeg" width=70%><br> ***Image credit***: [PJ Lamberson](http://social-dynamics.org/twitter-network-data/) --- class: middle layout: false .split-two[ .column.bg-main1[ <br><br> # The Network Ranking Problem .blockquote.font_large[Given a network, assign a scalar .alert2[**rank**] or .alert2[**score**] vector `\(\mathbf{r} \in \mathbb{R}^n\)` based on the network structure. `\(r_i\)` is the rank of node `\(i \in \mathcal{N}\)`. ] .content.font_large[ 1. Who is the **best** chessplayer or **most dominant** parakeet? 2. Which website is **most central** to the internet? 3. What is the **most important** account on Twitter? ]] .column[ .content.center.vmiddle[ <img src="img/pagerank-example.jpeg" width=90%><br> ***Image credit:*** *Wikipedia* ] ] ] --- layout: true class: split-two .column[ <br> # .alert[Ranks] from Matrices<br> .content.center[.font_large[ <img src="img/digraph.png" width=50%> $$\mathbf{A} = \left[\begin{matrix} <!-- 0 & \mathbf{1} & 0 & 0 & 0 & 0 \\ --> <!-- 0 & 0 & \mathbf{1} & 0 & 0 & 0 \\ --> <!-- 0 & 0 & 0 & 0 & \mathbf{1} & 0 \\ --> <!-- 0 & \mathbf{1} & 0 & 0 & 0 & 0 \\ --> <!-- 0 & 0 & 0 & \mathbf{1} & 0 & \mathbf{1} \\ --> <!-- 0 & 0 & 0 & 0 & 0 & 0 --> \end{matrix}\right] $$ ] ] ] .column.bg-main1[<br> .split-three[ .row[.content.font_large[ .alert2[Degree] (Number of positive interactions) `$$\mathbf{r} = \mathbf{d} = \mathbf{e}^T\mathbf{A}$$` <br> ]] .row[.content.font_large[ .alert2[PageRank] (Google) **r** is leading eigenvector of `$$\mathbf{P} = \mathbf{D}^{-1}\mathbf{A} + \frac{1}{n}(1-\alpha_p)\mathbf{E}$$` ]] .row[.content.font_large[ .alert2[SpringRank] (DeBacco et al. 2018) Solve linear system .font_medium[.font_small[$$\left[\mathbf{D}^i + \mathbf{D}^o - (\mathbf{A} + \mathbf{A}^T) + \alpha_s\mathbf{I}\right] \mathbf{r} = \left[\mathbf{D}^i - \mathbf{D}^o\right]\mathbf{e}$$] ]]] ]] --- class: hide-row1-col2 hide-row2-col2 hide-row3-col2 --- class: hide-row2-col2 hide-row3-col2 --- class:hide-row3-col2 --- class: --- layout: false class: split-two bg-main1 .column[ <br> .font_large[.font_large[.font_large[ .content.center[Ranks .alert2[⟳] Decisions]]] ] .blockquote[ .content.font_large[.content.font_large[ What happens when network ranks .alert2[inform] decision-making within a system?] ]] ] .column.bg-main4[.content.center[<br><br><br><br> <img src="img/us-news-rankings.jpeg" width=60%> ] .content.font_large[.alert[Example]: College ranks are based in part on selectivity. High ranks <br> `\(\implies\)` more applications <br> `\(\implies\)` higher selectivity <br> `\(\implies\)` even higher ranks.... ]] --- layout: false class: split-two bg-main1 .column[.content[ <br> .font_large[.content.center[.font_large[.font_large[The Model]]] <br> Matrix `\(\mathbf{A} = \mathbf{A}^{(t)}\)` of *endorsements*: `\(a_{ij}^{(t)}\)` is the weighted number of times `\(i\)` endorses `\(j\)` by time `\(t\)`. 1. Compute rank vector `\(\mathbf{r}\)` (degree, PageRank, SpringRank...) 2. Node `\(i\)` computes a *utility* of endorsing `\(j\)`: `$$u_{ij} = \color{#63d297}{\beta_1} r_j + \color{#ff5252}{\beta_2} (r_j - r_i)^2\;.$$` `\(\color{#63d297}{\beta_1}\)` : Preference for *prestige*. <br> `\(\color{#ff5252}{\beta_2}\)` : Preference for *proximity*. ]]] .column.bg-main4[.content.vmiddle[ <img src="img/fig_1.png" width=100%> ]] --- class: split-two bg-main1 .column[.content[ <br> .font_large[.content.center[.font_large[.font_large[The Model]]] <br> 3\. `\(m\)` nodes make endorsements. Node `\(i\)` selects node `\(j\)` to endorse with probability `$$p_{ij} = \frac{e^{u_{ij}}}{\sum_k e^{u_{ik}}}\;.$$` 4\. Matrix `\(\mathbf{A}\)` updated with .alert2[new endorsements]: `$$\mathbf{A}^{(t+1)} = \color{#ff5252}{\lambda} \mathbf{A}^{(t)} + (1-\color{#ff5252}{\lambda}) \color{#63d297}{\mathbf{\Delta}^{(t)}}$$` `\(\lambda\)` is a .alert[memory parameter]: `\(\lambda \approx 1 \rightarrow\)` system state evolves very slowly. ]]] .column.bg-main4[.content.vmiddle[ <img src="img/fig_1.png" width=100%> ]] --- class: split-two bg-main1 .column[.content[ .font_large[.font_large[.font_large[ .center[Ranks .alert2[⟳] Decisions] ]] .blockquote[Agents develop prestige by receiving endorsements. ] .blockquote[Agents make endorsements based on prestige. ] ]]] .column.bg-main4[.content.vmiddle[ <img src="img/fig_1.png" width=100%> ]] --- class: split-two bg-main1 .column[<br><br>.content.font_large[.font_large[What happens?]]<br><br><br> .font_large[ `$$u_{ij} = \color{#63d297}{\beta_1} r_j + \color{#ff5252}{\beta_2} (r_j - r_i)^2\;.$$` `\(\color{#63d297}{\beta_1}\)` : Preference for .alert2[*prestige*]. <br> - `\(\beta_1\)` small: fluctuating egalitarianism. - `\(\beta_1\)` large: emergence of distinct node ranks. `\(\color{#ff5252}{\beta_2}\)` : Preference for *.alert[proximity]*. - `\(\beta_2 < 0\)`: stabilization of hierarchical ranks. <br> Can we say anything analytic about these observations? ] ] .column.bg-main4[.content.vmiddle[ <img src="img/dynamics_examples.png" width=100%> ]] --- class: split-two bg-main1 .column[<br><br>.content.font_large[.font_large[Theorem [KCEL 2021]]]<br><br> .font_large[ 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 root such that `\(\mathbf{r} = r \mathbb{e}\)`. This root 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}$$` ]] .column.bg-main4[.content.vmiddle[ <img src="img/dynamics_examples.png" width=100%> ]] --- class: background-image: url("img/bifurcations_with_curves.png") background-size: contain --- class: split-two bg-main1 layout: true .column[<br><br>.content.font_large[.font_large[Theorem [KCEL 2021]]]<br><br> .font_large[ 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 root such that `\(\mathbf{r} = r \mathbb{e}\)`. This root 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}$$` .alert2[**Proof**]: Compute Jacobian, long linear algebra exercise. ]] .column.bg-main4[.content.font_medium[ {{content}} ]] --- class: <img src="img/algebra.png" width=100%> --- class: split-two layout: false .column.bg-main1[<br> # Inference in Data .content.font_large[ Model assigns a *likelihood* to the observed data. `$$\mathcal{L}(\lambda, \beta) = \sum_{t = 0}\sum_{i, j \in \mathcal{N}}\color{#ff5252}{k_{ij}^{(t)}} \log \color{#63d297}{\gamma_{ij}^{(t)}}$$` - `\(\color{#ff5252}{k_{ij}^{(t)}}\)`: \# of observed endorsements `\(i\rightarrow j\)` in timestep `\(t\)` (from data). - `\(\color{#63d297}{\gamma_{ij}^{(t)}}\)`: Modeled probability that `\(i\)` chooses `\(j\)` as recipient of endorsement at time `\(t\)` (depends on `\(\lambda\)`, `\(\beta\)`, and data from previous timesteps). **Method of maximum likelihood**: find parameters `\(\hat{\lambda}\)` and `\(\hat{\beta}\)` to maximize `\(\mathcal{L}\)`. ] ] .column.bg-main4[.content.vmiddle[.font_large[<br> **Math PhD Exchange**¹: University *A* "endorses" *B* by hiring a PhD trained at *B*, over 50 years. <br><br> **Monk Parakeets**²: Parakeet *A* "endorses" *B* by losing a fight to *B*, over 4 observation periods. <br><br><br> **Newcomb Fraternity**³: Fraternity brother *A* "endorses" *B* by stating that they like *B* on a survey, over a semester (15 weeks). ] <br> <br> ¹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). <br> North Dakota State University Department of Mathematics, Data from “The Mathematics Genealogy Project.” ([link](https://www.genealogy.math.ndsu.nodak.edu/index.php.)) <br> ²E. A. Hobson, S. DeDeo, Social feedback and the emergence of rank in animal society. *PLoS Comput. Biol.* 11, e1004411 (2015) <br> ³T. Newcomb, *The Acquaintance Process* (Holt, Reinhard, and Winston, New York, NY, 1961). ]] --- class: split-two .column.bg-main1[<br> # Inference in Data .content.font_large[ Model assigns a *likelihood* to the observed data. `$$\mathcal{L}(\lambda, \beta) = \sum_{t = 0}\sum_{i, j \in \mathcal{N}}\color{#ff5252}{k_{ij}^{(t)}} \log \color{#63d297}{\gamma_{ij}^{(t)}}$$` - `\(\color{#ff5252}{k_{ij}^{(t)}}\)`: \# of observed endorsements `\(i\rightarrow j\)` in timestep `\(t\)` (from data). - `\(\color{#63d297}{\gamma_{ij}^{(t)}}\)`: Modeled probability that `\(i\)` chooses `\(j\)` as recipient of endorsement at time `\(t\)` (depends on `\(\lambda\)`, `\(\beta\)`, and data from previous timesteps). **Method of maximum likelihood**: find parameters `\(\hat{\lambda}\)` and `\(\hat{\beta}\)` to maximize `\(\mathcal{L}\)`. ] ] .column.bg-main4[.content.vmiddle[ <img src="img/inference-table.png" width=100%> ]] --- class: split-two bg-main1 .column[<br><br>.content.font_large[.font_large[Are we in the hierarchical regime?]]<br><br> .font_large[ **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}$$` <br> <br> Math PhD exchange: .alert2[**barely subcritical**]. Parakeets + Newcomb Frat: .alert[**supercritical**]. ] ] .column.bg-main4[.content.vmiddle[ <img src="img/criticality-table.png" width=100%> ]] --- class: split-two bg-main1 .column[<br><br>.content.font_large[.font_large[It matters how we model prestige! ]]<br><br><br><br> .font_large[ Placement share, Root-Degree, and PageRank: MIT dominates, esp. recently. **SpringRank**: Favors Harvard, Stanford, Princeton, and Berkeley (based on prestigious placements of their graduates). Different estimates of fluidity in ranks. ] ] .column.bg-main4[<br> <br> .content.font_large[.font_large[Math PhD Exchange]] <br><br><br> <img src="img/phd-exchange.png" width=100%> ] --- class: split-two bg-main1 .column[.font_large[.font_large[.font_large[ .center[Ranks .alert2[⟳] Decisions] ]] We wrote a simple .alert[math model] of hierarchies emerging from feedback loops. Feedback loops can generate stable hierarchies, even when are .alert[no meaningful differences] between agents. Some systems are .alert[near criticality] -- small interventions could help to promote equality and equity. ] ] .column.bg-main4[.content.vmiddle[ <img src="img/pnas.png" width=100%> ]] --- # Scenes from a (really fun) collaboration <img src="img/heart-cookies.jpg" width=14.7%> <img src="img/apollo.jpg" width=14.7%> <img src="img/book.jpg" width=14.7%> <img src="img/dinner.jpg" width=26%> <img src="img/ezra.jpg" width=26%> <img src="img/so-pumped.png" width=16%> <img src="img/yes.GIF" width=32%> <img src="img/mari-mp.png" width=50%> <img src="img/ready.jpg" width=24.5%> <img src="img/obama.png" width=25.5%> <img src="img/two-cats.jpeg" width=24.5%> <img src="img/page-rank.png" width=22.7%> <!-- <img src="img/cats.jpeg" width=32%> --> <!-- <img src="img/cinnamon-rolls.jpg" width=16%> --> --- layout: false class: split-two .column.bg-main1[<br>.font_large[ # Thanks! ] <br> <img src="img/mari_portrait.jpeg" width=24%> <img src="img/phil_portrait.jpeg" width=24%> <img src="img/nicole_portrait.jpeg" width=24%> <img src="img/dan_portrait.jpeg" width=24%> .font_large[ Fab team: Mari, Nicole, Dan. Complex Networks Winter Workshop 2019 The cats Minisymposium organizers: Skylar + Joel "Travel" support: SIAM, NSF You! ]] .column.bg-main4[.content[<br> .font_large[ ## arXiv version https://arxiv.org/abs/2007.04448 *Includes a gender representation analysis of bibliography.* ## These slides [philchodrow.github.io/talks/emergence-of-hierarchy/short](https://philchodrow.github.io/talks/emergence-of-hierarchy/short#1) ## Socials @mkawakatsu <br> @philchodrow <br> @NicoleEikmeier <br> @DanLarremore ] ] ]