Maximal Cliques - Split Approach - SplitCompletely revisited

          First in thread      Previous in thread      Next in thread

Here is another slightly improved version of the algorithm that doesn't bother to split sets whose children will be too small to be retained in the MaximalSetSet reactor.

Now, the MaximalCliques algorithm as written always discovers all of the maximal cliques of a graph, but this needn't be the case - an application may not need the smaller maximal cliques or may not be able to afford the time needed to construct them.

If the MaximalCliques algorithm uses a retention threshold great than 1, this change in SplitCompletely isn't needed - after all, the MaximalSetSet reactor is responsible for discarding sets whose cardinality is below the retention threshold. This change in SplitCompletely is for the sake of efficiency.

Version 3

SplitCompletely( in  Set              seedSet,
                 in  list<NonEdge>    nonEdges
                 out MaximalSetSet    maximalCliqueCandidates )
{
    int  retentionThreshold = maximalCliqueCandidates.RetentionThreshold();

    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 )
            {
                if ( splittableSet.Cardinality() > retentionThreshold )
                {
                    Set  splitChild1 = splittableSet;
                    Set  splitChild2 = splittableSet

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

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

There several areas for major improvement in this algorithm, and they involve the list of non-edges.

One obvious improvement involves the order in which the non-edges are processed in the outer loop. So far, I've let them be processed in the order in which they were received. A bit of analysis can determine, however, how interrelated each non-edge is to the other non-edges. Given this information, should non-edges that are weakly interrelated to other non-edges be processed first or last? This is one of many open problems.

Here is a parameterized version of algorithm for SplitCompletely that explicitly handles relevance, creates a list containing only relevant non-edges, and sorts the list of relevant non-edges prior to processing them. The AnalyzeAndSort algorithm parameter is left undefined for now.

Version 4

SplitCompletely( in  Set              seedSet,
                 in  list<NonEdge>    nonEdges
                 out MaximalSetSet    maximalCliqueCandidates )
{
    int  retentionThreshold = maximalCliqueCandidates.RetentionThreshold();

    maximalCliqueCandiates.AddSet( seedSet );

    list<NonEdge>  relevantNonEdges;

    foreach ( nonEdge in nonEdges )
    {
        if ( seedSet.Contains( nonEdge.Node1 ) && 
             seedSet.Contains( nonEdge.Node2 ) )
        {
            relevantNonEdges.Append( nonEdge );
        }
    }

    AnalyzeAndSort( relevantNonEdges );

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

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

        foreach ( splittableSet in splittableSets )
        {
            if ( splittableSet.Cardinality() > retentionThreshold )
            {
                Set  splitChild1 = splittableSet;
                Set  splitChild2 = splittableSet

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

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

Suppose that the list of non-edges contains the following three non-edges: (3, 5), (3, 7), and (5, 7). What is the effect of this 3-independent-set upon the resulting set of maximal cliques?

Let's assume that the they are the first three non-edges processed and that the seed set is { 1, 2, 3, 4, 5, 6, 7 }.

action                              set of maximal clique candidates

add seed set                        { 1, 2, 3, 4, 5, 6, 7 }

remove sets containing (3, 5)

    { 1, 2, 3, 4, 5, 6, 7 }

split { 1, 2, 3, 4, 5, 6, 7 }

    { 1, 2, 3, 4, 6, 7 }
    { 1, 2, 4, 5, 6, 7 }

add split children                  { 1, 2, 3, 4, 6, 7 }
                                    { 1, 2, 4, 5, 6, 7 }

remove sets containing (3, 7)

    { 1, 2, 3, 4, 6, 7 }            { 1, 2, 4, 5, 6, 7 }

split { 1, 2, 3, 4, 6, 7 }          { 1, 2, 4, 5, 6, 7 }

    { 1. 2. 3. 4. 6 }
    { 1, 2, 4, 6, 7 }

add split children                  { 1, 2, 4, 5, 6, 7 }
                                    { 1, 2, 3, 4, 6 }
                                    { 1, 2, 4, 6, 7 }  discarded

remove sets containing (5, 7)       { 1, 2, 3, 4, 6 }

    { 1, 2, 4, 5, 6, 7 }

split { 1, 2, 4, 5, 6, 7 }          { 1, 2, 3, 4, 6 }

    { 1, 2, 4, 5, 6 }
    { 1, 2, 4, 6, 7 }

add split children                  { 1, 2, 3, 4, 6 }
                                    { 1, 2, 4, 5, 6 }
                                    { 1, 2, 4, 6, 7 }

The set { 1, 2, 4, 6, 7 } was discarded because it was not a maximal set in that collection.

Note that we started with three non-edges that constituted a 3-independent-set and ended up with 3 maximal clique candidates, each of which contains precisely one of the three nodes in the independent set.

This observation will lead to a more complex variant of the SplitCompletely algorithm that constructs a set of independent sets that cover the nodes that participate in non-edges and then, for each independent set, distributes the nodes of the independent set onto different maximal clique candidates.

Confusing as stated, I fear - I'll discuss this approach and present an algorithm for carrying it out in the near future.

For now, it is sufficient to note that the list of relevant non-edges may be analyzed and that the results of that analysis may guide the processing of the non-edges and may, indeed, make actually splitting the sets unnecessary,

MaximalCliques - Split Approach - IdentifyMaximalCliques revisited

This is the IdentifyMaximalCliques algorithm as I presented it on May 26:

Version 1

IdentifyMaximalCliques( in  Graph         graph,
                        out vector<Set>   maximalCliques )
{
    MaximalSetSet   nodeMaximalCliqueCandidates;
    MaximalSetSet   graphMaximalCliqueCandidates;

    foreach ( node in graph.Nodes )
    {
        Set  seedSet = graph.AugmentedAdjacencySet( node );

        seedSet.IntersectWith( Set.Range( node, graph.NumNodes - 1 ) );

        SplitCompletely( seedSet, graph.NonEdges, nodeMaximalCliqueCandidates );

        graphMaximalCliqueCandidates.AddSetsStolenFrom( 
		    nodeMaximalCliqueCandidates );    
    }

    graphMaximalCliqueCandidates.RemoveAllSets( maximalCliques );
}

One enhancement is to allow a client to specify a retention threshold in case the smaller maximal cliques either aren't needed or can't be afforded.

Version 2

IdentifyMaximalCliques( in  Graph         graph,
                        in  int           retentionThreshold,
                        out vector<Set>   maximalCliques )
{
    MaximalSetSet   nodeMaximalCliqueCandidates;
    MaximalSetSet   graphMaximalCliqueCandidates;

    nodeMaximalCliqueCandidates.SetRetentionThreshold( retentionThreshold );

    foreach ( node in graph.Nodes )
    {
        Set  seedSet = graph.AugmentedAdjacencySet( node );

        seedSet.IntersectWith( Set.Range( node, graph.NumNodes - 1 ) );

        SplitCompletely( seedSet, graph.NonEdges, nodeMaximalCliqueCandidates );

        graphMaximalCliqueCandidates.AddSetsStolenFrom( 
		    nodeMaximalCliqueCandidates );    
    }

    graphMaximalCliqueCandidates.RemoveAllSets( maximalCliques );
}

For the sake of initial simplicity, the initial version of this algorithm simply solved the nodes of the graph in ascending-node-ID order. This is almost certainly not the most efficient way of proceeding. For example, it may be more effective to process nodes having short augmented adjacency sets first. The order in which to solve the nodes of a graph is an open question.

For now, I'll assume that there is a function named PickNodeToSolve that applies an heuristic to determine which node to solve next.

Here is a parameterized version of IdentifyMaximalCliques that calls PickNodeToSolve as needed:

Version 3

IdentifyMaximalCliques( in  Graph         graph,
                        in  int           retentionThreshold,
                        out vector<Set>   maximalCliques )
{
    MaximalSetSet   nodeMaximalCliqueCandidates;
    MaximalSetSet   graphMaximalCliqueCandidates;

    nodeMaximalCliqueCandidates.SetRetentionThreshold( retentionThreshold );

    Set  unsolvedNodes = graph.Nodes;

    while ( unsolvedNodes.Cardinality > 0 )
    {
        int  node = PickNodeToSolve( unsolvedNodes, graph );

        Set  seedSet = graph.AugmentedAdjacencySet( node );

        seedSet.IntersectWith( unsolvedNodes );

        SplitCompletely( seedSet, graph.NonEdges, nodeMaximalCliqueCandidates );

        graphMaximalCliqueCandidates.AddSetsStolenFrom( 
		    nodeMaximalCliqueCandidates );

        unsolvedNodes.RemoveElement( node );
    }

    graphMaximalCliqueCandidates.RemoveAllSets( maximalCliques );
}

This method should be called with a retention threshold of 1 to construct all of the maximal cliques of a graph.

Maximum Cliques - Split Approach

A closely related problem is to construct all of the maximum cliques of a graph. A maximum clique of a graph is a clique larger than any other clique of a graph. There may be more than one maximum clique.

We can adapt the IdentifyMaximalCliques algorithm to construct the maximum cliques of a graph by adjusting the retention thresholds of both MaximalSetSet objects after each iteration of the loop. The thresholds should be set to the cardinality of the largest set in the nodeMaximalCliqueCandidates collection.

The names of the objects in the method will be changed appropriately.

The retentionThreshold parameter can be used to pass a hint to the method that the maximum cliques of the graph are at least as large as the specified retentionThreshold.

IdentifyMaximumCliques( in  Graph         graph,
                        in  int           retentionThreshold,
                        out  vector<Set>   maximumCliques )
{
    MaximalSetSet   nodeMaximumCliqueCandidates;
    MaximalSetSet   graphMaximumCliqueCandidates;

    nodeMaximumCliqueCandidates.SetRetentionThreshold( retentionThreshold );

    Set  unsolvedNodes = graph.Nodes;

    while ( unsolvedNodes.Cardinality > 0 )
    {
        int  node = PickNodeToSolve( unsolvedNodes, graph );

        Set  seedSet = graph.AugmentedAdjacencySet( node );

        seedSet.IntersectWith( unsolvedNodes );

        SplitCompletely( seedSet, graph.NonEdges, nodeMaximumCliqueCandidates );

        int  largestSetSize = nodeMaximumCliqueCandidates.GetLargestSetSize();

        nodeMaximumCliqueCandidates.SetRetentionThreshold( largestSetSize );
        graphMaximumCliqueCandidates.SetRetentionThreshold( largestSetSize );

        graphMaximumCliqueCandidates.AddSetsStolenFrom( 
		    nodeMaximumCliqueCandidates );

        unsolvedNodes.RemoveElement( node );
    }

    graphMaximumCliqueCandidates.RemoveAllSets( maximumCliques );
}

Maximum Clique Size - Split Approach

We may only need to know the cardinality of a maximum clique of a graph.

The following method discards maximum clique candidates once the cardinality of the largest set is known.

IdentifyMaximumCliqueSize( in  Graph  graph,
                           in  int    retentionThreshold,
                           out int    maximumCliqueSize )
{
    MaximalSetSet   nodeMaximumCliqueCandidates;

    nodeMaximumCliqueCandidates.SetRetentionThreshold( retentionThreshold );

    Set  unsolvedNodes = graph.Nodes;

    while ( unsolvedNodes.Cardinality > 0 )
    {
        int  node = PickNodeToSolve( unsolvedNodes, graph );

        Set  seedSet = graph.AugmentedAdjacencySet( node );

        seedSet.IntersectWith( unsolvedNodes );

        SplitCompletely( seedSet, graph.NonEdges, nodeMaximumCliqueCandidates );

        int  largestSetSize = nodeMaximumCliqueCandidates.GetLargestSetSize();

        nodeMaximumCliqueCandidates.RemoveAllSets();

        nodeMaximumCliqueCandidates.SetRetentionThreshold( largestSetSize );

        unsolvedNodes.RemoveElement( node );
    }

    maximumCliqueSize = nodeMaximumCliqueCandidates.RetentionThreshold;
}

k-Clique Exists - Split Approach

This is the famous Clique problem - that of determining whether a graph contains a k-clique, a clique size k.

If a k-clique does exist, this algorithm returns an exemplar clique of cardinality k or greater. It could easily be adapted to return all all k-cliques.

DetermineWhetherKCliqueExists( in  Graph  graph,
                               in  int    k,
                               out bool   kCliqueExists,
                               out Set    exemplarClique )
{
    MaximalSetSet   kCliqueCandidates;

    kCliqueCandidates.SetRetentionThreshold( k );

    Set  unsolvedNodes = graph.Nodes;

    while ( unsolvedNodes.Cardinality > 0 )
    {
        int  node = PickNodeToSolve( unsolvedNodes, graph );

        Set  seedSet = graph.AugmentedAdjacencySet( node );

        seedSet.IntersectWith( unsolvedNodes );

        SplitCompletely( seedSet, graph.NonEdges, kCliqueCandidates );

        if ( kCliqueCandidates.GetLargestSetCardinality() > 0 )
        {
            kCliqueExists = true;
            exemplarKClique = kCliqueCandidates.GetLargestSet( exemplarClique );
            return;
        }

        unsolvedNodes.RemoveElement( node );
    }

    kCliqueExists = false;
    exemplarClique.RemoveAllElements();
}

          First in thread      Previous in thread      Next in thread

Copyright and Legal Notices

All Rights Reserved.