Maximal Clique Analysis
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.
clique(dist,alphac,minsize=1,mult=100) ## S3 method for class 'clique' summary(object, ...) ## S3 method for class 'clique' plot(x, panel = 'all', ...)
dist |
|
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 |
x |
an object of class ‘clique’ |
panel |
an integer switch to indicate which panel to plot |
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.
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 |
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.
David W. Roberts droberts@montana.edu http://ecology.msu.montana.edu/labdsv/R
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)Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.