Core decomposition and maintenance in weighted graph

Coreness is an important index to reflect the cohesiveness of a graph. The problems of core computation in static graphs and core update in dynamic graphs, known as the core decomposition and core maintenance problems respectively, have been extensively studied in previous work. However, most of these work focus on unweighted graphs. Considering that graphs are weighted in a lot of realistic applications, it is indispensable to extend the coreness to weighted graphs and devise efficient algorithms for weighted core decomposition and weighted core maintenance. In this work, we present a new definition of weighted coreness for vertices in a weighted graph, by taking into account the weights of vertices, which makes the coreness in unweighted graph be a special case. We propose efficient algorithms for both weighted core decomposition and weighted core maintenance problems. The coreness of vertices can be computed in linear time by the proposed decomposition algorithm, while the proposed core maintenance algorithm can process multiple-edge insertions/deletions simultaneously, which greatly reduces the core update time. Comprehensive experiments on both realistic networks and temporal graphs exhibit our algorithms are efficient and scalable.