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)
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.