nz.ac.waikato.mcennis.rat.graph.algorithm.clustering
Class EnumerateMaximalCliques

java.lang.Object
  nz.ac.waikato.mcennis.rat.graph.model.ModelShell
      nz.ac.waikato.mcennis.rat.graph.algorithm.clustering.EnumerateMaximalCliques

All Implemented Interfaces:

java.io.Serializable, Component, Algorithm, Model

public class EnumerateMaximalCliques
extends ModelShell
implements Algorithm

Maximal cliques are defined as a fully connected subgraph such that any additional node added to the subgraph is not fully connected. This problem is NP-Complete, but can be completed in O(nlog(n)) where n is the number of nodes in the graph and exponential over k where k is the maximum out degree of the graph. For many applications, including web page hyperlink structure and social network data, k is suffeciantly small that the algorithm's cost is manageable. This a rediscovery of the Bron-Berbosch Algorithm (1973) C. Bron, J. Kerboach, Algorithm 457. 1973. Finding all cliques of an uncirected graph. Communications of the ACM. 16(9):575-577.

See Also:

Serialized Form

Field Summary

Fields inherited from class nz.ac.waikato.mcennis.rat.graph.model.ModelShell

listener

Constructor Summary

EnumerateMaximalCliques()
Creates a new instance of EnumerateMaximalCliques

Method Summary

protected void	assertMaximal(java.util.HashSet<Clique> maximal) This functions identify those cliques that are subsets of maixmal cliques rather than maximal cliques themselves.
void	execute(Graph g) execute the algorithm against the given graph
protected void	extend(Clique seed, Actor[] intersection) create a set of new cliques of size n+1 from a clique of size n.
java.util.List<IODescriptor>	getInputType() The input type describes all the different kinds of graph objects that are utilized (and hence required) by this object.
java.util.List<IODescriptor>	getOutputType() The output type describes all the different kinds of graph objects that are created during the execution of this algorithm.
Properties	getParameter() List of all parameters this component accepts.
Parameter	getParameter(java.lang.String param) Returns the specific parameter identified by its key-name.
void	init(Properties map) Parameters for init: 'name' - name for this instance of the algorithm.
EnumerateMaximalCliques	prototype() All Components implement the prototype pattern.

Methods inherited from class nz.ac.waikato.mcennis.rat.graph.model.ModelShell

addListener, fireChange

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface nz.ac.waikato.mcennis.rat.graph.model.Model

addListener

Constructor Detail

EnumerateMaximalCliques

public EnumerateMaximalCliques()

Creates a new instance of EnumerateMaximalCliques

Method Detail

execute

public void execute(Graph g)

Description copied from interface: Algorithm

execute the algorithm against the given graph

Specified by:

execute in interface Algorithm

Parameters:

g - graph to be modified

extend

protected void extend(Clique seed,
                      Actor[] intersection)

create a set of new cliques of size n+1 from a clique of size n. This only need to be done for actors strictly greater than the largest actor in the set. This is acceptable since every clique involving a smaller actor will already generate this clique in a previous iteration. However, this generates some spurious maximal cliques that are subsets of other cliques. These are weeded out by assertMaximal algorithm

assertMaximal

protected void assertMaximal(java.util.HashSet<Clique> maximal)

This functions identify those cliques that are subsets of maixmal cliques rather than maximal cliques themselves. These are removed from the set of maximal cliques before they are added to the global clique set. The test is to sequentially test whether or not there exists a node in the intersection that creates a new clique (hence the current clique is not maximal). Since this clique will be created by another clique or seed, this clique can be safely discarded.

getInputType

public java.util.List<IODescriptor> getInputType()

Description copied from interface: Component

The input type describes all the different kinds of graph objects that are utilized (and hence required) by this object. This result is only guaranteed to be fixed if structural parameters are not modified. This is an empty array if there is no input.

Specified by:

getInputType in interface Component

Returns:

IODescriptor array for this component

See Also:

IODescriptor

getOutputType

public java.util.List<IODescriptor> getOutputType()

Description copied from interface: Component

The output type describes all the different kinds of graph objects that are created during the execution of this algorithm. The result is only guaranteed to be fixed if structural parameters are not modified. This is an empty array if there is no output.

Specified by:

getOutputType in interface Component

Returns:

IODescriptor array for this component

See Also:

IODescriptor

getParameter

public Properties getParameter()

Description copied from interface: Component

List of all parameters this component accepts. Each parameter also has a distinct key-name used when initializing the object using the init method. If there are no parameters, null is returned.

Specified by:

getParameter in interface Component

Returns:

read-only array of Parameters

getParameter

public Parameter getParameter(java.lang.String param)

Description copied from interface: Component

Returns the specific parameter identified by its key-name. If no parameter is found with this key-name, null is returned.

Specified by:

getParameter in interface Component

Parameters:

param - key-name of the parameter

Returns:

named parameter

init

public void init(Properties map)

Parameters for init:

1. 'name' - name for this instance of the algorithm. Default 'Enumerate Maximal Cliques'.
2. 'relation' - name of the type (relation) of link to be used. Default 'Knows'.
3. 'actorType' - naem of the actor type (mode) to be used. Default 'User'.
4. 'graphIDPrefix' - name of the prefix for the ids of generated graphs. Default 'clique'.

Input 1 - Link
Output 1 - Graph

Specified by:

init in interface Component

Parameters:

map - map of the given properties naming parameters and their values in a string

prototype

public EnumerateMaximalCliques prototype()

Description copied from interface: Component

All Components implement the prototype pattern. The new parameter has no common resources to the original that are not static resources o the class.

Specified by:

prototype in interface Component

Specified by:

prototype in interface Algorithm

Returns:

default-parameter version of the same class as the original.