On Finding and Analyzing the Backbone of the k-Core Structure of a Graph

In many network applications, dense subgraphs have proven to be extremely useful. One particular type of dense subgraph known as the k-core has received a great deal of attention. k-cores have been used in a number of important applications, including identifying important nodes, speeding up community detection, network visualization, and others. However, little work has investigated the ‘skeletal’ structure of the k-core, and the effect of such structures on the properties of the overall k-core and network itself. In this paper, we propose the Skeletal Core Subgraph, which describes the backbone of the k-core structure of a graph. We show how to categorize graphs based on their skeletal cores, and demonstrate how to efficiently decompose a given graph into its Skeletal Core Subgraph. We show both theoretically and experimentally the relationship between the Skeletal Core Subgraph and properties of the graph, including its core resilience.

在许多网络应用中，密集子图已被证明极其有用。一种被称为k - 核的特殊密集子图受到了大量关注。k - 核已被用于许多重要应用中，包括识别重要节点、加速社区检测、网络可视化等。然而，很少有研究探讨k - 核的“骨架”结构，以及这种结构对整个k - 核和网络自身特性的影响。在本文中，我们提出了骨架核心子图，它描述了图的k - 核结构的主干。我们展示了如何根据骨架核心对图进行分类，并演示了如何有效地将给定图分解为其骨架核心子图。我们从理论和实验两方面展示了骨架核心子图与图的特性（包括其核心韧性）之间的关系。