Why $k$ -core decomposition?

LaNet-vi is a visualization tool for large scale networks based on the $k$ -core decomposition [1].

Formally, the $k$ -core of a graph $\mathcal{G}$ is the connected maximal induced subgraph which has minimum degree greater than or equal to $k$ [2]. Roughly speaking, it is the maximal subgraph $\mathcal{H}$ of $\mathcal{G}$ with the property that the minimum number of edges from any vertex in $\mathcal{H}$ towards other vertices of $\mathcal{H}$ is at least $k$ .

Starting from $k =1$ (for graphs without isolated vertices), a simple recursive algorithm allows to obtain all $k$ -cores of a graph.

• Every vertex of a connected graph belongs to the $1$ -core. In Fig.1, we have highlighted the different core using closed lines of different types. A dashed line encloses all the vertices in the $1$ -core (the entire graph).
• Then, all vertices of degree $d < 2$ are recursively cut out. In Fig.1 all these vertices are colored in blue. The other vertices maintain a degree $d \geq 2$ also after the pruning of the blue ones, therefore they are not eliminated. The remaining vertices form the $2$ -core, enclosed by a dotted line.
• Further pruning allows to identify the innermost set of vertices, the $3$ -core. One can check that all red vertices in Fig.1 have internal degree (i.e. between red vertices) at least $3$ . This core is highlighted by a dash-dotted line.

The use of different colors for the vertices is useful to stress another important property: the shell index of a vertex. A vertex has shell index $k$ if it belongs to the $k$ -core but not to the $k+1$ -core. A $k$ -shell collects all vertices with the same shell index, i.e. those vertices that are pruned at the same stage of the procedure. Blue vertices in Fig.1 belong to the $1$ -shell, green ones to the $2$ -shell and the red vertices compose the $3$ -shell that, being the highest one, coincides with the $3$ -core.

In Graph Theory there are many other definitions that are usefully exploited in the analysis of social networks [3] as cliques, $n$ -cliques, $n$ -clans, $n$ -clubs, $k$ -plexes, $ls$ -sets, etc. Many of these notions can be, in principle, used to draw a reduced representation of a graph by means of pruning or renormalization algorithms. The $k$ -core analysis is particularly indicated for two main situations:

• the analysis of large sparse networks, since the visualization algorithm runs in a time $O(n+e)$ (where $n$ and $e$ are the total number of vertices and edges respectively);
• the analysis of networks with a non trivial hierarchical structure, since the vertices are displayed in different $2D$ annular shells in relation with their actual shell index, that provides a centrality measure and a manner to gain information on the hierarchical order in the network.