Universal sampling rules for the signed friendship paradox

The friendship paradox describes a bias in mean degree induced by neighbour sampling. We study signed weighted networks, with transitions proportional to edge magnitudes and signed strength as the vertex score. We characterize all positive initial weights, depending on total strength and score, that guarantee a nonnegative one-step mean change on every connected graph. Without regularity assumptions, the same condition yields stochastic dominance at every fixed time. Continuous admissible rules are precisely total strength multiplied by a positive continuous nonincreasing function of the score. It is enough to test connected graphs with at most five vertices and two vertex types. The bound of five is optimal even for continuous rules; the proof uses a sharp four-vertex energy inequality. The complete score vector alone cannot determine a universally valid initial law with full support. Under marked local convergence and suitable integrability assumptions, we also obtain joint limits for local conditional mean score increments and compute an explicit limiting law and mean for independently signed random regular graphs. Under joint cut-norm convergence of the magnitude and signed kernels and uniformly bounded normalized strengths, we also obtain Wasserstein convergence of the sampling-weighted distributions of normalized local biases and convergence of their means.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.17118
Primary Topic
Complex Network Analysis Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Universal sampling rules for the signed friendship paradox

Michail Louvaris, Samis Trevezas
arXiv (Cornell University)
Complex Network Analysis Techniques
preprint

Universal sampling rules for the signed friendship paradox

Michail Louvaris, Samis Trevezas
preprint en

Abstract

The friendship paradox describes a bias in mean degree induced by neighbour sampling. We study signed weighted networks, with transitions proportional to edge magnitudes and signed strength as the vertex score. We characterize all positive initial weights, depending on total strength and score, that guarantee a nonnegative one-step mean change on every connected graph. Without regularity assumptions, the same condition yields stochastic dominance at every fixed time. Continuous admissible rules are precisely total strength multiplied by a positive continuous nonincreasing function of the score. It is enough to test connected graphs with at most five vertices and two vertex types. The bound of five is optimal even for continuous rules; the proof uses a sharp four-vertex energy inequality. The complete score vector alone cannot determine a universally valid initial law with full support. Under marked local convergence and suitable integrability assumptions, we also obtain joint limits for local conditional mean score increments and compute an explicit limiting law and mean for independently signed random regular graphs. Under joint cut-norm convergence of the magnitude and signed kernels and uniformly bounded normalized strengths, we also obtain Wasserstein convergence of the sampling-weighted distributions of normalized local biases and convergence of their means.

arXiv (Cornell University)
Complex Network Analysis Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon