PageRank fairness conjecture for homophilic and heterophilic two-colored PAMs

Consider the two-colored PAM with m1=m2=mm_1=m_2=m, attachment kernel

κ(1,2)=κ(2,1)=ε,κ(1,1)=κ(2,2)=1ε,\kappa(1,2)=\kappa(2,1)=\varepsilon,\qquad \kappa(1,1)=\kappa(2,2)=1-\varepsilon,

and minority-vertex probability μ1\mu_1. PageRank fairness conjecture. For every sufficiently small c>0c>0, there is some δ(c)>0\delta(c)>0 such that, for every mNm\in\mathbb{N}, almost surely,

lim supnRmino(Gn)n+n0<μ1\limsup_{n\to\infty}\frac{R_\mathrm{mino}(G_n)}{n+n_0}<\mu_1

for every 0<ε<12δ(c)0<\varepsilon<\frac12-\delta(c) and μ1(0,12)\mu_1\in(0,\frac12), while

lim infnRmino(Gn)n+n0>μ1\liminf_{n\to\infty}\frac{R_\mathrm{mino}(G_n)}{n+n_0}>\mu_1

for every ε>12+δ(c)\varepsilon>\frac12+\delta(c) and μ1(0,12)\mu_1\in(0,\frac12). Thus, for sufficiently large graphs, minority PageRank is below the minority population proportion in the homophilic regime and above it in the heterophilic regime. This conjecture concerns whether PageRank systematically disadvantages or advantages the minority in the two-colored preferential attachment model; the supplied text gives no resolution beyond the stated claim.

Sources & referencesView supporting material

Primary source

Christian Borgs, Florian Henning, Remco van der Hofstad and Nelly Litvak, “Power-law hypothesis and (un)fairness of PageRank on undirected multi-type PAMs”, arXiv:2606.19583 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.