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:

  • Grunert, 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 paramters (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(a) = max_s. 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

• Grunert, 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

It is significantly faster in finding the first k-clique: All cases with random graphs from the above two papers could be handled in less than a second, with three exceptions:

• (100, 10, 10, 0.92, 0.92), which takes 5 seconds now, instead of 4000 seconds originally by Grunert et. al.,
• (100, 10, 10, 0,94, 0.94) remains infeasible in the given time,
• (100, 10, 10, 0,95, 0.95) remains infeasible in the given time. The original implementation of FindClique by Grundert et. al. apparently needed more than 100 seconds for random graphs with several different parameters to find the first k-clique.

The paper by Mirghorbani and Krokhmal lists several new parameters to time obtaining the first k-clique. We could not reproduce timings above one tenth of a millisecond, even in those cases that apparently took 10, 50 and 250 seconds respectively.