论文标题
关于图形算法平均案例分析的外部有效性
On the External Validity of Average-Case Analyses of Graph Algorithms
论文作者
论文摘要
对平均案例分析的第一批评是，我们实际上不知道现实世界输入的概率分布。因此，在某些随机模型上分析算法对实际性能没有任何影响。从本质上讲，这种批评怀疑外部有效性的存在，即，它假设在某种简单且干净的模型上的算法行为并没有将模型超出模型转化为实践绩效现实世界中的输入。在本文中，我们为系统地研究外部有效性问题提供了第一步。为此，我们根据两种属性评估了2740个稀疏现实世界网络集合中六种图形算法的性能；异质性（学位分布的差异）和局部性（边缘连接已经接近的顶点的趋势）。我们将其与在生成的网络上的性能进行比较，该网络具有不同的位置和异质性。我们发现，在理想化的网络模型设置中的性能使现实世界中的网络非常出色。此外，异质性和局部性似乎是影响许多图算法性能的核心特性。
The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2740 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.
