PyKPartiteKClique

是 https://github.com/kliem/KPartiteKClique 的 Python 封装。

遍历 k-分割图中所有 k-完全子图。

需求

• setuptools
• Cython

快速入门

一个简单的例子

>>> from kpkc import KCliqueIterator
>>> edges = [[1, 2]]
>>> parts = [[1], [2]]
>>> it = KCliqueIterator(edges, parts)
>>> list(it)
[[1, 2]]

默认算法是 kpkc，它首先选择具有较少边的节点

>>> parts = [[1, 2, 3, 4], [5, 6, 7, 8, 9]]
>>> edges = [[1, 6], [5, 2], [5, 3]]
>>> edges += [[i, j] for i in range(2, 5) for j in range(6, 10)]
>>> it = KCliqueIterator(edges, parts)
>>> list(it)[:3]
[[1, 6], [3, 5], [2, 5]]

算法 FindClique 首先选择具有较少节点的部分

>>> parts = [[1, 2, 3, 4], [5, 6, 7, 8, 9]]
>>> edges = [[1, 6], [5, 2], [5, 3]]
>>> edges += [[i, j] for i in range(2, 5) for j in range(6, 10)]
>>> it = KCliqueIterator(edges, parts, algorithm='FindClique')
>>> list(it)
[[1, 6], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [4, 6], [4, 7], [4, 8], [4, 9]]

基准测试

我们对以下算法/实现进行了基准测试

• kpkc（我们的实现）
• FindClique（我们的实现）
• Cliquer（通过 SageMath 暴露）
• networkx
• mcqd（通过 SageMath 暴露）

为此，我们使用了三种类型的图

• 位于 sample_graphs/ 中的图，可以使用 kpkc.test.load_tester 进行测试。

• 我们还对具有参数 (k, min_s, max_s, a_1, a_2) 的随机图进行了基准测试，其中 k 是部分的数量，每个部分的大小在 [min_s, max_s] 范围内均匀分布。每个顶点 v 被分配一个从 [a_1, a_2] 均匀分布中选择的随机浮点数 p(v)。对于来自不同部分的任意一对 v、w，边以概率 (p(v) + p(w))/2 生成。

  这种方法在以下文献中描述

  • Grünert, Tore & Irnich, Stefan & Zimmermann, Hans-Jürgen & Schneider, Markus & Wulfhorst, Burkhard. (2001). K-分割图中的团及其在纺织工程中的应用

  可以使用 kpkc.test.get_random_k_partite_graph(k, min_s, max_s, a_1, a_2) 获取此类随机图。

• 此外，我们使用参数 (k, max_s, a) 对示例进行了基准测试，其中 k 表示部分数量。对于 i 在 1, ..., k 的范围内，部分的大小为 1 + ((max_s -1) * i) // k。

  设 f 是由 f(1) = 1 和 f(max_s) = a 确定的仿射函数。对于来自不同部分且大小分别为 s 和 t 的所有成对 v 和 w，边以概率 f(min(s, t)) 生成。

  这意味着大小为 1 的部分将具有所有邻居，而部分中的顶点越多，其边的密度就越低。

  可以通过 kpkc.test.get_random_k_partite_graph_2(k, max_s, a) 获取这样的随机图。

  在许多情况下，这比上面的随机图更自然。如果 k-完全图对应于某些匹配，那么这对应于选择越少，人们就越不挑剔的事实。例如

  假设该地区只有一个水泥厂，两个混凝土泵，二十辆混凝土搅拌车和二十个混凝土施工队。没有人会质疑水泥厂的质量，因为没有替代品。由于只有两个混凝土泵，卡车司机通常会愿意与两者都合作。同样，混凝土施工队通常会忍受两个泵操作员。然而，混凝土施工队可能会拒绝与一些卡车司机（总是迟到）合作，或者卡车司机可能会拒绝与一些施工队合作（总是订购比需要的更多的卡车）。

  特别是，sample_graphs/ 中的图表现得有点像这样：较小部分中的顶点比较大部分中的顶点有更多的邻居。有超过 1400 万个这样的图是我们想要检查的。这可以通过 kpkc 实现，而其他实现则似乎不可行。

结果是在 Intel i7-7700 CPU @3.60GHz 上获得的。

检查 k-完全图

我们测量确定完全图数量或找到第一个 k-完全图（如果有的话）所需的时间。

请注意，sample_graphs 中的图没有 k-完全图。

nan 表示计算在 1000 秒后中断（未确定）。

找到所有k-完全子图

我们测量找到所有k-完全子图所需的时间，如果这个时间与上述不同。

结论

根据上述时间，kpkc和FindClique似乎是寻找k-部分图中的k-完全子图的最佳选择。

• 如果所有顶点的预期邻居数量大致相同，那么FindClique是最佳选择。
• 如果有许多边并且预期的k-完全子图数量很大，那么FindClique是获取一些k-完全子图的最佳选择。
• 如果只预期有少数k-完全子图（如果有），且较大部分的顶点比较小部分的顶点有更少的邻居，那么kpkc是获取所有k-完全子图的最佳选择。

请注意，我们的FindClique实现似乎在查找所有k-完全子图方面比原始实现（未发表）更快

• Grünert, Tore & Irnich, Stefan & Zimmermann, Hans-Jürgen & Schneider, Markus & Wulfhorst, Burkhard. (2001). K-分割图中的团及其在纺织工程中的应用

和

• Mirghorbani, M. & Krokhmal, P.. (2013). 在k-部分图中寻找k-完全子图. 优化信件. 7. 10.1007/s11590-012-0536-y

对于具有参数(k, min_s, max_s, a_1, a_2)和k = 100的随机图，我们通过一个因子100提高了Grünert等人的基准。请注意，我们还将3.6 GHz用于100 MHz，从而提高了约28个改进因子。

Mirghorbani等人将FindClique的实现提高了至9倍，与Grünert等人相比。