# `Yog.Connectivity.KCore`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/connectivity/k_core.ex#L1)

Algorithms for k-core decomposition.

A [k-core](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) is a maximal subgraph
in which every node has at least degree `k`.

## K-Core Decomposition Visualization

A graph can be decomposed into nested "cores" where higher values of `k` represent denser, more central subgraphs.

<div class="graphviz">
graph G {
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];

  // 2-Core (Square + internal connections)
  subgraph cluster_c2 {
    label="2-Core (min_deg=2)"; color="#6366f1"; style=rounded;
    A -- B; B -- C; C -- D; D -- A;
  }

  // 1-Core additions (Peripheral nodes)
  A -- P1; C -- P2;
}
</div>

    iex> alias Yog.Connectivity.KCore
    iex> graph = Yog.from_edges(:undirected, [
    ...>   {"A", "B", 1}, {"B", "C", 1}, {"C", "D", 1}, {"D", "A", 1},
    ...>   {"A", "P1", 1}, {"C", "P2", 1}
    ...> ])
    iex> core_2 = KCore.detect(graph, 2)
    iex> Yog.node_ids(core_2) |> Enum.sort()
    ["A", "B", "C", "D"]

## Algorithms

| Problem | Function | Complexity |
|---------|----------|------------|
| Find k-core | `detect/2` | O(V + E) |
| Highest core number | `degeneracy/1` | O(V + E) |
| All core numbers | `core_numbers/1` | O(V + E) |

## Key Concepts

- **k-Core**: Maximal subgraph where min degree >= k.
- **Core Number**: For a node v, the largest k such that v is in a k-core.
- **Degeneracy**: The maximum core number found in the graph.
- **Pruning**: The process of iteratively removing nodes with degree < k.

## Applications

- **Community Detection**: Finding clusters of highly-connected nodes.
- **Graph Robustness**: Measuring the resilience of a network.
- **Search Space Reduction**: Pruning nodes that cannot participate in cliques of size k+1.
- **Visualization**: Filtering out peripheral nodes.

## Examples

    # Square graph has 2-core (all of it), but no 3-core
    iex> graph =
    ...>   Yog.undirected()
    ...>   |> Yog.add_node(1, nil)
    ...>   |> Yog.add_node(2, nil)
    ...>   |> Yog.add_node(3, nil)
    ...>   |> Yog.add_node(4, nil)
    ...>   |> Yog.add_edge_ensure(1, 2, 1)
    ...>   |> Yog.add_edge_ensure(2, 3, 1)
    ...>   |> Yog.add_edge_ensure(3, 4, 1)
    ...>   |> Yog.add_edge_ensure(4, 1, 1)
    iex> core_2 = Yog.Connectivity.KCore.detect(graph, 2)
    iex> Yog.node_count(core_2)
    4
    iex> core_3 = Yog.Connectivity.KCore.detect(graph, 3)
    iex> Yog.node_count(core_3)
    0

# `core_numbers`

```elixir
@spec core_numbers(Yog.graph()) :: %{required(Yog.node_id()) =&gt; integer()}
```

Calculates all core numbers for all nodes in the graph.
Core number of node v is the largest k such that v is in a k-core.

## Examples

    iex> graph = Yog.undirected() |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_edge_ensure(1, 2, 1)
    iex> Yog.Connectivity.KCore.core_numbers(graph)
    %{1 => 1, 2 => 1}

# `degeneracy`

```elixir
@spec degeneracy(Yog.graph()) :: integer()
```

Finds the degeneracy of the graph, which is the maximum core number.

# `detect`

```elixir
@spec detect(Yog.graph(), integer()) :: Yog.graph()
```

Detects the k-core of a graph.
Returns the maximal subgraph where every node has at least degree `k`.

## Examples

    iex> graph = Yog.undirected() |> Yog.add_node(1, nil) |> Yog.add_node(2, nil)
    iex> core = Yog.Connectivity.KCore.detect(graph, 1)
    iex> Yog.node_count(core)
    0

## Time Complexity

O(V + E)

# `shell_decomposition`

```elixir
@spec shell_decomposition(Yog.graph()) :: %{required(integer()) =&gt; [Yog.node_id()]}
```

Groups nodes into their respective k-shells.
A k-shell contains nodes that have a core number of exactly k.

---

*Consult [api-reference.md](api-reference.md) for complete listing*