clique: Maximal Clique Analysis

In optpart: Optimal Partitioning of Similarity Relations

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 [e-mail] 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)

Example output

Loading required package: cluster
Loading required package: labdsv
Loading required package: mgcv
Loading required package: nlme
This is mgcv 1.8-33. For overview type 'help("mgcv-package")'.
This is labdsv 2.0-1
convert existing ordinations with as.dsvord()

Attaching package: ‘labdsv’

The following object is masked from ‘package:stats’:

    density

Loading required package: MASS
Loading required package: plotrix
162 maximal cliques at alphac =  0.5 
minimum size =  1 
maximum size =  10 

optpart documentation built on March 26, 2020, 6:18 p.m.