Maximal Cliques - An example of the Split Completely algorithm

          First in thread      Previous in thread      Next in thread

This is the algorithm that I outlined on May 26 for constructing all maximal-clique candidates from the augmented adjacency set of a node in a graph:

Version 1

SplitCompletely( in  Set              seedSet,
                 in  list<NonEdge>    nonEdges
                 out MaximalSetSet    maximalCliqueCandidates )
{
    maximalCliqueCandiates.AddSet( seedSet );

    foreach ( nonEdge in nonEdges )
    {
        vector<Set>  splittableSets;

        maximalCliqueCandidates.RemoveSplittableSets( 
            splittableSets, nonEdge.Node1, nonEdge.Node2 );

        foreach ( splittableSet in splittableSets )
        {
            Set  splitChild1 = splittableSet;
            Set  splitChild2 = splittableSet

            splitChild1.RemoveElement( nonEdge.Node1 );
            splitChild2.RemoveElement( nonEdge.Node2 );

            maximalCliqueCandidates.AddSet( splitChild1 );
            maximalCliqueCandidates.AddSet( splitChild2 );
        }
    }
}

Here is a slightly improved algorithm that determines which non-edges are relevant (have both of their end-nodes in seedSet) and only attempts to remove splittable sets for relevant non-edges.

Version 2

SplitCompletely( in  Set              seedSet,
                 in  list<NonEdge>    nonEdges
                 out MaximalSetSet    maximalCliqueCandidates )
{
    maximalCliqueCandiates.AddSet( seedSet );

    identify which non-edges are relevant (have both end-nodes in seedSet)

    foreach ( nonEdge in nonEdges )
    {
        if ( nonEdge is relevant )
        {
            vector<Set>  splittableSets;

            maximalCliqueCandidates.RemoveSplittableSets( 
                splittableSets, nonEdge.Node1, nonEdge.Node2 );

            foreach ( splittableSet in splittableSets )
            {
                Set  splitChild1 = splittableSet;
                Set  splitChild2 = splittableSet

                splitChild1.RemoveElement( nonEdge.Node1 );
                splitChild2.RemoveElement( nonEdge.Node2 );

                maximalCliqueCandidates.AddSet( splitChild1 );
                maximalCliqueCandidates.AddSet( splitChild2 );
            }
        }
    }
}

There is nothing like an example.

In this example, a 20-node graph was generated with the probability of an edge being 0.7. The SplitCompletely algorithm was run with the augmented adjacency set for node 0 being passed as the seedSet, the graph's set of non-edges being passed as nonEdges, and an empty MaximalSetSet being passed as maximalCliqueCandidates.

Augmented Adjacency Sets for Graph

0 : { 0, 1, 2, 5, 6, 7, 9, 11, 16, 17, 19 }
1 : { 0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 13, 14, 16, 17, 18, 19 }
2 : { 0, 1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18 }
3 : { 1, 2, 3, 4, 5, 6, 8, 9, 10, 13, 15, 16, 18, 19 }
4 : { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19 }
5 : { 0, 1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19 }
6 : { 0, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 17, 19 }
7 : { 0, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16 }
8 : { 1, 2, 3, 4, 5, 8, 9, 11, 12, 13, 14, 16, 19 }
9 : { 0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19 }
10 : { 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19 }
11 : { 0, 1, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19 }
12 : { 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19 }
13 : { 1, 3, 4, 5, 7, 8, 10, 11, 12, 13, 14, 16, 17, 18, 19 }
14 : { 1, 2, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15, 17 }
15 : { 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 17, 18, 19 }
16 : { 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 16, 17, 18 }
17 : { 0, 1, 5, 6, 9, 10, 12, 13, 14, 15, 16, 17, 18 }
18 : { 1, 2, 3, 4, 5, 9, 10, 11, 12, 13, 15, 16, 17, 18 }
19 : { 0, 1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 19 }

Solving node 0

Considering the (possibly reduced) augmented adjacency set 
{ 0, 1, 2, 5, 6, 7, 9, 11, 16, 17, 19 } :

--- adding it to the set of maximal clique candidates

determining which non-edges are relevant
non-edge  (  1,  6 )
non-edge  (  1,  7 )
non-edge  (  2,  5 )
non-edge  (  2,  7 )
non-edge  (  2, 11 )
non-edge  (  2, 17 )
non-edge  (  2, 19 )
non-edge  (  6,  9 )
non-edge  (  6, 11 )
non-edge  (  6, 16 )
non-edge  (  7,  9 )
non-edge  (  7, 17 )
non-edge  (  7, 19 )
non-edge  ( 11, 17 )
non-edge  ( 16, 19 )
non-edge  ( 17, 19 )
16 out of 54 non-edges are relevant

