clique {optpart}R Documentation

Maximal Clique Analysis

Description

Maximal clique analysis produces the set of maximal cliques of a dissimilarity or distance matrix. Maximal cliques are sets where every member of the set is <= alpha-dissimilar to every other member.

Usage

clique(dist,alphac,minsize=1,mult=100)
## S3 method for class 'clique'
summary(object, ...)
## S3 method for class 'clique'
plot(x, panel = 'all', ...)

Arguments

dist

an object of class ‘dist’ from dist, vegdist, or dsvdis

alphac

the dissimilarity threshold to establish the relationship

minsize

the minimum size clique to list in the results

mult

scratch space multiplier to control stack size (see below)

object

an object of class ‘clique’

...

ancillary arguments to summary or plot

x

an object of class ‘clique’

panel

an integer switch to indicate which panel to plot

Details

Maximal clique analysis produces a covering, as opposed to a partition, i.e. objects can belong to more than one clique, and every object belongs to at least one clique. The maximal clique solution is solved for by symbolic computation, as opposed to numerical computation, and produces a unique solution. The number of cliques produced cannot be known beforehand, and can significantly exceed the number of objects. The ‘mult’ argument controls the size of the stack to hold intermediate terms in the equation as the solution proceeds. At each iteration, the algorithm simplifies the equation to the extent possible, and recovers space used to hold terms that have been eliminated. Nonetheless, it is possible for the equation to grow quite large at intermediate steps. The initial value of ‘mult=100’ sets the stack to 100 times the number of objects in the dissimilarity/distance matrix. If the memory allocated is exceeded, the output is set to NULL, and a message is printed to increase the ‘mult’ argument to a higher value.

Value

produces a list with elements:

alphac

the threshold value used to establish the cliques

musubx

a matrix of object membership in each of the maximal cliques

member

a list of members of each clique

Note

WARNING. The run time of maximal clique analysis is approximately 2^n+n for n objects. The number of cliques generated, and the run time, is sensitive to ‘alpha’, as values of ‘alpha’ close to the mean dissimilarity of the matrix are likely to produce the most cliques and longest run time. A solution for 1200 objects once took approximately 20 CPU days on a SparcStation. The example shown below (100 objects) runs in a few seconds on a modern computer.

Author(s)

David W. Roberts droberts@montana.edu http://ecology.msu.montana.edu/labdsv/R

Examples

data(shoshveg) # produces a vegetation dataframe
dis.bc <- dsvdis(shoshveg,'bray/curtis') 
    # produces a Bray/Curtis dissimilarity matrix
cli.50 <- clique(dis.bc,0.5) # clusters at 0.5 dissimilarity, likely
    # to run for a few seconds in most PCs
summary(cli.50)

[Package optpart version 3.0-3 Index]