Core decomposition and maintenance in weighted graph
Core decomposition and maintenance in weighted graph
复制标题
加权图中的核心分解与维护
DOI：
10.1007/s11280-020-00857-0
复制
发表时间：
2021-01
影响因子：
3.7
通讯作者：
Fu Xiaoming
中科院分区：
文献类型：
--
作者：
Zhou Wei;Huang Hong;Hua Qiang-Sheng;Yu Dongxiao;Jin Hai;Fu Xiaoming
紧密度是反映图形内聚性的重要指标。静态图中的核心计算问题和动态图中的核心更新问题，分别被称为核心分解问题和核心维护问题，在以往的工作中得到了广泛的研究。然而，这些工作大多集中在未加权的图上。考虑到图在很多实际应用中都是加权的，将核扩展到加权图，并设计出有效的加权核分解和维护算法是必不可少的。本文通过考虑顶点的权重，提出了加权图中顶点的加权核心度的新定义，使未加权图中的核心度成为一种特例。我们针对加权核分解和加权核维护问题提出了有效的算法。所提出的分解算法可以在线性时间内计算出顶点的核心度，而所提出的核心维护算法可以同时处理多个边缘的插入/删除，大大减少了核心更新时间。在现实网络和时间图上的综合实验表明，我们的算法是有效的和可扩展的。
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.
登录
查看更多内容
DOI：
10.1109/icdmw.2014.31
发表时间：
2014-12
期刊：
2014 IEEE International Conference on Data Mining Workshop
影响因子：
--
作者：
Chung-Yuan Huang;Yu-Hsiang Fu;Chuen-Tsai Sun
通讯作者：
Chung-Yuan Huang;Yu-Hsiang Fu;Chuen-Tsai Sun
影响因子：
5.6
作者：
Samudrala, R;Moult, J
通讯作者：
Moult, J
影响因子：
3.9
作者：
B. Liu;Feiteng Zhang
通讯作者：
B. Liu;Feiteng Zhang
DOI：
--
发表时间：
2014-06
期刊：
--
影响因子：
--
作者：
J. Leskovec;A. Krevl
通讯作者：
J. Leskovec;A. Krevl
影响因子：
2.4
作者：
Eidsaa, Marius;Almaas, Eivind
通讯作者：
Almaas, Eivind