Processing non-edge ( 1, 6 )
--- Removing 1 splittable set from the set of maximal-clique candidates
--- Splitting set { 0, 1, 2, 5, 6, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 2, 5, 6, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 2, 5, 7, 9, 11, 16, 17, 19 }
Processing non-edge ( 1, 7 )
--- Removing 1 splittable set from the set of maximal-clique candidates
--- Splitting set { 0, 1, 2, 5, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 2, 5, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 2, 5, 9, 11, 16, 17, 19 }
Processing non-edge ( 2, 5 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 1, 2, 5, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 2, 9, 11, 16, 17, 19 }
--- Splitting set { 0, 2, 5, 6, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 6, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 2, 6, 7, 9, 11, 16, 17, 19 }
Processing non-edge ( 2, 7 )
--- Removing 1 splittable set from the set of maximal-clique candidates
--- Splitting set { 0, 2, 6, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 6, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 2, 6, 9, 11, 16, 17, 19 }
Processing non-edge ( 2, 11 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 1, 2, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 2, 9, 16, 17, 19 }
--- Splitting set { 0, 2, 6, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 6, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 2, 6, 9, 16, 17, 19 }
Processing non-edge ( 2, 17 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 1, 2, 9, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 9, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 2, 9, 16, 19 }
--- Splitting set { 0, 2, 6, 9, 16, 17, 19 }
--- --- adding to candidates : { 0, 6, 9, 16, 17, 19 }
--- --- adding to candidates : { 0, 2, 6, 9, 16, 19 }
Processing non-edge ( 2, 19 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 1, 2, 9, 16, 19 }
--- --- adding to candidates : { 0, 1, 9, 16, 19 }
--- --- adding to candidates : { 0, 1, 2, 9, 16 }
--- Splitting set { 0, 2, 6, 9, 16, 19 }
--- --- adding to candidates : { 0, 6, 9, 16, 19 }
--- --- adding to candidates : { 0, 2, 6, 9, 16 }
Processing non-edge ( 6, 9 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 2, 6, 9, 16 }
--- --- adding to candidates : { 0, 2, 9, 16 }
--- --- adding to candidates : { 0, 2, 6, 16 }
--- Splitting set { 0, 5, 6, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 6, 7, 11, 16, 17, 19 }
Processing non-edge ( 6, 11 )
--- Removing 1 splittable set from the set of maximal-clique candidates
--- Splitting set { 0, 5, 6, 7, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 7, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 6, 7, 16, 17, 19 }
Processing non-edge ( 6, 16 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 2, 6, 16 }
--- --- adding to candidates : { 0, 2, 16 }
--- --- adding to candidates : { 0, 2, 6 }
--- Splitting set { 0, 5, 6, 7, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 7, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 6, 7, 17, 19 }
Processing non-edge ( 7, 9 )
--- Removing 1 splittable set from the set of maximal-clique candidates
--- Splitting set { 0, 5, 7, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 7, 11, 16, 17, 19 }
Processing non-edge ( 7, 17 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 5, 6, 7, 17, 19 }
--- --- adding to candidates : { 0, 5, 6, 17, 19 }
--- --- adding to candidates : { 0, 5, 6, 7, 19 }
--- Splitting set { 0, 5, 7, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 5, 7, 11, 16, 19 }
Processing non-edge ( 7, 19 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 5, 6, 7, 19 }
--- --- adding to candidates : { 0, 5, 6, 19 }
--- --- adding to candidates : { 0, 5, 6, 7 }
--- Splitting set { 0, 5, 7, 11, 16, 19 }
--- --- adding to candidates : { 0, 5, 11, 16, 19 }
--- --- adding to candidates : { 0, 5, 7, 11, 16 }
Processing non-edge ( 11, 17 )
--- Removing 1 splittable set from the set of maximal-clique candidates
--- Splitting set { 0, 1, 5, 9, 11, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 11, 16, 19 }
Processing non-edge ( 16, 19 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 1, 5, 9, 16, 17, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 17, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 16, 17 }
--- Splitting set { 0, 1, 5, 9, 11, 16, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 11, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 11, 16 }
Processing non-edge ( 17, 19 )
--- Removing 2 splittable sets from the set of maximal-clique candidates
--- Splitting set { 0, 5, 6, 17, 19 }
--- --- adding to candidates : { 0, 5, 6, 19 }
--- --- adding to candidates : { 0, 5, 6, 17 }
--- Splitting set { 0, 1, 5, 9, 17, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 19 }
--- --- adding to candidates : { 0, 1, 5, 9, 17 }


Candidates for maximal 6-cliques : 

{ 0, 1, 5, 9, 11, 16 }
{ 0, 1, 5, 9, 16, 17 }
{ 0, 1, 5, 9, 11, 19 }

Candidates for maximal 5-cliques : 

{ 0, 1, 2, 9, 16 }
{ 0, 5, 7, 11, 16 }

Candidates for maximal 4-cliques : 

{ 0, 5, 6, 7 }
{ 0, 5, 6, 17 }
{ 0, 5, 6, 19 }

Candidates for maximal 3-cliques : 

{ 0, 2, 6 }

The reason why these results are considered only candidates for maximal cliques is because only a single node of the graph has been 'solved' - it is quite possible that the results from solving other nodes in the graph will contain sets that are supersets of some of these.

          First in thread      Previous in thread      Next in thread

Errors and corrections

I make mistakes in the best of times, even when I have the luxury of time and no deadlines, and I'm afraid I'll make them while writing in this blog.

I've already made a few big ones and have corrected them as soon as possible.

My apologies in advance for any inconvenience or confusion that any errors may cause.

Copyright and Legal Notices

All Rights Reserved.