An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
复制标题
DOI：
10.1137/1.9781611974782.58
复制
发表时间：
2016-04
影响因子：
--
通讯作者：
Michele Borassi;P. Crescenzi;L. Trevisan
中科院分区：
文献类型：
--
作者：
Michele Borassi;P. Crescenzi;L. Trevisan
近年来，研究人员提出了几种算法来计算现实世界复杂网络的度量量，并且在实践中非常有效，尽管没有最坏情况的保证。在这项工作中，我们提出了一个公理框架来分析这些算法的性能，通过证明它们在满足某些公理的图类上是有效的。在此基础上，我们进一步证明了这些公理可以被几种生成幂律随机图的概率模型渐近地几乎肯定地验证。近年来，研究人员提出了几种计算现实世界复杂网络度量量的算法，尽管没有最坏情况保证，但在实践中非常有效。在这项工作中，我们提出了一个公理化框架来分析这些算法的性能，通过证明它们在满足某些性质的图类上是有效的。此外，我们还用几个生成幂律随机图的概率模型，如配置模型、Chung-Lu模型和Norros-Reittu模型，证明了这些性质是渐近地几乎肯定地验证的。因此，我们的结果意味着这些模型中的平均情况分析。例如，在我们的框架中，现有的算法可以在次二次时间内计算图的直径和半径，有时甚至可以在时间$n^{1+o(1)}$中计算。此外，在某些情况下，可以在次二次时间内根据接近中心性计算出k个最中心的顶点，并设计出查询时间为次线性且占用次二次空间的距离oracle。在最坏的情况下，除非人们普遍相信的猜想是错误的，否则不可能对这些问题中的任何一个获得可比的结果。
In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is no worst-case guarantee. In this work, we propose an axiomatic framework to analyze the performances of these algorithms, by proving that they are efficient on the class of graphs satisfying certain axioms. Furthermore, we prove that the axioms are verified asymptotically almost surely by several probabilistic models that generate power law random graphs, such as the In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is no worst-case guarantee. In this work, we propose an axiomatic framework to analyze the performances of these algorithms, by proving that they are efficient on the class of graphs satisfying certain properties. Furthermore, we prove that these properties are verified asymptotically almost surely by several probabilistic models that generate power law random graphs, such as the Configuration Model, the Chung-Lu model, and the Norros-Reittu model. Thus, our results imply average-case analyses in these models. For example, in our framework, existing algorithms can compute the diameter and 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$ most central vertices according to closeness centrality in subquadratic time, and to design a distance oracle with sublinear query time and subquadratic space occupancy. In the worst case, it is impossible to obtain comparable results for any of these problems, unless widely-believed conjectures are false.