k-core is a cohesive subgraph such that every vertex has at least k neighbors within the subgraph, which provides a good measure to evaluate the importance of vertices as well as their connections. Unfortunately, k-core cannot adequately reveal the structure of a temporal graph, in which two vertices may connect multiple edges containing time information. As a result, (k, h)-core is derived from k-core, which is also called temporal core, to provide a well-formulated definition, where h represents the number of temporal edges between two vertices. However, it is costly to repeatedly decompose a temporal graph changing over time. To address this challenge, we study the method of (k, h)-core maintenance, which can find current (k, h) cores with less computational efforts. To estimate the influence scope of inserted (removed) edges, we propose quasi-temporal core, denoted by quasi-(k, h)-core, which relaxes the constraint of (k, h)-core but still has similar properties to (k, h)-core. With the aid of quasi (k, h)-core, our insertion algorithm finds the minimum incremental graph for each influenced (k, h)-core, and the removal algorithm adjusts each influenced (k, h)-core in the minimal range. Experimental results verify effectiveness and scalability of our proposed algorithms. (C) 2019 Elsevier Inc. All rights reserved.
展开▼
