Incremental Algorithms of the Core Maintenance Problem on Edge-Weighted Graphs
Incremental Algorithms of the Core Maintenance Problem on Edge-Weighted Graphs
复制标题
DOI：
10.1109/access.2020.2985327
复制
发表时间：
2020
期刊：
影响因子：
3.9
通讯作者：
B. Liu;Feiteng Zhang
中科院分区：
文献类型：
--
作者：
B. Liu;Feiteng Zhang
$k$ -核是图的一种结构，是最小度大于或等于$k$的最大连通子图，已在许多领域得到应用。$k$使得$k$ -core包含$u$的最大值是$u$的$K$值。特别地，对于边权图，顶点的度是它所有关联边的权之和。在无权图中研究了静态图的核分解问题和动态图的核维护问题。我们改进了核分解算法以适应边加权图，但直接使用它在大图变化后更新所有顶点的K值代价太大。然后，我们找到一个小的子图$H$，它包含所有的顶点，其$K$值将改变后的图。通过在H$上操作，成本将大大降低。其次，我们设计了边权图在插入和删除两种情况下的核维护算法，这是本文的主要工作。在这些核维护算法中，增加了一个分层的过程，帮助我们确定新的$K$值的顶点在$H$从小到高。最后，我们在真实世界的图上进行了大量的实验，以显示我们的算法的有效性和效率。实验结果表明，我们的算法具有最好的性能.
The $k$ -core, a kind of structure of graphs, is a maximal connected subgraph with the minimum degree greater than or equal to $k$ , and has been used in many fields. The maximum $k$ such that a $k$ -core contains $u$ is the $K$ value of $u$ . Especially, for an edge-weighted graph, the degree of a vertex is the sum of weights of all its incident edges. The core decomposition problem on static graphs and the core maintenance problem on dynamic graphs have been studied in unweighted graphs. We improve the core decomposition algorithm to suit edge-weighted graphs, but it costs too much to update $K$ values of all vertices after the change of large graphs by using it directly. Then we find a small subgraph $H$ which contains all vertices whose $K$ values will change after the change of graphs. By operating on $H$ , the cost will be greatly reduced. Next, we design core maintenance algorithms for edge-weighted graphs in both insertion and deletion cases, which is the major work in this paper. In those core maintenance algorithms, a hierarchical process is added, which help us determine the new $K$ values of vertices in $H$ from the small ones to high. Finally, we conduct extensive experiments on real-world graphs to show the effectiveness and the efficiency that our algorithms have. The results show that our algorithms have the best performance.