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

In recent years, researchers proposed several algorithms that compute metricquantities of real-world complex networks, and that are very efficient inpractice, although there is no worst-case guarantee.  In this work, we propose an axiomatic framework to analyze the performancesof these algorithms, by proving that they are efficient on the class of graphssatisfying certain axioms. Furthermore, we prove that the axioms are verifiedasymptotically almost surely by several probabilistic models that generatepower law random graphs, such as the In recent years, researchers proposedseveral algorithms that compute metric quantities of real-world complexnetworks, and that are very efficient in practice, although there is noworst-case guarantee.  In this work, we propose an axiomatic framework to analyze the performancesof these algorithms, by proving that they are efficient on the class of graphssatisfying certain properties. Furthermore, we prove that these properties areverified asymptotically almost surely by several probabilistic models thatgenerate power law random graphs, such as the Configuration Model, the Chung-Lumodel, and the Norros-Reittu model. Thus, our results imply average-caseanalyses in these models.  For example, in our framework, existing algorithms can compute the diameterand the radius of a graph in subquadratic time, and sometimes even in time$n^{1+o(1)}$. Moreover, in some regimes, it is possible to compute the $k$ mostcentral vertices according to closeness centrality in subquadratic time, and todesign a distance oracle with sublinear query time and subquadratic spaceoccupancy.  In the worst case, it is impossible to obtain comparable results for any ofthese problems, unless widely-believed conjectures are false.

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs