corenumbers

Corenumbers, in graph theory, refer to the core numbers or coreness of vertices. The coreness of a vertex is the largest integer k such that the vertex lies in the k-core of a graph. A k-core is a maximal subgraph in which every vertex has degree at least k. The collection of core numbers for all vertices constitutes a core decomposition of the graph, and the maximum coreness across vertices equals the graph’s degeneracy.

Core numbers can be computed efficiently. The standard approach processes vertices in order of nondecreasing degree and assigns a core number to each vertex as it is removed from the graph. A more widely used, linear-time method uses a bucket (or bin) queue to implement this core decomposition, achieving O(n + m) time for a graph with n vertices and m edges. This makes core decomposition scalable to large networks.

Interpreting coreness, a higher core number indicates that a vertex belongs to a more cohesive, densely interconnected region of the network. Core numbers provide a localized measure of robustness or centrality that is complementary to other centrality metrics. They are related to the graph’s degeneracy—the largest core number observed in the graph.

Applications of corenumbers include identifying cohesive subgraphs, backbone structures, or influential nodes in social and information networks, as well as guiding network pruning and visualization. They are used in exploratory data analysis, community detection heuristics, and resilience studies. Limitations include the fact that coreness captures only a local, degree-based notion of connectivity and may not fully reflect global centrality, community structure, or dynamic processes on the network.