K-Core Cluster
given an integer k > 0, the k-core of a graph is the largest subgraph, such that each node in the subgraph has at least k neighbors within the subgraph
note: this subgraph maybe disconnected
Example K-Cores
the k-cores of a graph, for various values of k, form a nested hierarchical system
Algorithm to Find the K-Core Subgraph
- delete all nodes of degree < k
- if the remaining graph is empty, then output the message “the k-core is empty” and halt
- if the remaining graph is non-empty, then
- if every node in the remaining graph has degree ≥ k, then this is the k-core; output this graph and halt
- else repeat from step 1