sf.apps.clique

Tools for users to identify large cliques in graphs.

A clique is a subgraph where all nodes are connected to each other. The maximum clique problem is to identify the largest clique in a graph. It has been shown that samples from GBS can be used to select dense subgraphs as a starting seed for heuristic algorithms [9].

See also

Maximum Clique

Algorithm

This module provides search(), a variant of the local search heuristics described in [14] and [15]. The algorithm proceeds as follows:

  1. A small clique in the graph is identified. The initial clique can be a single node, or it can be obtained by shrinking a random subgraph, for example obtained from GBS.

  2. The clique is grown as much as possible by adding nodes connected to all nodes in the clique.

  3. When no more growth is possible, a node in the clique is swapped with a node outside of it.

Steps 2-3 are repeated until a pre-determined number of steps have been completed, or until no more growth or swaps are possible.

Clique growth and swapping

A clique can be grown by evaluating the set \(C_0\) of nodes in the remainder of the graph that are connected to all nodes in the clique. A single node from \(C_0\) is selected and added to the clique. This process is repeated until \(C_0\) becomes empty. This is provided with the grow() function.

Searching the local space around a clique can be achieved by swapping a node from the clique with a node in the remainder of the graph. The first step is to evaluate the set \(C_1\) of nodes in the remainder of the graph that are connected to all but one of the nodes in the current clique. A swap is then performed by adding the node into the clique and removing the node in the clique that is not connected to it. This is provided with the swap() function.

Whenever the sets \(C_0\) and \(C_1\) used during growth and swapping have more than one element, there must be a choice of which node to add or swap. The supported choices are:

  • Select among candidate nodes uniformly at random;

  • Select the candidate node with the greatest degree, settling remaining ties uniformly at random;

  • Select the candidate node with the greatest node weight, settling remaining ties uniformly at random.

Using GBS to find a starting clique

Samples from GBS correspond to subgraphs that are likely to be dense. These subgraphs may not be cliques, which is the required input to the search() algorithm. To reconcile this, a subgraph may be shrunk using the shrink() function by removing nodes until the remainder forms a clique. This can be achieved by selecting the node with the lowest degree relative to the rest of subgraph and removing the node, repeating the process until a clique is found.

Functions

c_0(clique, graph)

Generates the set \(C_0\) of nodes that are connected to all nodes in the input clique subgraph.

c_1(clique, graph)

Generates the set \(C_1\) of nodes that are connected to all but one of the nodes in the input clique subgraph.

grow(clique, graph[, node_select])

Iteratively adds new nodes to the input clique to generate a larger clique.

is_clique(graph)

Determines if the input graph is a clique.

search(clique, graph, iterations[, node_select])

Local search algorithm for identifying large cliques.

shrink(subgraph, graph[, node_select])

Shrinks an input subgraph until it forms a clique.

swap(clique, graph[, node_select])

If possible, generates a new clique by swapping a node in the input clique with a node outside the clique.