论文标题
用于图形压缩的准稳定着色：近似最大流，线性程序和中心性
Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality
论文作者
论文摘要
我们提出了准稳定着色，这是稳定着色的大约版本。稳定的着色，也称为颜色改进，是用于分类顶点的图理论中的一种精心研究的技术，可用于构建图形的紧凑，无损表示。但是，由于其依赖严格的对称性，其实用性受到限制。真实数据使用颜色改进非常差。据我们所知，我们提出了第一个近似颜色改进方案，我们称之为准稳定着色。通过使用近似值，我们可以减轻严格的对称性的需求，并可以在压缩程度和表示的准确性之间进行权衡。我们研究了三个应用：线性编程，最大流量和中心性，并在每种情况下提供了理论证据，即准稳定着色可以在还原的图上带来良好的近似值。接下来，我们考虑如何计算最大准稳定的颜色：我们证明，通常，这个问题是NP-HARD，并提出了一种基于启发式方法的简单而有效的算法。最后，我们在几个真实的图和应用上实验评估了准稳定的着色技术，与先前的近似技术相比。 参考实现和实验代码可在https://github.com/mkyl/quasistablecolors.jl上获得。
We propose quasi-stable coloring, an approximate version of stable coloring. Stable coloring, also called color refinement, is a well-studied technique in graph theory for classifying vertices, which can be used to build compact, lossless representations of graphs. However, its usefulness is limited due to its reliance on strict symmetries. Real data compresses very poorly using color refinement. We propose the first, to our knowledge, approximate color refinement scheme, which we call quasi-stable coloring. By using approximation, we alleviate the need for strict symmetry, and allow for a tradeoff between the degree of compression and the accuracy of the representation. We study three applications: Linear Programming, Max-Flow, and Betweenness Centrality, and provide theoretical evidence in each case that a quasi-stable coloring can lead to good approximations on the reduced graph. Next, we consider how to compute a maximal quasi-stable coloring: we prove that, in general, this problem is NP-hard, and propose a simple, yet effective algorithm based on heuristics. Finally, we evaluate experimentally the quasi-stable coloring technique on several real graphs and applications, comparing with prior approximation techniques. A reference implementation and the experiment code are available at https://github.com/mkyl/QuasiStableColors.jl .
