k-Core Decomposition

Given a graph $G = \left< V, E \right>$, and a subset $S \subset V$, the sub-graph $G(S)$ induced by $S$ is defined as

where $E_S = \{ e : e = (u, v) \in E \wedge (u, v) \in S \times S\}$.

$G(S)$ is called a $k$-core if it is the maximal sub-graph wuch that every vertex in $S$ has degree at least $k$ inside this sub-graph. Given the definition of $k$-core, the core number of a vertex $v \in V$ is the maximum $k$ such tha t $\exists S \subset V$, $G(S)$ is a $k$-core and $v \in S$.

The key observation is that, given a $k$-core $G(S)$, if we remove every vertex $v \in V$ (as long as edges incident to $v$) such that $d(v) < k$, then $G(S)$ remains a $k$-core. Since

1. If $d(v) < k$, then $v \notin S$.
2. Removing edges incident to $v$ will not affect edges inside $G(S)$. Then, the vertices' degree inside $G(S)$ remains unchanged.

This gives an algorithm for computing the core number of each vertex.

1. for $v \in V$:
2. $\quad$ $check[v] \leftarrow$ false
3. while not $check[v] =$ true $\forall v \in V$:
4. $\quad$ Get an $v$ with smallest $d(v)$ and $check[v] =$ false
5. $\quad$ $check[v] \leftarrow$ true
6. $\quad$ $core[v] \leftarrow d(v)$
7. $\quad$ for $u \in N(v)$ such that $d(u) > k$:
8. $\qquad$ Delete $(v, u)$
9. $\qquad$ $d(u) \leftarrow d(u) - 1$

We can use an array $D$ such that $D[i]$ is a linked list and contains all vertices with degree $i$. Therefore, line 4 can be executed in $O(1)$ time.

Reference

[1] Batagelj, V. and Zaversnik, M., 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049.