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
Algorithm¶
This module provides search()
, a variant of the local search heuristics described in
[14] and [15]. The algorithm proceeds as follows:
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.
The clique is grown as much as possible by adding nodes connected to all nodes in the clique.
When no more growth is possible, a node in the clique is swapped with a node outside of it.
Steps 23 are repeated until a predetermined 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

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

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

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

Determines if the input graph is a clique. 

Local search algorithm for identifying large cliques. 

Shrinks an input subgraph until it forms a clique. 

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