An Approximation Algorithm for the Rich-Club Coefficient via Sample Complexity

• Eric Y. Fukuyama UTFPR
• Leandro M. Zatesko UTFPR
• Murilo V. G. da Silva UFPR

DOI: https://doi.org/10.5753/etc.2026.22277

Resumo

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 (∆/ε²p (log ∆ log 1/p + log 1/δ ) + n+m) , improving over the exact ap proach, which requires O(∆m) time.

Referências

Ball, G., Aljabar, P., Zebari, S., Tusor, N., Arichi, T., Merchant, N., Robinson, E. C., Ogundipe, E., Rueckert, D., Edwards, A. D., and Counsell, S. J. (2014). Rich-club organization of the newborn human brain. Proceedings of the National Academy of Sciences, 111(20):7456–7461.

Colizza, V., Flammini, A., Serrano, M. A., and Vespignani, A. (2006). Detecting rich-club ordering in complex networks. Nature Physics, 2(2):110–115.

de Lima, A. M. (2022). Approximation Algorithms in Graphs via Sample Complexity. PhD thesis, Federal University of Paraná (UFPR), Curitiba. PhD thesis (Doctorate in Computer Science) – Exact Sciences Division, Graduate Program in Computer Science.

Ducruet, C., Cuyala, S., and El Hosni, A. (2016). The changing influence of city-systems on global shipping networks: an empirical analysis. Journal of Shipping and Trade, 1(1):4.

Har-Peled, S. (2011). Geometric Approximation Algorithms. American Mathematical Society, USA. Monographs on Discrete Mathematics and Applications.

Riondato, M. and Kornaropoulos, E. M. (2016). Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery, 30(2):438–475.

Zhou, S. and Mondragon, R. (2004). The rich-club phenomenon in the internet topology. IEEE Communications Letters, 8(3):180–182.