Core (graph theory)

In graph theory, a core is a specific type of subgraph with notable properties. The most common definition refers to the k-core of a graph.

k-Core

The k-core of a graph G is the largest subgraph of G such that every vertex in the subgraph has degree at least k. In simpler terms, it's the largest subgraph where each vertex is connected to at least k other vertices within that subgraph. The k-core may be empty if no such subgraph exists. The k-core is necessarily an induced subgraph.

Finding the k-core of a graph involves iteratively removing vertices with degree less than k, along with their incident edges, until all remaining vertices have degree at least k. The resulting subgraph is the k-core. The process is deterministic, meaning that for a given graph and value of k, there is only one k-core.

Core Number

The core number (or degeneracy) of a vertex v in a graph is the highest value of k for which v belongs to the k-core. This value indicates the "tightness" of the vertex's connection within the graph.

Applications

k-cores and core decomposition have numerous applications in network analysis, including:

• Identifying dense subgraphs: k-cores are used to find cohesive subgroups within a network, revealing communities or groups with strong internal connections.
• Social network analysis: Identifying influential users or groups based on their core numbers.
• Bioinformatics: Analyzing protein-protein interaction networks to identify essential proteins.
• Data mining: Finding patterns and structures in large datasets represented as graphs.

Related Concepts

• Cliques: A clique is a complete subgraph where every vertex is connected to every other vertex. While a clique is a specific type of dense subgraph, k-cores provide a more general measure of density.
• Graph Degeneracy: The degeneracy of a graph is the largest value of k for which the graph contains a k-core. It provides a measure of the overall density of the graph.