Networks -> Subgroups -> K-Plex

Contents - Index

NETWORK > SUBGROUPS > K-PLEX

PURPOSE Find all k-plexes in a network.

DESCRIPTION A k-plex is a maximal subgraph with the following property: each vertex of the induced subgraph is connected to at least n-k other vertices, where n is the number of vertices in the induced subgraph. The basic algorithm is a depth first search.

The routine will also provide an analysis of the overlapping structure of the k-plexes. This analysis gives information on the number of times each pair of actors are in the same k-plex and gives an hierarchical clustering based upon this information.

PARAMETERS
Input dataset:
Name of file containing network to be analyzed. Data type: Graph.

Value of K: (Default = 2)
The value of k specifies the relative minimum size of the degree of each vertex compared with the size of the k-plex. A value of 1 corresponds to a Luce and Perry clique. Every vertex in a k-plex of size n has degree at least n-k in the subgraph induced by the k-plex. The range of k is 1 to N. (A value of N would give the whole graph as the only k-plex).

Minimum Size: (Default = 3)
This gives the smallest group size which is to be considered a k-plex. The range is 1 to N, normally this should be at least K+2.

Analyze pattern of overlaps? (Default = YES).

Yes means that an analysis of k-plex overlap will be performed. This includes the construction of an k-plex co-membership matrix, and an hierarchical clustering which is saved in a partition indicator matrix as described below.

No restricts the analysis to identifying k-plexes only.

Diagram Type: (Default = 'Tree diagram')
When analyzing the overlap the clustering diagram can either be a Tree Diagram or a Dendrogram.

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

(Output) Co-membership matrix: (Default = 'KplexOvr').
Name of file which contains k-plex 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 = 'KplexPrt').
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 m in a column labeled i and row j means that actor j is in partition m and is in i k-plexes with every other member of partition m. Actor m is always a member of partition m, and is a representative label for the group.

LOG FILE Number of k-plexes found.
List of k-plexes, labeled - each k-plex is specified by the vertices it contains.

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 single link clustering of the k-plex overlap matrix. In the k-plex overlap matrix a value of m in row i column j means that vertices i and j occurred in the same k-plex m times. The ith diagonal entry gives the number of k-plexes 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 k-plexes 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 k-plexes with any other vertex. An 'X' indicates that vertex j was in i k-plexes with all vertices on the same row as j which can be found by tracing across that row without encountering a space.

TIMING Algorithm is exponential.

COMMENTS It is advisable to initially select k and the minimum size n so that k< (n+2)/2 - in this case the diameter of the k-plex is 2 (or less). If a k-plex is connected and k > (n+2)/2-1 then the diameter is always less than or equal to 2k-n+1, however it should not be assumed that the k-plex is connected and this would need to be examined.

REFERENCES Seidman S and Foster B (1978). A graph theoretic generalization of the clique concept. J or Math Soc, 6, 139-154.

Seidman S and Foster B (1978). A note on the potential for genuine cross-fertilization between anthropology and mathematics. Social Networks 1, 65-72.