.png){kind=icon}
.png){kind=icon}
Return
Efficient order-based algorithms for core maintenance in weighted graph
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ins.2025.122775.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Graphs are widely used to model a wide range of real-world applications. The k-core structure plays a key role in analysis and research of graphs. For dynamic graphs, k-core maintenance has been investigated to accelerate core decomposition-a problem that has been extensively studied in the context of unweighted graphs. Edge weights are of great significance in reality. In this paper, we address the core maintenance problem in edge-weighted graphs. Building upon an advanced order-based core maintenance algorithm, we propose efficient algorithms for edge-weighted graphs and extend single-edge maintenance to update for multiple edges. For single-edge insertion, we incorporate a priority queue within each segment to minimize unnecessary vertex traversals. For single-edge deletion, we propose the ECS (Edge Classification Structure) to classify neighbors and shrink the search space. For maintenance of multiple edges, we adopt a centralized processing strategy to handle multiple updates simultaneously, together with a dynamic segment expansion mechanism that gradually enlarges the segment range until the end. Extensive experiments are performed on real-world networks to evaluate the effectiveness and scalability of the proposed algorithms. Experimental results show that our new single-edge insertion algorithm significantly outperforms the traversal-based incremental method by up to three orders of magnitude on 12 real-world graphs.
Keywords:
K-core
Edge-weighted graph
Core maintenance
Core decomposition