English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present KADABRA, a new algorithm to approximate betweenness centrality indirected and undirected graphs, which significantly outperforms all previousapproaches on real-world complex networks. The efficiency of the new algorithmrelies on two new theoretical contributions, of independent interest. The firstcontribution focuses on sampling shortest paths, a subroutine used by mostalgorithms that approximate betweenness centrality. We show that, on realisticrandom graph models, we can perform this task in time $|E|^{\frac{1}{2}+o(1)}$with high probability, obtaining a significant speedup with respect to the$\Theta(|E|)$ worst-case performance. We experimentally show that this newtechnique achieves similar speedups on real-world complex networks, as well.The second contribution is a new rigorous application of the adaptive samplingtechnique. This approach decreases the total number of shortest paths that needto be sampled to compute all betweenness centralities with a given absoluteerror, and it also handles more general problems, such as computing the $k$most central nodes. Furthermore, our analysis is general, and it might beextended to other settings.

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation