Kjernetallet

Kjernetallet is a term used in graph theory to denote the core number of a vertex in a graph. It is the largest integer k such that the vertex lies in the k-core of the graph. The k-core is the maximal subgraph in which every vertex has degree at least k, and the core numbers across all vertices yield a hierarchical core decomposition of the network. This concept helps reveal the deeply interconnected part of a graph versus its periphery.

Computationally, the core decomposition can be obtained by iteratively removing vertices with degree less than k, or more efficiently by algorithms that assign a core number to each vertex in a single linear-time pass. The best-known approaches run in O(n + m) time, where n is the number of vertices and m is the number of edges. The largest core number in a graph is equal to its degeneracy, a measure of the graph’s maximum minimum degree across subgraphs.

Interpretation and use: A higher kjernetall indicates that a vertex belongs to a more central and densely connected region of the network. Core numbers are used in network analysis to identify influential nodes, study network resilience, and assist in community detection or data reduction for visualization and further processing. They are also useful in prioritizing vertices for sampling, diffusion studies, or search strategies in large graphs.

Variants and context: In directed graphs, core concepts can be adapted using in-degree or out-degree thresholds, yielding directed k-cores or related notions. The term kjernetallet is the Norwegian translation of core number and is commonly used in Norwegian-language sources; English literature typically uses “core number” and “k-core.”

See also: core number, k-core, k-shell, degeneracy, graph theory.