Contents - Index

NETWORK > SUBGROUPS > CLIQUES

PURPOSE Find all cliques in a network.

DESCRIPTION A clique is a maximally complete subgraph.  
The program implements the Bron and Kerbosch (1973) algorithm to find all Luce and Perry (1949) cliques greater than a specified size.  The routine will also provide an analysis of the overlapping structure of the cliques.  This analysis gives information on the number of times each pair of actors are in the same clique, and gives a  hierarchical clustering based upon this information. It is also does the dual operation by examining the number of actors a pair of cliques has in common and submits this to an hierarchical clustering routine. In addition the routine calculates a clique participation score which measures the extent to which an actor is in any of the cliques. 

PARAMETERS
Input dataset
Name of file containing data to be analyzed. Data type: Graph.
  
Minimum Size: (Default = 3)
This gives the smallest group size which is to be considered a clique. The range is 1 to N.

Analyze pattern of overlaps?  (Default = YES).
Yes means that an analysis of clique overlap will be performed. This includes the construction of a clique co-membership matrix, and an hierarchical clustering which is saved in a partition indicator matrix as described below. The co-clique matrix is also constructed and this is also submitted to an hierarchical clustering routine.
No restricts the analysis to identifying the cliques and calculating the participation scores.
  
Diagram Type: (Default = 'Tree diagram')
When analyzing the overlap the clustering diagram can either be a Tree Diagram or a Dendrogram.

(Output) Clique indicator matrix: (Default = 'CliquesSets').
Name of file which contains a clique by actor incidence matrix.  A 1 in column i row j indicates that actor j is a member of clique i.  This matrix is not displayed in the LOG FILE.

(Output) Co-membership matrix: (Default = 'CliquesOver').
Name of file which contains clique overlap matrix described in LOG FILE below.  Note that if no analysis of pattern overlaps was chosen then this file is not created.

(Output) Partition indicator matrix: (Default = 'CliquePart').
Name of file which contains partition indicator matrix derived from overlap analysis.  The partition indicator matrix corresponds to the hierarchical clustering displayed in the LOG FILE. A value of k in a column labeled i and row j means that actor j is in partition k and is in i cliques with every other member of partition k.  Actor k is always a member of partition k, and is a representative label for the group.

(Output) Clique proximities:(Default='CliqueParticipation)
Name of file that will contain the clique participation scores. This is a matrix with the vertices as the rows and the cliques as the columns. A value of x in row i column j indicates that vertex i has a proportion x of the required links to be in clique number j. Hence if i is in clique j this score will be 1. If i is not adjacent to any vertices in clique j this will be zero. High scores indicate that the vertex is nearly a clique member.


LOG FILE Number of cliques found.
List of cliques, labeled - each clique is specified by the vertices it contains.

The clique participation matrix.

The following output is also produced if YES was inserted on the form in reply to the question 'Analyze pattern of overlaps?' The first part of the output will be the tree diagram or dendrogram corresponding to the clustering of the actor by actor co-membership matrix. In the matrix  a value of k in row i column j means that vertices i and j occurred in the same clique k times.  The ith diagonal entry gives the number of cliques which contain i.

The tree diagram (or a dendrogram) re-orders the actors so that they are located close to other actors in similar clusters. The level at which any pair of actors are aggregated is the point at which both can be reached by tracing from the start to the actors from right to left. The scale at the top gives the level at which they are clustered and corresponds to the number of overlaps. The diagram can be printed or saved. Parts of the diagram can be viewed by moving the mouse to the split point in a tree diagram or the beginning of a line in the dendrogram and clicking. The first click will highlight a portion of the diagram and the second click will display just the highlighted portion. To return to the original right click on the mouse. There is also a simple zoom facility simply change the values and then press enter. If the labels need to be edited (particularly the scale labels) then you should take the partition indicator matrix into the spreadsheet editor remove or reduce the labels and then submit the edited data to Tools>Dendrogram>Draw. 

   
Behind the diagram is a window containing the number of cliques and a list as specified above. This is followed by a clustering diagram representing the same clustering as the tree diagram (or dendrogram).  The columns are rearranged and labeled.  A '·' in row label i column label j means that vertex j was not in i cliques with any other vertex.  An 'X' indicates that vertex j was in i cliques with all vertices on the same row as j which can be found by tracing across that row without encountering a space.

This is followed by the clique by clique co-membership matrix. In the matrix  a value of k in row i column j means that cliques i and j contain k actors in common.  The ith diagonal entry gives the number of actors in clique i. This is followed by a clustering diagram corresponding to an hierarchical clustering of the clique by clique co-membership matrix.


TIMING Algorithm is exponential.

COMMENTS None.

REFERENCES Luce R and Perry A (1949).  A method of matrix analysis of group structure.  Psychometrika 14, 95-116.

Bron C and Kerbosch J (1973).  Finding all cliques of an undirected graph.  Comm of the ACM 16, 575-577.