Yog.Connectivity.KCore (YogEx v0.97.0)

Algorithms for k-core decomposition.

A k-core 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.

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; }

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

Summary

Functions

core_numbers(graph)

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.

degeneracy(graph)

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

detect(graph, k)

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

shell_decomposition(graph)

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

Functions

core_numbers(graph)

@spec core_numbers(Yog.graph()) :: %{required(Yog.node_id()) => 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(graph)

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

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

detect(graph, k)

@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(graph)

@spec shell_decomposition(Yog.graph()) :: %{required(integer()) => [Yog.node_id()]}

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