Maintaining Top-<inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula> Cores in Dynamic Graphs

Graphs have been widely used in many applications. One important graph analytics is to explore cohesive subgraphs in a large graph. Among several cohesive subgraphs studied, <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq3-3332638.gif"/></alternatives></inline-formula>-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 <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq4-3332638.gif"/></alternatives></inline-formula>-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 <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq5-3332638.gif"/></alternatives></inline-formula>-order, among vertices, while a graph is updated. Our new algorithm can significantly outperform the state-of-the-art algorithm up to 3 orders of magnitude for the 11 large real graphs tested. In addition, we also study the problem of partial core maintenance, which is to maintain the top-<inline-formula><tex-math notation="LaTeX">$t$</tex-math><alternatives><mml:math><mml:mi>t</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq6-3332638.gif"/></alternatives></inline-formula> cores of the graph for a given positive integer <inline-formula><tex-math notation="LaTeX">$t$</tex-math><alternatives><mml:math><mml:mi>t</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq7-3332638.gif"/></alternatives></inline-formula>. By instead maintaining only a small subset of cores, further improvement in performance can be obtained.