A Fast Order-Based Approach for Core Maintenance
Refereed conference paper presented and published in conference proceedings

Times Cited
Web of Science23WOS source URL (as at 27/01/2021) Click here for the latest count
Altmetrics Information

Other information
AbstractGraphs have been widely used in many applications such as social networks, collaboration networks, and biological networks. One important graph analytics is to explore cohesive subgraphs in a large graph. Among several cohesive subgraphs studied, k-core is one that can be computed in linear time for a static graph. Since graphs are evolving in real applications, in this paper, we study core maintenance which is to reduce the computational cost to compute k-cores for a graph when graphs are updated from time to time dynamically. We identify drawbacks of the existing efficient algorithm, which needs a large search space to find the vertices that need to be updated, and has high overhead to maintain the index built, when a graph is updated. We propose a new order-based approach to maintain an order, called k-order, among vertices, while a graph is updated. Our new algorithm can significantly outperform the state-of-theart algorithm up to 3 orders of magnitude for the 11 large real graphs tested. We report our findings in this paper.
All Author(s) ListYikai Zhang, Jeffrey Xu Yu, Ying Zhang, Lu Qin
Name of Conference2017 IEEE 33rd International Conference on Data Engineering (ICDE)
Start Date of Conference19/04/2017
End Date of Conference22/04/2017
Place of ConferenceSan Diego
Country/Region of ConferenceUnited States of America
Proceedings TitleData Engineering (ICDE), 2017 IEEE 33rd International Conference on
LanguagesEnglish-United States

Last updated on 2021-28-01 at 00:55