PyKPartiteKClique

A python wrapper of https://github.com/kliem/KPartiteKClique.

Iterate over all k-cliques of a k-partite graph.

Requirements

• setuptools
• Cython

Quick start

A trivial example:

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

The default algorithm is kpkc, which first selects nodes with few edges:

>>> 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]]

The algorithm FindClique first selects parts with few nodes:

>>> 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]]

Benchmarks

We benchmark the following algorithms/implementations:

• kpkc (our implementation)
• FindClique (our implementation)
• Cliquer (exposed via SageMath)
• networkx
• mcqd (exposed via SageMath)

For this we use three types of graphs:

• Graphs in sample_graphs/ that can be tested with kpkc.test.load_tester.

• Also we benchmark random graphs with parameters (k, min_s, max_s, a_1, a_2), where k is the number of parts, each part has size in [min_s, max_s] chosen with uniform distribution. Each vertex v is assigned a random float p(v) chosen with uniform distribution from [a_1, a_2]. For all pairs v, w from different parts the edge is generated with probability (p(v) + p(w))/2.

  This approach is described in:

  • Grünert, Tore & Irnich, Stefan & Zimmermann, Hans-Jürgen & Schneider, Markus & Wulfhorst, Burkhard. (2001). Cliques in k-partite Graphs and their Application in Textile Engineering

  Such a random graph can be obtain with kpkc.test.get_random_k_partite_graph(k, min_s, max_s, a_1, a_2).

• In addition we benchmark examples with parameters (k, max_s, a), where k is the number of parts. Parts have sizes 1 + ((max_s -1) * i) // k for i in 1, ..., k.

  Let f be the affine function determined by f(1) = 1 and f(max_s) = a. For all pairs v, w from different parts with sizes s, t, the edge is generated with probability f(min(s, t)).

  This means parts of size 1 will have all neighbors and the more vertices a part has, the lower will be the density of its edges.

  Such a random graph can be obtain with kpkc.test.get_random_k_partite_graph_2(k, max_s, a).

  In many contexts this might be a more natural choice than the above random graph. If the k-clique corresponds to some matching, than this corresponds to the fact that fewer choices means that people will be less picky. Example:

  Suppose there is only one cement mill in the area, two concrete pumps, twenty conrete mixer trucks, and twenty concrete crews. Nobody can question the quality of the cement mill, because there is no alternative. As there is only two concrete pumps, the truck drivers will usually be willing to work with both of them. Likewise the concrete crews will usually put up with both pump operators. However, it is very much possible that the conrete crews might refuse to work with some truck drivers (always late) or the truck drivers might refuse to work with some crews (always order more trucks than they need).

  In particular, the graphs in sample_graphs/ behave somewhat like this: Vertices in smaller parts have more neighbors than vertices in larger parts. There are more than 14 million of those that we would like to check. This is feasible with kpkc and appears infeasible with the other implementations.

The results have been obtained with an Intel i7-7700 CPU @3.60GHz.

Checking for a k-clique

We time how long it takes to either determine the clique number or to find the first k-clique, if any.

Note that the graphs in sample_graphs do not have k-cliques.

nan indicates that the computation was interrupted after 1000s (without determination).

Finding all k-cliques

We time how long it takes to find all k-clique, if this time differs from above.

Conclusion

According to the above timings, kpkc and FindClique appear to be best choices for finding k-cliques in k-partite graphs.

• If all vertices are expected to have somewhat the same number of neighbors, then FindClique is the best choice.
• If there are many edges and the expected number of k-cliques is large, then FindClique is the best choice to obtain some k-cliques.
• If only few k-cliques (if any) are exepcted and vertices in larger parts have fewer neighbors than vertices in smaller parts, then kpkc is the best choice to obtain all k-cliques.

Note that our implementation of FindClique appears to be faster in finding all k-cliques than the original implementations (which are not published) in

• Grünert, Tore & Irnich, Stefan & Zimmermann, Hans-Jürgen & Schneider, Markus & Wulfhorst, Burkhard. (2001). Cliques in k-partite Graphs and their Application in Textile Engineering

and

• Mirghorbani, M. & Krokhmal, P.. (2013). On finding k-cliques in k-partite graphs. Optimization Letters. 7. 10.1007/s11590-012-0536-y

For random graphs with parameters (k, min_s, max_s, a_1, a_2) and k = 100 we improve the benchmarks of Grünert et. all by a factor of 100. Note that we also use 3.6 GHz instead of 100 MHz leaving an improvement factor of about 28.

Mirghorbani et. al. improved the implementation of FindClique by a factor of up to 9 in comparison to Grünert et. al.