Introduction

The incremental k-core algorithm is a crucial data structure in graph theory, particularly useful for analyzing evolving networks. The k-core of a graph is a maximal subgraph in which each node has at least k neighbors. This concept can be pivotal in understanding the cohesiveness of social networks, biology networks, or any structure that can be represented as a graph.

Understanding k-core

A k-core of a graph $G$ is a maximally connected subgraph where each vertex has at least degree $k$. Formally, given a graph $G = (V, E)$, its k-core is the largest subgraph $G_k = (V_k, E_k)$ such that every vertex in $V_k$ has a degree of at least $k$.

Algorithm Overview

The k-core decomposition of a graph can be computed efficiently using a peeling algorithm:

1. Initialize: Start with the original graph $G$.
2. Peeling Process:
   • Remove all vertices with degrees less than $k$.
   • Repeat the process until no such vertices remain.
3. The remaining subgraph is the k-core for the given $k$.

Incremental k-core Algorithm

An incremental k-core algorithm is tasked with updating the current k-core structure dynamically as the graph changes—typically through the addition or removal of edges.

Key Operations

1. Edge Insertion: When a new edge $(u, v)$ is added to the graph:
   • Check if either $u$ or $v$ can now be included in a higher k-core.
   • If they can, add them and reevaluate the k-core structure iteratively for affected nodes.
2. Edge Deletion: When an edge is removed:
   • Check if this affects the k-core connectivity for nodes on the deleted edge.
   • Re-calculate the k-core removing nodes whose degrees no longer satisfy the k-core requirement.

Incremental Algorithm Steps

The steps for updating a graph's k-core incrementally can be detailed as follows:

1. Adjust Degree: Incrementally adjust the degree of vertices for any added or deleted edges.
2. Update Core Vertices: Re-evaluate the core condition for affected vertices only.
3. Dynamic Core Adjustment:
   • For an added edge: Check downstream neighbors for core inclusion.
   • For a removed edge: Initiate a cascade removal for vertices falling below the required degree.

Examples

Let's consider a simple graph $G$:

2 - 3