An Approximation Algorithm for the Rich-Club Coefficient via Sample Complexity - Fukuyama, Eric Y.; Zatesko, Leandro M.; Silva, Murilo V. G. da (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2026.22277, 2026)
Sample complexity theory has been used to design efficient approximation algorithms for computing graph parameters, such as betweenness centrality and clustering coefficient. The Rich-Club coefficient ϕ(k) quantifies the density of edges among vertices with degree greater than k. Using sample complexity theory, we present a (p, ε)-relative approximation algorithm for the problem of determining ϕ(k) for all k. That is, given parameters 0 < p, ε, δ < 1, our algorithm returns, with probability at least 1 − δ, an estimate ϕ̂(k) with relative error at most ε for every k such that ϕ(k) ≥ σk(p), where σk(p) denotes a threshold function. The algorithm runs in time O (∆/ε 2 p (log ∆ log 1/p + log 1/δ ) + n+m) , improving over the exact ap proach, which requires O(∆m) time.