PageRank fairness conjecture for homophilic and heterophilic two-colored PAMs

Less than 1 year old · traced to

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 m∈Nm\in\mathbb{N}, almost surely,

lim sup⁡n→∞Rmino(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 inf⁡n→∞Rmino(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.

References

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.