Contents - Index

NETWORK > REGIONS > K-CORES

PURPOSE List all k-cores of a graph.

DESCRIPTION A k-core in an undirected graph is a connected maximal induced subgraph which has minimum degree greater than or equal to k. For a valued graph we require the sum of all the edges incident with a vertex is greater than k.  This procedure finds all k-cores for every possible value of k and expresses these in a hierarchical clustering format. The coreness score is the maximum value of k for which it is in a k-core.

PARAMETERS
Input dataset:
Name of file containing data to be analyzed. Data type: Valued Graph.
  
Output dataset: (Default = 'Kcores')
Name of file which will contain a k-core by actor partition matrix. The partition by actor matrix is defined as follows:  a value of k in a column labeled i and row labeled j means that node j is in partition k for the i-core partition. From the remarks above it follows that if there is only one value k in the column labeled i then node j is not a member of any i-core.  Otherwise all other members of j's i-core will have a value of k in the same column. If the input dataset is multirelational it will produce and output dataset for each relation with the filename <matrixlabel>-Kcores.

Orientation:
The clustering diagram can be printed in the LOG FILE in portrait or landscape mode. If none is selected the clustering diagram is not produced.

Maximum label length:
Maximum number of characters in the labels. Labels that are longer than the prescribed value are truncated.

LOG FILE A hierarchical clustering diagram unless 'none' was selected giving the k-cores.  The columns are rearranged and labeled.  A '·' in row label i column label j means that vertex j was not in an i-core with any other vertex.  An 'X' indicates that vertex j was in an i-core with all vertices on the same row as j which can be found by tracing across that row without encountering a space.
 
Partition metrics. The first line labeled 'nclusters' gives the number of clusters at each level. The levels are given by row number and not the value of k. Hence the column labeled 1 gives the number of clusters in the bottom line of the cluster diagram (this will be the smallest number for k in the k-cores) and the last column gives the number of clusters in the top level corresponding to the highest value for k in a k-core. Then for each cluster specified in the row column j gives the proportion of actors in that cluster at level j (again the level corresponds to the level number and not the k-core value).

Finally the coreness value for each node (in each relation is given)

TIMING O(N^3)

COMMENTS K-Cores are not necessarily cohesive subsets but they do identify areas of the graph which contain clique like structures.

REFERENCES Seidman S (1983).  'Network structure and minimum degree'.  Social Networks, 5, 269-287.