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/

Zendy Plus

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

Zendy Tools

Zendy Open

The average distance from a node to all other nodes in a graph, or from aquery point in a metric space to a set of points, is a fundamental quantity indata analysis. The inverse of the average distance, known as the (classic)closeness centrality of a node, is a popular importance measure in the study ofsocial networks. We develop novel structural insights on the sparsifiability ofthe distance relation via weighted sampling. Based on that, we present highlypractical algorithms with strong statistical guarantees for fundamentalproblems. We show that the average distance (and hence the centrality) for allnodes in a graph can be estimated using $O(\epsilon^{-2})$ single-sourcedistance computations. For a set $V$ of $n$ points in a metric space, we showthat after preprocessing which uses $O(n)$ distance computations we can computea weighted sample $S\subset V$ of size $O(\epsilon^{-2})$ such that the averagedistance from any query point $v$ to $V$ can be estimated from the distancesfrom $v$ to $S$. Finally, we show that for a set of points $V$ in a metricspace, we can estimate the average pairwise distance using $O(n+\epsilon^{-2})$distance computations. The estimate is based on a weighted sample of$O(\epsilon^{-2})$ pairs of points, which is computed using $O(n)$ distancecomputations. Our estimates are unbiased with normalized mean square error(NRMSE) of at most $\epsilon$. Increasing the sample size by a $O(\log n)$factor ensures that the probability that the relative error exceeds $\epsilon$is polynomially small.

Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees