Querying Cohesive Subgraph regarding Span-Constrained Triangles on Temporal Graphs with Dynamic Index Maintenance Chuhan Hu∗ , Ming Zhong† , and Lei Li‡ ∗ DSA Thrust, The Hong Kong University of Science and Technology (Guangzhou) † School of Computer Science, Wuhan University, Wuhan, China ‡ The Hong Kong University of Science and Technology
arXiv:2606.11582v1 [cs.DB] 10 Jun 2026
[email protected], [email protected], [email protected]
Abstract—Recent advances in temporal graph research have redefined traditional static graph concepts such as triangles, motifs, and k-cores. Inspired by this, we introduce a novel (k, δ)truss for temporal graphs, requiring triangles to exist within sufficiently short time windows. The (k, δ)-truss ensures both static and temporal cohesion, while the original k-truss is a special case when δ = ∞. To address (k, δ)-truss queries, we propose index-free and index-based approaches. Utilizing the dual containment relation of (k, δ)-trusses, our indexes losslessly compress all (k, δ)-trusses into map or tree structures, significantly reducing space while enabling optimal-time retrieval. To scale to large temporal graphs, we develop two index construction algorithms based on truss decomposition and truss maintenance, respectively, which substantially reduce redundant computations. Moreover, we present techniques for the dynamic maintenance of the proposed indexes. The experimental results demonstrate that index-based approaches process queries in interactive time and outperform the index-free approach by 2∼4 orders of magnitude, while the indexes achieve compression ratios of up to 10−4 and can be updated efficiently without rebuilding from scratch. Index Terms—temporal graph, cohesive subgraph, truss, triangle, time span, index, query processing, maintenance
I. I NTRODUCTION Recently, temporal graphs in which each edge is associated with a set of timestamps have drawn intensive research interests, as introduced by [1] [2]. The typical examples of temporal graph are such as social networks [3], transaction networks [4], transportation networks [5], communication networks [6], power networks [7], disease transmission networks [8], etc. In those graphs, the temporality enables a variety of time-relevant constraints in analytics, such as time order, time window, time span, etc. For temporal graphs, the traditional definitions of cohesive subgraphs such as k-clique, k-truss, and k-core also need to be extended with time-relevant constraints, so that both temporal and topological features can be exploited for comprehensive analysis. For example, there have been a bunch of temporal k-core studies, which mainly fall into two categories. The first is to find primitive k-cores that exist in specific time windows, such as span-core [9], temporal k-core [10] [11], historical k-core [12] [13], temporal (k, X )-core [14], etc. The second is to study various new temporal k-cores models,
(4, 6)-truss (4, 4)-truss (4, 2)-truss (4, 0)-truss
8
6, 7
6
Fig. 1: A running example temporal graph and several (k, δ)trusses, which forms a “δ-shell” with a fixed k. such as frequent core [15], [16], persistent core [17], bursting core [18], periodic core [19], continual core [20], reliable core [21], etc. However, the models and approaches designed for k-core query are not sufficient for k-truss query on temporal graphs. In contrast to migrating them to k-truss directly, like [22] for the first category and [23] for the second category, it is more important to investigate the models and approaches dedicated to temporal k-truss query. As we know, k-truss in which each edge is contained by at least k − 2 triangles is defined on top of another more fundamental concept, namely, triangle. Thus, a reasonable definition of temporal k-truss should take the temporal constraint on triangles into consideration. Actually, many meaningful temporal triangle or motif (note that, triangles can be seen as a kind of motifs sometimes) models [24]–[29] have been proposed recently. These models mainly consider two kinds of temporal constraints. The first is the total or partial time order among edges, which is usually defined on directed temporal graphs, so that a triangle or motif can be seen as a sequence of edges in order of timestamps. Such constraints are too specific and complicated for a basic component of k-truss, and would result in over-tailoring of ktruss. The second is the duration, which is generally measured by the maximum time lag between timestamps of edges. In this paper, we propose a novel definition of (k, δ)-truss
(k, δ)-truss vertex# edge# triangle# coefficient duration (a) (16, ∞)
(b) (16, 200)
(c) (16, 150)
(a) 213 4402 42683 0.72 803
(b) 130 2355 21738 0.77 803
(c) 108 1735 14978 0.81 803
(d) 38 564 4670 0.85 802
(d) (16, 100)
Fig. 2: A case study on (k, δ)-trusses of Email dataset, which demonstrates the effectiveness of δ on improving cohesion. In each truss, we remark the vertices and edges of successive truss with different colors, so that the changes can be observed. for undirected temporal graphs, on top of a kind of “span”constrained δ-triangles. The rationale is two-fold. Since k-truss considers a triangle as a strong evidence of its vertices are bonded tightly in a community, it is better to consistently guarantee the tightness of triangle but not truss from the perspective of time. Moreover, different from the related works, (k, δ)-truss requires the minimum time span but not normal duration of triangles to be no greater than δ, which regulates temporal cohesion beyond static cohesion k. Because a triangle that ever occurs in a short enough period should be more cohesive in the sense of time than another triangle that has the same duration but no interactions close in time between each pair of its vertices, as illustrated in Fig 3. Let us consider the following empirical (k, δ)-truss queries. E XAMPLE 1 (Case Study). To demonstrate the effectiveness of (k, δ)-truss query, we conduct a case study on Email [30], a communication network between members of a European research institution. Fig 2 illustrates four trusses with k = 16 and δ = ∞, 200, 150, and 100 respectively. The (k, δ)-truss query can help us to further tailor the static k-truss (a) in time dimension. We can see that, the stricter temporal cohesion indeed makes the truss structure more compact. The k-truss (a) is composed of several smaller communities. With the decrease of δ, the successive (k, δ)-trusses (b), (c), and (d) become more and more clustered. As an evidence, the clustering coefficient increases from 0.72 to 0.85 gradually. In contrast, the duration of whole trusses does almost not change, which means we will not find the more compact trusses like (b), (c), and (d) by using the duration of truss as temporal constraint. In order to address the (k, δ)-truss query, we propose both index-free and index-based approaches. Unlike the index-free approach that performs a straightforward truss decomposition under the constraint of δ, the index-based approach only needs to scan each edge in the result once, thereby being theoretically time-optimal. Since there could be a great number of (k, δ)-trusses in a temporal graph, we use Temporal Containment Index (TC-Index) or Dual Containment Index (DC-Index) to preserve trusses incrementally. Moreover, for large-scale temporal graphs, we develop two scalable index construction algorithms based on two classical paradigms, truss decomposition [31]–[35] and truss maintenance [36]– [40], respectively. Decomposition Based Algorithm (DBA) can compute the incremental edge sets between (k, δ)-truss and
(k, δ+1)-truss, and Maintenance Based Algorithm (MBA) can further compute the incremental edge sets between (k, δ)-truss and (k+1, δ)-truss. Lastly, we propose a local search approach to maintain the indexes when new edges or timestamps are inserted into temporal graphs. In summary, our contributions are as follows. Inspired by the latest studies on temporal triangle and motif, we formalize a novel (k, δ)-truss query problem on temporal graphs, with respect to a meaningful temporal triangle metric called minimum time span. The (k, δ)truss considers both static and temporal cohesion, while the static k-truss is its special case for δ = ∞. • We leverage the dual containment relation on (k, δ)trusses to design compact indexes that store and retrieve all possible (k, δ)-trusses efficiently. Firstly, we present a map-structured index called TC-Index that preserves the incremental edges in δ dimension. Then, we present a tree-structured index called DC-Index that preserves the globally minimum incremental edges in both k and δ dimensions. Both indexes provide the optimal query efficiency, and DC-Index is space-optimal when query efficiency cannot be degraded. • To enable the proposed indexes to scale to large temporal graphs, we follow the line of truss decomposition and truss maintenance respectively to improve the scalability of index construction. DBA decomposes k-truss gradually by removing triangles in descending order of minimum time span for each k. MBA maintains all edge trussness simultaneously when invalidating triangles in descending order of minimum time span. • We present an efficient filter-and-verification algorithm for dynamic index maintenance, thereby avoiding to rebuild index from scratch. For an edge update, it gradually narrows the ranges of trussness and temporal threshold, and then identifies a small local subgraph comprised of the edges that may need to be updated in indexes. • We conduct comprehensive experimental evaluation on eight real-world temporal graphs, on which we observed that triangle counts distribute widely on minimum time span. Our index-based TC-Query and DC-Query process queries in interactive time, and outperform the index-free Online-Query by 2∼4 orders of magnitude. Meanwhile, our indexes can achieve the compression ratio of up to 10−4 , and can be updated significantly faster than •
0
minimum time span
n
0
uv
uv
uw
uw
vw
vw
duration
minimum time span
n
duration
Fig. 3: Abstract comparison of different minimum time spans of a triangle ∆ = {u, v, w}. For each edge like (u, v) of ∆, its timestamps are marked by a kind of symbols like rectangles in a timeline from 0 until n. The combination of dark symbols of each kind determines the minimum time span of ∆. rebuilding from scratch. We present the preliminaries, index-free approach, indexbased approaches, index construction, index maintenance, experimental evaluation, related work, and conclusion in the rest sections respectively. II. P RELIMINARIES Let G = (V, E) be an undirected static graph, where V is a set of vertices and E ⊆ V × V is a set of edges. For each edge e = (u, v) ∈ E, the pair of vertices u and v may have multiple interactions at different times. We denote the set of timestamps of interaction between u and v by τ(u,v) . Thus, the temporal edge between u and v can be represented by (u, v, τ(u,v) ), and the temporal graph can be represented by G t = (V, E, Γ), where Γ = {τ(u,v) |(u, v) ∈ E} is the set of nonempty timestamp sets for each edge in E. Fig 1 illustrates a temporal graph as our running example. Without loss of generality, we use consecutive natural numbers from 0 until n to denote timestamps in a temporal graph. Then, let us consider the reasonable definition of k-truss for temporal graphs. Given a static graph G, the k-truss, denoted by Tk (G), is defined as the maximal subgraph of G in which each edge is contained by at least k − 2 triangles, where k ≥ 2 is a user-specified integer that represents topological cohesion of the subgraph. Obviously, the definition of k-truss is closely associated with that of triangle, a more fundamental concept for graph. Inspired by [24]–[29], we propose a novel and meaningful definition of temporal triangle in the context of truss study as follows. Definition 1 (Minimum Time Span). Given a temporal graph G t , for a triangle ∆ = {u, v, w} of G with u, v, w ∈ V and (u, v), (v, w), (w, u) ∈ E, its minimum time span mts(∆, G t ), represents the shortest duration of time window in which each two vertices have interaction, namely, mts(∆, G t ) = min{max{|t1 − t2 |, |t2 − t3 |, |t3 − t1 |} : t1 ∈ τ(u,v) , t2 ∈ τ(v,w) , t3 ∈ τ(w,u) }. When the context is clear, we replace mts(∆, G t ) by mts(∆).
3 0
1
2
Fig. 4: An illustration of (k, δ)-truss graph of a temporal graph, where each arrow Tk,δ → Tk′ ,δ′ denotes that Tk′ ,δ′ ⊆ Tk,δ . interact with each other during at least one same short period. As illustrated in Fig 3, the left triangle is considered as a tighter bond than the right one from the perspective of time, though them have the same duration. Because, in the shorter minimum time span, all three vertices may participate in a same event. In contrast, the right triangle represents a typical counterexample. When two of the vertices have contacts, neither of them interacts with the other vertex. Like in a social network, I know both of you but do not know you know each other, which means the three of us are not that close. On top of δ-triangle, we give the definitions of δ-support of temporal edge and (k, δ)-truss of temporal graph as follows. Definition 3 (δ-support). Given a temporal graph G t and an integer δ ≥ 0, the δ-support of an edge e = (u, v) ∈ E, denoted by δ-sup(e), is the number of δ-triangles that contain e, namely, |{∆ : u, v ∈ ∆, mts(∆) ≤ δ}|. E XAMPLE 2. Consider an edge e = (v2 , v8 ) in Fig 1. The triangles containing e are ∆1 = {v2 , v3 , v8 } and ∆2 = {v2 , v7 , v8 }. We have mts(∆1 ) = 2 and mts(∆2 ) = 6, so that δ-sup(e) is 2 if δ ≥ 6, 1 if 2 ≤ δ < 6, or 0 otherwise. Definition 4 ((k, δ)-truss). Given a temporal graph G t , an integer k ≥ 2, and an integer δ ≥ 0, the (k, δ)-truss of G t , denoted by Tk,δ , is defined as the maximal subgraph of G t in which the δ-support of each edge e is no less than k − 2, namely, δ-sup(e) ≥ k − 2 in the temporal subgraph Tk,δ .
Definition 2 (δ-triangle). Given a threshold δ of minimum time span, a triangle ∆ is called a δ-triangle if mts(∆) ≤ δ.
E XAMPLE 3. In Fig 1, given k = 4, we use colored dashed lines to remark the (k, δ)-trusses with different δ. The edges surrounded by black dashed line comprise the largest (4, 6)truss. When δ is decreased to 4, the edges such as (v2 , v8 ) are excluded due to inadequate δ-support, and the edges surrounded by red dashed line comprise the smaller (4, 4)truss. Similarly, with the decrease of δ, the (k, δ)-truss shrinks gradually, like the (4, 2)-truss surrounded by green dashed line and (4, 0)-truss surrounded by blue dashed line.
Intuitively, δ-triangles represent tight bonds in the sense of both topology and time, which require the involved vertices to
More importantly, similar to the static cohesive subgraphs like k-truss and k-core, (k, δ)-truss also has the containment
property, which is however dual with respect to both k and δ. As illustrated in Fig 4, each (k, δ)-truss is contained by both (k − 1, δ)-truss and (k, δ + 1)-truss directly. Such containment properties are the keys to developing efficient algorithms for retrieving cohesive subgraphs, such as truss decomposition [31] and core decomposition [41]. The dual containment property is formally defined as follows. Property 4.1 (Dual Containment). For any two (k, δ)-trusses Tk,δ and Tk′ ,δ′ of a temporal graph G t , Tk,δ is a subgraph of Tk′ ,δ′ , denoted by Tk,δ ⊆ Tk′ ,δ′ , if k ′ ≤ k and δ ′ ≥ δ. In this paper, we aim to address the following problem. P ROBLEM. Given a temporal graph G t , an integer k ≥ 2, and an integer δ ≥ 0, find the (k, δ)-truss Tk,δ of G t . III. I NDEX -F REE A PPROACH In this section, we first propose a straightforward online solution derived from the classic truss decomposition [31] as a baseline. The pseudo code of online solution can be found in the conference version [46]. It first computes the δ-support of each edge in E, and pushes all edges into a priority queue Q in ascending order of δ-support. Then, it performs an edge peeling process that iteratively removes the edge with the minimum δ-support from queue until the δ-supports of all rest edges are no less than k−2. Upon the removal of an edge e, for the other edges in each same triangle ∆ with e, we will keep their δ-support unchanged if mts(∆) is greater than δ because they are never counted in the first place, or decrease their δsupport otherwise. After the peeling process, the remaining edges in the queue comprise the target (k, δ)-truss. Correctness. The correctness is obvious as long as the correctness of truss decomposition holds. Complexity. The original truss decomposition algorithm takes P O( (u,v)∈E min{deg(u), deg(v)}) time, where deg(u) is the degree of u in G. Compared with that, the main extra time cost of our algorithm is to compute mts(∆) for each triangle in G t . Let |τ | denote the average number of timestamps associated with an edge (u, v) and |∆| denote the total number of triangles. The time cost of computing mts(∆) for a single triangle is O(|τ |) if τ(u,v) is ordered. Thus, the time complexity of our P algorithm is O( (u,v)∈E min{deg(u), deg(v)} + |τ | · |∆|). IV. I NDEX -BASED A PPROACH The complexity of the above index-free algorithm is at least sub-quadratic to the number of edges for a temporal graph, and thus is infeasible for real-time processing when the graph is large. Therefore, we propose index-based approaches to efficiently answer (k, δ)-truss queries in this section. A. TC-Index 1) Index Structure: A basic idea of indexing is to preserve all possible (k, δ)-trusses for a temporal graph, which can answer any query in the optimal time due to precomputation. However, directly preserving all possible (k, δ)-trusses takes O(kmax · δmax · |E|) space in the worst case, where kmax and δmax are the maximum values of k and δ respectively
for a given temporal graph. It means the index could be thousands of times or even larger than the graph itself in practice. Consequently, we propose a Temporal Containment Index (TC-Index) that adopts an incremental storage scheme to reduce the index size. With only a little compromise of query efficiency compared with the uncompressed index, the size of TC-Index is reduced to O(kmax · (|E| + δmax )). Before introducing TC-Index, let us consider the following pilot concept firstly. Definition 5 (k-Span). Given a temporal graph G t and a support threshold k, the k-span of an edge e ∈ E is an integer δ = k- spn(e, G t ), such that (i) the (k, δ)-truss contains e and (ii) the (k, δ ′ )-truss does not contain e for any δ ′ < δ. When the content is clear, we replace k- spn(e, G t ) by k- spn(e). Property 5.1. The k-span of edges in the (k, δ)-truss is no greater than δ. With Property 4.1 and 5.1 , we only need to consider edges in the k-truss of G whose k-span is no greater than δ in order to find the (k, δ)-truss of G t , because the (k, δ)-truss of G t is certainly a subgraph of the k-truss of G. Based on the above observation, for a temporal graph G t , TC-Index maintains a map structure Ik = (Ek , Dk ) for each possible k value. Ek is a sequence that preserves edges of the k-truss in descending order of k-span, and Dk is an index that records the unique k-spans and the offsets of the first edges with the corresponding k-span in Ek . Then, TC-Index I = (I3 , I4 , · · · , Ikmax ) is comprised of the map structures for all possible k. Note that TC-Index does not store the map structures for k ≤ 2 because the (2, δ)-truss is actually the entire temporal graph, regardless of δ. E XAMPLE 4. The TC-Index for the temporal graph in Fig 1 is given in Fig 5. Three are three map structures I3 , I4 , and I5 . Within I4 , there are four unique k-spans 6, 4, 2, and 0 in D4 , which have pointers to the first edges with these k-spans in E4 . We can see the edges (v2 , v3 ), (v2 , v7 ), (v2 , v8 ), (v3 , v7 ), and (v3 , v8 ) have the k-span 6 when k = 4. T HEOREM 1. For a temporal graph G t , the size of TC-Index is bounded by O(kmax · (|E| + δmax )). 2) Query Processing: The TC-Index based query algorithm is named TC-Query, whose pseudo code can be found in the conference version [46]. For the given k and δ, TC-Query first retrieves Ik = (Ek , Dk ) from TC-Index. Then, it finds the maximum δ ′ in Dk with δ ′ ≤ δ, and locates the position in Ek with respect to the offset associated with δ ′ in Dk . Lastly, it scans Ek from the position until the end, and all scanned edges comprise Tk,δ . E XAMPLE 5. Consider the (k, δ)-truss query with k = 4 and δ = 1. In D4 , the first k-span no greater than δ is 0. Thus, we locate the edge (v6 , v8 ) in E4 and start to scan the following edges. Lastly, we get the edges of (4, 1)-truss, namely, (v6 , v8 ), (v6 , v9 ), (v6 , v10 ), (v8 , v9 ), (v8 , v10 ), and (v9 , v10 ), which can be verified in Fig 1 (see the blue edges).
6 (0,1)
4 (0,3)
6 (2,3)
3 (2,7) (4,5)
4
2 (5,6)
2
(2,7)
(2,8)
(3,7) (3,8)
(6,8)
(6,9) (6,10) (7,8)
0
(5,7) (1,2)
(1,3) (2,3)
(2,8)
(3,7)
(3,8)
(4,7)
(5,7)
(6,7) (7,8)
(4,6) (4,7)
(6,7)
(7,8)
(7,9) (7,10) (6,8)
(6,9) (6,10) (8,9) (8,10) (9,10)
0 (4,5)
(4,6)
(5,6)
(7,9) (7,10) (6,8)
(6,9) (6,10) (8,9) (8,10) (9,10)
2 (6,7)
(7,9) (7,10) (8,9) (8,10) (9,10)
Fig. 5: An example of TC-Index, in which (vi , vj ) is represented by (i, j). T HEOREM 2. TC-Query computes the edge set of Tk,δ in at most O(log δmax + |Tk,δ |) time, where |Tk,δ | denotes the number of edges in Tk,δ . Compared with the optimal time of processing (k, δ)-truss query that is certainly O(|Tk,δ |), TC-Query is almost optimal since log δmax is usually much less than |Tk,δ |. B. DC-Index 1) Index Structure: Although TC-Index exploits temporal containment to achieve incremental storage, it is still not space-efficient enough as it only takes into account one aspect of Property 4.1. To fully exploit the property, we propose an advanced tree-structured index called Dual Containment Index (DC-Index). DC-Index is space-optimal while guaranteeing the same order of query efficiency as TC-Index. Specifically, DCIndex is derived in the following steps. Definition 6 ((k, δ)-Truss Graph). Given a temporal graph G t , we define a (k, δ)-truss graph as a directed weighted graph G = (V, E, w), where V = {Tk,δ : 3 ≤ k ≤ kmax , 0 ≤ δ ≤ δmax } is the set of all possible (k, δ)-trusses of G t , E = Ev ∪ Eh = {(Tk,δ , Tk+1,δ ) : 3 ≤ k ≤ kmax − 1, 0 ≤ δ ≤ δmax } ∪ {(Tk,δ , Tk,δ−1 ) : 3 ≤ k ≤ kmax , 1 ≤ δ ≤ δmax } is a subset of dual containment relation on V , and w : E 7→ N indicates the number of incremental edges between two connected trusses. Fig 6(a) illustrates the (k, δ)-truss graph of our example temporal graph. Intuitively, we call the edges in Ev as vertical edges and the edges in Eh as horizontal edges. For each edge in this graph, if the sink truss has been stored, the cost of incrementally preserving the source truss is the weight of edge. Definition 7 ((k, δ)-Truss Arborescence). Given a (k, δ)-truss graph G, we derive a (k, δ)-truss arborescence A from it by removing the outgoing edge (Tk,δ , Tk+1,δ ) or (Tk,δ , Tk,δ−1 ) with greater weight for each truss Tk,δ . Note that, if Tk,δ has one or none outgoing edge, no edge will be removed. Fig 6(b) illustrates the (k, δ)-truss arborescence, which is actually a minimum-weight directed spanning tree. For each truss, there is a single directed path that leads to the root, namely, (kmax , 0)-truss. Definition 8 (Reduced (k, δ)-Truss Arborescence). Given a (k, δ)-truss arborescence A, we reduce it to another arborescence A− by (i) removing each truss and its outgoing edge if
the edge weight is zero and (ii) reconnecting each truss to the next truss on its original path in A if its sink truss is removed. Fig 6(c) illustrates the reduced (k, δ)-truss arborescence. Obviously, each omitted truss can still be retrieved because there is certainly another truss identical to it remained. Then, we use an incremental storage scheme to preserve all possible (k, δ)-trusses according to the reduced (k, δ)-truss arborescence. As illustrated in Fig 6(d), the incremental edge set tree of DC-Index is logically equivalent to the reduced (k, δ)-truss arborescence, and preserves the Incremental Edge Sets (IESes) between trusses in each node of the tree. Compared with TC-Index, DC-Index surely has fewer redundant edges. For example, the total number of edges in Fig 6(d) is 40, and in contrast, the total number of edges in Fig 5 is 54. Actually, the space cost of DC-Index is the minimum under a precondition. T HEOREM 3. Given a temporal graph G t , the incremental edge set tree of DC-Index is space-optimal for preserving all possible (k, δ)-trusses of G t , when the efficiency of retrieving a specific (k, δ)-truss cannot be degraded. Moreover, to retrieve a specific (k, δ)-truss in the tree, DCIndex uses a lookup table to record the pointers to tree nodes. As shown in Fig 6(e), the cell in k row and δ column contains the pointer to the tree node that represents an identical truss of (k, δ)-truss. For example, to lookup T3,0 , the pointer to T4,0 in the tree is returned. We further compress the lookup table by skipping the consecutively repeating pointers for each row. As illustrated in Fig 6(f), when k = 5, there are only two unique pointers to T5,0 and T5,2 respectively, and we only record these two pointers with their smallest column ids (namely, 0 and 2) in the row. For 0 < δ < 2 or 2 < δ ≤ 6, it is easy to know the corresponding T5,δ is identical to T5,0 or T5,2 . 2) Query Processing: The DC-Index based query algorithm is named DC-Query, which is similar to TC-Query. For the given k and δ, it firstly finds the maximum δ ′ ≤ δ in row k and gets the pointer to a node of incremental edge set tree. Then, we traverse the path from this node to the root, and the union of all traversed edge sets is the edge set of Tk,δ . The pseudo code is omitted. T HEOREM 4. DC-Query is as efficient as TC-Query.
T5,0 T4,0 T3,0
T5,1 0 6
0
T4,1 0 T3,1 0
T5,2 10
T5,3 0
T5,4 0
T5,5 0
T5,6 0
T5,0
6
0 T4,2 4
0 T4,3 0
5 T4,4 5
5 T4,5 0
10 T4,6 5
T4,0
0
8 T3,2 12
10 7 T3,3 T3,4 2 2
7 T3,5 0
4 T3,6 2
T3,0
(a) An example of ( 6 *T3,6 *T4,6 *T5,2
5 *T3,4 *T4,4 *T5,2
4 *T3,4 *T4,4 *T5,2
T5,1 0 6
0
2 *T3,2 *T5,2 *T5,2
(e) The complete lookup table for all (
T3,1 0
0 T4,2
8 T3,2
(b) The (
)-truss graph 3 *T3,3 *T5,2 *T5,2
T4,1 0
T5,2 10
1 *T4,0 *T4,0 *T5,0
0 *T4,0 *T4,0 *T5,0
T5,3 0
T5,4 0
T5,5 0
T5,6 0
T5,0
T4,3 0
T4,4 5
T4,5 0
T4,6 5
T4,0
T3,3 2
T3,4 2
T3,5 0
T3,6 2
6 8 T3,2
T5,0
T4,0
3 4 5
(6,8) (6,9) (6,10) (8,9) (8,10) (9,10)
T3,2 3 4 5
T3,3 T3,4 T3,6
T4,4
T4,6 5
T3,3 2
T3,4 2
(c) The reduced (
)-truss arborescence
)-trusses
6, *T3,6 4, *T3,4 3, *T3,3 2, *T3,2 0, *T4,0 6, *T4,6 4, *T4,4 2, *T5,2 0, *T4,0 2, *T5,2
T5,2 10
T3,6 2
)-truss arborescence
T5,2
(6,7) (6,8) (6,9) (6,10) (7,8) (7,9) (7,10) (8,9) (8,10) (9,10)
(1,2) (1,3) (2,3) (2,8) (3,7) (3,8) (4,6) (4,7)
T4,4 (4,5) (4,6) (4,7) (5,6) (5,7)
(5,6) (5,7)
T4,6 (2,3) (2,7) (2,8) (3,7) (3,8)
(2,7) (4,5)
(0,1) (0,3)
(f) The compressed lookup table of DC-Index
(d) The incremental edge set tree of DC-Index
Fig. 6: An example of DC-Index, in which (vi , vj ) is represented by (i, j). V. I NDEX CONSTRUCTION In this section, we address the scalable construction of TC/DC-Index on large-scale temporal graphs. For that, we propose two algorithms based on two classic paradigms, namely, truss decomposition [31]–[35] and truss maintenance [36]– [40], respectively. A. TC-Index Construction based on Decomposition Intrinsically, the construction of TC-Index can be addressed by computing the Incremental Edge Sets (IESes) between each pair of (k, δ)-truss and (k, δ + 1)-truss for a temporal graph. Since these IESes correspond to the horizontal edges (Eh ) of the (k, δ)-truss graph illustrated in Fig 4, we call them Horizontal IES (H-IES), The index construction algorithm needs to reduce the redundant part in the computation of different H-IESes to scale to large temporal graphs. A basic strategy is to exploit the dual containment property to decrementally decompose (k, δ)-trusses in a particular order with respect to k and δ, like the existing temporal k-core decomposition [11]. However, temporal k-core decomposition does not involve the extra metric like the minimum time span of triangle, which may be needed repeatedly for evaluating δ-supports of edges. Thus, to eliminate the repeating computation of minimum time span, we design the following data structure to store mts(∆) for each ∆ in a temporal graph. Definition 9 (δ-triangle List). Given a temporal graph G t , a δ-triangle list is a list of triangle sets (S0∆ , S1∆ , · · · , Sδ∆max ), where Sδ∆ is the set of all triangles in G t whose minimum time spans are exactly δ with 0 ≤ δ ≤ δmax . Then, for each k, we decrementally induce each (k, δ)truss from (k, δ + 1)-truss, so that the H-IES between them can be obtained. The pseudo code of our Decomposition Based Algorithm (DBA) can be found in the conference version [46]. Initially, we enumerate all triangles and evaluate their minimum time span, for building the δ-triangle list. Let Xk∆ denote the set of triangles of k-truss. Obviously, the 2truss is G t itself, and thereby X2∆ is the union of all sets in
k-triangle list. Then, for each k with 3 ≤ k ≤ kmax , we decompose Tk,δmax = Tk gradually until Tk,0 is obtained, and collect the H-IESes. Specifically, each iteration starts with obtaining Tk of G by a traditional truss decomposition function decompv(), since the (k, δ)-truss is always a subgraph of k-truss. In particular, we can also obtain the set of deleted triangles X ∆ by decompv(). Thus, the triangle set of k-truss ∆ Xk∆ can be computed by removing X ∆ from Xk−1 . Then, for each δ from δmax − 1 until 0, the (k, δ)-truss is induced by a new decomposition function decomph(), which invalidates the triangles in Xk∆ from the (k, δ + 1)-truss. In this function, the H-IES can also be obtained. The details of functions are also included in the conference version [46]. E XAMPLE 6. Consider the temporal graph in Fig 1. Since the greatest minimum time span of its triangles δmax = 6, the 4-truss is actually the (4, 6)-truss surrounded by black dashed line. For k = 4, we can get the 4-truss from previous 3-truss by a traditional truss decomposition, and start to decompose (4, 6)-truss from δ = 5. The triangle ∆ = {v2 , v7 , v8 } ∈ X4∆ with mts(∆) = 6 will be invalidated because we are trying to obtain (4, 5)-truss currently. Thus, the δ-supports of its edges are decreased by 1. Then, we have both 5-sup(v2 , v7 ) and 5sup(v2 , v8 ) = 1 < 4 − 2, so (v2 , v7 ) and (v2 , v8 ) are pushed into Q and waiting to be deleted. On the removal of edge (v2 , v7 ), the triangle {v2 , v3 , v7 } containing it will be broken, so that the other two edges (v2 , v3 ) and (v3 , v7 ) also need to be checked like (v2 , v7 ). Iteratively, the edges not belong to (4, 5)-truss are all deleted and pushed into the H-IES between (4, 6)-truss and (4, 5)-truss, until Q is empty. Similarly, when δ decreases gradually, the edges remarked by red color and green color will be deleted respectively, until only the blue edges that comprise the (4, 0)-truss remain. Correctness. We only discuss the correctness of decomph() here, as the other parts of DBA are straightforward. Due to Property 4.1, we can induce the (k, δ)-truss from the (k, δ+1)truss. It is easy to know, we can finish that by invalidating all
triangles in Xk∆ whose minimum time span is greater than δ. To avoid redundant computation, we have a trick that is to only invalidate the triangle whose minimum time span is exactly δ + 1, because the other triangles have been invalidated during the previous calls of decomph(). The rest decomposition procedure is correct obviously. Complexity. P The time complexity of building the δ-triangle list is O( (u,v)∈E min{deg(u), deg(v)} + |τ | · |∆|), which is the same as the online Palgorithm. The total time cost of calling decompv() is O( (u,v)∈E min{deg(u), deg(v)}. For the inner loop with a specific k, the time complexity is O(|Xk∆ | + P (u,v)∈Tk min{deg(u), deg(v)}), since each triangle in Tk is invalidated at most once and each edge in Tk is visited at most Thus, thePtotal time cost of calling decomph() is Ponce. kmax (|Xk∆ | + (u,v)∈Tk min{deg(u), deg(v)})), which O( k=3 dominates the total time cost of DBA. B. TC/DC-Index Construction based on Maintenance DBA can only produce H-IES but not IES between each pair of (k, δ)-truss and (k + 1, δ)-truss, which are called Vertical IES (V-IES) for corresponding to the vertical edges (Ev ) of the (k, δ)-truss graph in Fig 6, and thereby is not efficient for constructing DC-Index. Thus, we propose another Maintenance Based Algorithm (MBA). MBA can construct both TC-Index and DC-Index, and is more efficient than DBA. The traditional truss maintenance problem is to update the trussness of edges when edges are inserted or deleted, which has been widely studied [36]–[39]. Different from that, we mainly focus on truss maintenance when triangles are validated or invalidated with respect to minimum time span. Moreover, similar to edge-oriented maintenance, updating trussness for triangle invalidation is much more efficient than triangle validation. Therefore, we only maintain edge trussness when a triangle becomes invalid due to the decease of δ, with respect to the following observations. Lemma 1. Given a graph G, the trussness of any edge in E can be decreased by at most 1 if a triangle ∆ of G gets invalid. With Lemma 1, we only need to identify the edges whose trussness will be affected by triangle invalidation and decrease their trussness by 1 for maintenance. Definition 10 (k-triangle). Given a graph G, a triangle ∆ of G is a k-triangle if the minimum edge trussness in the triangle is k. We say the level of ∆ is k, denoted by L(∆, G). When the content is clear, we replace L(∆, G) by L(∆). Lemma 2. For any k-triangle ∆ of G, the trussness of an edge e ∈ E will not be updated when ∆ gets invalid if trn(e) ̸= k. Lemma 3. For any k-triangle ∆ of G, the trussness of an edge e ∈ E may be updated when ∆ gets invalid, if trn(e) = k and one of following conditions is satisfied: (i) e ∈ ∆ or (ii) e ∈ /∆ and ∃e′ ∈ ∆ such that trn(e′ ) = k and e is connected with e′ though a series of k-triangles sharing common edges. With Lemma 2 and 3, we develop an algorithm to maintain the edge trussness for a single triangle invalidation,
(4, 6)-truss (4, 5)-truss trn(e) = 2 trn(e) = 3 trn(e) = 4 trn(e) = 5
8
8
6, 7
6
before the iteration with 𝜹 = 6
6, 7
6
after the iteration with 𝜹 = 6
Fig. 7: An example of executing MBA before and after δ = 6. which draws inspiration from the removal algorithm proposed by [37]. The most important trick is that, for each edge e ∈ E, we maintains a stricter k-support ks(e) = |{∆ : e ∈ ∆, L(∆) = trn(e)}|, which is the number of trn(e)-triangles containing e. In the trn(e)-truss, ks(e) actually becomes the number of triangles that contain e, so that ks(e) is no less than trn(e)−2. The pseudo code of triangle invalidation algorithm can be found in the conference version [46]. After the invalidation of input k-triangle ∆, we firstly decrease the k-support of each edge e of ∆ with trn(e) = k according to the case (i) of Lemma 3, and pushes e to a queue Q if ks(e) is no longer greater than trn(e) − 1, implying that its trussness will decrease. Then, for each edge e ∈ Q, since the decrease of trn(e) can further result in the decrease of trussness of other edges in a same triangle with e, we perform a breadthfirst search to find such edges according to the case (ii) of Lemma 3. Lastly, the algorithm returns the set of edges whose trussness is decreased by triangle invalidation. Then, let us consider how to construct DC-Index through edge trussness maintenance. Since the construction of DCIndex requires to compute both V-IES and H-IES, we present the methods respectively. V-IES. The V-IES between (k, δ)-truss and (k + 1, δ)-truss is simply the set of edges whose trussness is k + 1 when the triangles whose minimum time span is greater than δ have been invalidated. Thus, we can obtain all V-IESes by invalidating triangles in descending order of minimum time span gradually, and maintain the edge trussness simultaneously. H-IES. The H-IES between (k, δ)-truss and (k, δ−1)-truss can be further obtained with respect to the following observation. Lemma 4. When all triangles whose minimum time span is greater than δ have been invalidated, for an edge e with trn(e) = k, it belongs to the H-IES between (k, δ)-truss and (k, δ − 1)-truss if trn(e) decreases after any triangle ∆ with mts(∆) = δ has been further invalidated. With Lemma 4, we can obtain both V-IES and H-IES in the procedure of truss maintenance. Specifically, after invalidating each triangle whose minimum time span is δ, we only need to check the edges whose trussness is exactly the level of this triangle according to Lemma 2, and add edges whose trussness has decreased into the corresponding H-IES. The pseudo code of MBA can be found in the conference version [46]. We first build the δ-triangle list and compute the initial edge trussness of G. Then, we enumerate δ gradually in descending order and compute the H-IES and V-IES respec-
tively. For a specific δ, obtaining the V-IES is straightforward since the edge trussness is already known. Moreover, we invalidate each triangle ∆ with mts(∆) = δ by calling the triangle invalidation algorithm. For each edge returned, we add e to the H-IES between (k, δ)-truss and (k, δ − 1)-truss, where k is the level of ∆. E XAMPLE 7. Consider running MBA on the temporal graph in Fig 1. As illustrated in Fig 7, we remark the trussness of edges by different colors. The initial trussness before iterations is shown on the left. We highlight the (4, 6)-truss comprised of green and yellow edges because δmax = 6. Then, in the iteration with δ = 6, the triangle ∆ = {v2 , v7 , v8 } is invalidated because mts(∆) = 6. According to Lemma 2, (v7 , v8 ) will be not affected since L(∆) = 4 ̸= trn(v7 , v8 ) = 5. According to the case (i) of Lemma 3, (v2 , v7 ) and (v2 , v8 ) will be affected. According to the case (ii) of Lemma 3, (v2 , v3 ), (v3 , v7 ), and (v3 , v8 ) will be affected. Lastly, according to Lemma 1, the trussness of affected edges is decreased by 1. The updated trussness is shown on the right, and the current green and yellow edges comprise the highlighted (4, 5)-truss. Correctness. The correctness of MBA is established on the corretness of Lemma 1, 2, 3, and 4. Complexity. For brevity, we only compare the difference of dominant time cost between DBA and MBA here. For the quantity of visited edges (pushed into Q), two algorithms are equivalent, though DBA enumerates k firstly and MBA enumerates δ firstly. For the quantity of invalidated triangles, MBA only needs to invalidate each triangle in G t once, while DBA does that each Pkfor P k. Thus, the dominant time cost max of MBA is O( k=3 (u,v)∈Tk min{deg(u), deg(v)} + |∆|), which means MBA is more efficient than DBA. VI. I NDEX M AINTENANCE Since temporal graphs are naturally evolving, we address dynamic index maintenance in this section. We have two reasonable assumptions. Firstly, the history should not be changed, which means that we do not consider edge deletion (note that, deletion can still be handled like insertion in the same way as our approach). Secondly, it is not necessary to restrict the order of timestamps for edge insertion, which makes our approach more flexible. As a result, an evolving temporal graph can be seen as a stream of edges with arbitrary timestamps. As new edges are inserted, the k-span of existing edges may change accordingly, incurring updates to both the TC-Index and the DC-Index. Instead of rebuilding the entire indexes from scratch, we propose a filter-and-verification algorithm to find the set of edges with changed k-spans, and only update the positions of these edges in the indexes. In the following, we denote by et0 = (u, v, t) a temporal edge and by e0 = (u, v) its corresponding static edge. After t inserting et0 into a temporal graph G t , let G+ and G+ denote the updated temporal graph and its corresponding static graph, respectively.
A. Filter of k In order to find the set of edges with changed k-spans, the first step is to identify a range of k such that the k-spans of all edges are not changed for each k that is out of the range. For that, we have the following observation. T HEOREM 5. When a temporal edge et0 = (u, v, t) is inserted into G t , if k > trn(e0 , G+ ), the insertion of et0 does not change the k-span of any edge e in the k-truss of G (Tk (G)), namely, t k- spn(e, G t ) = k- spn(e, G+ ). P ROOF. When k > trn(e0 , G+ ), it has been proven in [36] that Tk (G) remains identical to that of G+ (i.e., Tk (G+ )). Since e0 does not belong to Tk (G), the minimum time span of all triangles in Tk (G) remains unchanged. Thus, the k-span of each edge in Tk (G) also remains unaffected. Intuitively, for values of k greater than the trussness of e0 in the updated graph, both the k-truss and the minimum time spans of its triangles in the original graph remain unchanged, so that the k-spans of all its edges will not be changed. Based on Theorem 5, we only need to update the k-span of edges in Tk (G) with k ≤ trn(e0 , G+ ). B. Filter of k-Span For each k in the identified range, we aim to bound the values of k-span that could be changed. There are two cases that need to be discussed, respectively. 1) Timestamp Insertion. When inserting a temporal edge et0 into G t , if the underlying static edge e0 already exists (namely, e0 ∈ E(G)), the insertion only needs to add the timestamp t to τ (e0 ). This operation does not change the trussness of any edge and only reduce the minimum time span of existing triangles containing e0 . Moreover, only some of such triangles lead to decreases in the k-span of edges. The following lemma provides a criterion for identifying these triangles. Lemma 5. Given a temporal graph G t , a support threshold k and a temporal edge et0 with e0 ∈ E(G) to be inserted, for each triangle ∆ containing e0 , the k-span of any edge will not be decreased by the decrease of mts(∆), if mts(∆, G t ) < δm or t mts(∆, G+ ) ≥ δm , where δm = max{k- spn(e, G t ) : e ∈ ∆}. P ROOF. When mts(∆, G t ) < δm , for any edge e ∈ ∆ with k- spn(e) = mts(∆, G t ), its k-span cannot decrease, as this would require at least one triangle in G whose minimum time span drops from at least δm to below δm , which is impossible. Moreover, for any e ∈ ∆ with k- spn(e) < mts(∆, G t ), its kspan remains unchanged, since ∆ cannot be a valid triangle in its corresponding truss either before or after the insertion. Therefore, no edge in ∆ has its k-span decreased, and thus no edge in G is affected by ∆. The case for when mts(∆, G t ) ≥ δm can be proved analogously. Thus, only the triangles that both contain e0 and do not satisfy the conditions in Lemma 5 need to be considered, which are denoted by Te∆ . For each triangle ∆ ∈ Te∆ , we 0 0 − + − + compute a corresponding k-span interval [δ∆ , δ∆ ] (δ∆ < δ∆ )
such that the set of edges in G with k-span outside this interval remains unchanged in G+ due to the change induced by ∆. + For each ∆ ∈ Te∆ , it is evident that δ∆ cannot exceed 0 + the maximum k-span of the edges in triangle ∆, i.e., δ∆ = − t max{k- spn(e, G ) : e ∈ ∆}. To determine a proper δ∆ , the key is to identify the minimum δ such that ∆ can be a valid + }, triangle in a (k, δ)-truss. We define δ̂ = max{δ∆ : ∆ ∈ Te∆ 0 which represents the maximum k-span among all edges potentially affected by the insertion of a temporal edge. Then for any edge e ∈ ∆ ∈ Te∆ , the lower bound of its k-span is given 0 by δ(e) = min{δa : |{e, e′ , e′′ }| ≥ k − 2, k- spn(e′ , G t ) ≤ t δ̂, k- spn(e′′ , G t ) ≤ δ̂, mts(∆, G+ ) ≤ δa }, which implies that e can participate in at most k − 2 valid triangles in (k, δa )-truss. Furthermore, δ(e) = min{δb : |{e, e′ , e′′ }| ≥ k − 2, δ(e′ ) ≤ t ) ≤ δb } serves as a tighter lower δb , δ(e′′ ) ≤ δb , mts(∆, G+ bound for the k-span of e, as it incorporates an extra constraint regarding δ values. Hence, triangle ∆ only exist in (k, δ ∗ )t truss where δ ∗ ≥ max{mts(∆, G+ ), max{δ(e), e ∈ ∆}}. Lemma 6. Given a triangle ∆ ∈ Te∆ and a support threshold 0 + − t ), max{δ(e) : e ∈ ∆}} and δ∆ = k, let δ∆ = max{mts(∆, G+ t ′ max{k- spn(e, G ) : e ∈ ∆}, for any integer δ such that − + δ ′ < δ∆ or δ ′ > δ∆ , the set of edges in G with k-span equal ′ to δ remains unaffected in G+ by the change induced by ∆. + P ROOF. We first consider the case δ ′ > δ∆ . For any edge + e ∈ E(G) with k- spn(e) > δ∆ , suppose that its k-span is decreased. Then there must exist an edge e′ sharing a triangle + with e whose k-span also drops from at least δ∆ to below + δ∆ . By applying this recursively through a series of triangles sharing common edges, we eventually reach an edge e∗ of ∆ + with k- spn(e∗ ) > δ∆ and its k-span is decreased due to the reduction in the minimum time span of ∆. However, by the + definition of δ∆ , no such edge e∗ exists in ∆, which leads to a contradiction. Moreover, the reduction in the minimum time span of ∆ cannot cause any edge to increase its k-span. Thus, the set of edges with k-span equal to δ ′ keeps same. + Then we prove the case δ ′ < δ∆ . For any edge e ∈ ∆, since k- spn(e) <= δ̂, it follows that k- spn(e) ≥ δ(e) ≥ − δ(e) and max{mts(∆, G t ), max{k- spn(e) : e ∈ ∆}} ≥ δ∆ . ′ Therefore, the (k, δ )-truss in G does not contain ∆. Similarly, − since δ ′ < δ∆ , ∆ is also excluded from the (k, δ ′ )-truss in G+ . Consequently, the (k, δ ′ )-truss remains unchanged, and thus the set of edges with k-span equal to δ ′ keeps same.
Therefore, after inserting a temporal edge et0 , the affected range of k-span values can be identified by R(et0 ) = S − + ∆∈Te∆ [δ∆ , δ∆ ], which can be simply merged to a set of 0 disjoint intervals. 2) Edge Insertion. When a temporal edge et0 is inserted into G t with e0 ∈ / E(G), the static edge e0 is added to E(G) and its timestamp set initialized as τ (e0 ) = t. According to [36], the t trussness of e0 in updated graph G+ can be estimated within the interval [ka , kb ], where ka = max{k : |{e0 , e′ , e′′ }| ≥ k − 2, trn(e′ , G) ≥ k, trn(e′′ , G) ≥ k), kb = max{k : |{e0 , e′ , e′′ }| ≥ k − 2, trn(e′ , G) ≥ k − 1, trn(e′′ , G) ≥ k − 1) and kb − ka ≥ 1. Assuming that the trussness of e0 in G is
4-span(e) = 4 4-span(e) = 8 4-truss 3-truss
8
Fig. 8: An example of estimating the k-span upper bound for a new edge. ka , for e ∈ E(G) ∪ e0 with trn(e, G) < trn(e0 , G+ ) may have their trussness increased by 1. As a result, new edges may be introduced into Tk (G). Since these edges are not originally in Tk (G) and their k-spans are undefined, for each such edge e, we estimate an upper bound on its k-span, denoted by δ(e), − + before obtaining the k-span interval [δ∆ , δ∆ ] for each triangle ∆ containing e0 . First, for k ∈ [3, ka ], the edge e0 is added into Tk (G), and the upper bound of its k-span can be estimated by: δ(e0 ) = min{δ : |{e0 , e′ , e′′ }| ≥ k − 2, k- spn(e′ , G t ) ≤ t ) ≤ δ}. Next, we estimate an δ, k- spn(e′′ , G t ) ≤ δ, mts(∆, G+ upper bound on the k-span of edges whose trussness increases by one after the insertion of e0 . Definition 11 (LEk ). When a temporal edge et0 with e0 ∈ / E(G) is inserted into G t , for each k ∈ [3, trn(e0 , G+ )], we define the set LEk = {L1Ek , L2Ek , · · · , LiEk }, where 0 ≤ i, satisfying: (1) ∀ e ∈ LEk , trn(e, G+ ) = k and trn(e, G) = k − 1; (2) For any LjEk , any two different edges in it can be connected through a series of adjacent (k − 1)- triangles formed by edges in E(G) ∪ e0 ; (3) For ∀ej ∈ LjEk , ∀el ∈ LlEk , j ̸= l, there does not exist any (k − 1)-triangle formed by the edges E(G) ∪ e0 that contains both ej and el . For each LiEk within LEk , we can independently estimate an upper bound δ(LiEk ) on the k-span of the internal edges. Definition 12 (δ(LiEk )). For each k ∈ [3, trn(e0 , G+ )], let e′ be any edge in LiEk and e′′ be any edge not in LiEk , the upper bound of the k-span for edges in LiEk is defined as: δ(LiEk ) = max{t1 , t2 } t t1 = max{mts(∆, G+ ) : e′ ∈ ∆, L(∆, G+ ) = k} ′′
t
′
′′
(1)
′′
t2 = max{k- spn(e , G ) : e , e ∈ ∆, trn(e , G) ≥ k} Lemma 7. For a given k ∈ [3, trn(e0 , G+ )] and any edge e′ ∈ LiEk , δ(LiEk ) serves as an upper bound on the k-span of e′ , i.e., δ(e′ ) = δ(LiEk ). P ROOF. For ∀ e′ ∈ LiEk , by the definition of t1 , the edge e′ must participate in at least k − 2 triangles whose minimum time spans are less than t1 and for which L(∆, G+ ) = k. Consider any ∆ containing e′ and let e∗ denote any other edge in ∆. There are two possible cases. On one hand, if e∗ ∈ / LiEk ∗ ∗ t and trn(e , G) ≥ k, then we have k- spn(e , G+ ) ≤ t2 . On
the other hand, if e∗ ∈ LiEk , then e∗ satisfies the same triangle support condition as e′ . By recursively applying this reasoning, it follows that e′ participates in at least k − 2 valid triangles t within (k, max{t1 , t2 })-truss. Thus, k- spn(e′ , G+ ) ≤ δ(LiEk ) i ′ and δ(LEk ) is an upper bound for the k-span of e . E XAMPLE 8. When inserting the temporal edge (v3 , v4 , 2) into the temporal graph in Fig 8, accroding to the definition of ka and kb , the trussness of edge (v3 , v4 ) is estimated within the range [4, 5]. For k = 4, δ((v3 , v4 )) is computed as 8, supported by triangles {v0 , v3 , v4 } and {v1 , v3 , v4 }. Moreover, the insertion triggers an increase in trussness to 4 for two disjoint edge sets: L1E4 = {(v1 , v5 ), (v3 , v5 ), (v4 , v5 )} and L2E4 = {(v3 , v6 ), (v3 , v7 ), (v4 , v6 ), (v4 , v7 ), (v6 , v7 )}. For L1Ek , the triangles satisfying the conditions in t1 include {{v1 , v3 , v5 }, {v1 , v4 , v5 }, {v3 , v4 , v5 }}, and t1 is computed as 10. Then, the edges satisfying the conditions in t2 are {(v1 , v3 ), (v1 , v4 ), (v3 , v4 )}, and t1 is computed as 8. Thus, δ(L1E4 ) = max{10, 8} = 10. Similarly, δ(L2E4 )= max{8, 9} = 9. For k = 5, the edges between the vertices v0 , v1 , v2 , v3 , v4 pairwise form L1E5 , and δ(L1E5 ) is computed as 8. For all newly inserted edges in Tk (G), we assign their upper bounds of k-span to be their k-span values in the original temporal graph. Accordingly, the edge insertion can be equivalently transformed into a timestamp insertion maintenance problem, namely, reducing the minimum time span of certain t ). triangles from ∞ to mts(∆, G+ C. Filter of Edge For each k-span interval [δ − , δ + ] in R(et0 ), the potentially affected edges with k-span within this interval can be further filtered since our k-span maintenance exhibits a triangle propagation property similar to that of truss maintenance [36]. We define the k-rank of triangle ∆, denoted by k- rnk(∆), as the minimum δ value such that triangle can be included in a (k, δ)truss for the given k. Based on this definition, after inserting a temporal edge et0 , a potentially affected edge e needs to satisfy two conditions: 1) k- spn(e) ∈ [δ − , δ + ] ∈ R(et0 ) and 2) e, e0 and another e′ form a new triangle with k- rnk(∆) ∈ [δ − , δ + ] or e is connected with e0 through a series of adjacent triangles, each ∆ of which has k- rnk(∆) ∈ [δ − , δ + ]. Due to the connectivity of the triangles in the second condition, for each k-span interval [δ − , δ + ], we adopt a local search method to identify all potential affected edges, which s form a subset of the Tk,δ+ of G, denoted as Tk,δ + . During ∆ s this process, we construct the δ-triangle list S of Tk,δ + and count the potentially valid triangles associated with each candidate edge. Algorithm 1 provides the pseudocode for this procedure. For a given k and a k-span interval [δ − , δ + ], we use breadth-first search to locate all edges with k-span values within [δ − , δ + ] that are connected to edge e0 via a sequence of triangles whose k-ranks are not greater than δ + . (Line 2-23) For each such edge e, we consider all triangles with k-rank not exceeding δ + as its potentially valid triangles, set the number of these triangles as the support of e, and add them to δtriangle list S ∆ (lines 10-23). If an edge with a k-span less
Algorithm 1: Get Affected Subgraph (GAS) Input: a temporal graph G t , the inserted temporal edge et0 , a support threshold k and a k-span interval [δ − , δ + ] s Output: The potentially affected edge Tk,δ + and the ∆ local δ-triangle list S ∆ 1 S ← ∅; Q ← ∅; visited ← ∅; + 2 if k- spn(e0 ) ≤ δ and k- spn(e0 ) ≥ δ − then 3 Q.push(e0 ); visited ← visited ∪ e0 ; 4 for each ∆ containing e0 in G ∪ e0 do 5 if k- rnk(∆) > δ + then 6 continue; 7 for each other e of ∆ do 8 if k- spn(e) ≤ δ + and k- spn(e) ≥ δ − then 9 Q.push(e); visited ← visited ∪ e; 10 while Q ̸= ∅ do 11 e ← Q.pop(); sup[e] ← 0; 12 for each ∆ containing e in G ∪ e0 do 13 if k- rnk(∆) > δ + then 14 continue; ∆ ∆ 15 Smts(∆) ← Smts(∆) ∪ ∆; 16 sup[e] ← sup[e] + 1; 17 for each other e′ of ∆ do 18 if e′′ ∈ / visited then 19 if k- spn(e′ ) ≥ δ − then 20 Q.push(e′ ); 21 else 22 s[e′ ] ← ∞; 23 visited ← visited ∪ e′ ; ∆ s 24 return Tk,δ + and S ;
than δ − is encountered, the search terminates for that branch, and its support is set to ∞ (lines 19-22). D. Verification of Edge k-Span Algorithm 2 provides the pseudocode of the complete filterand-verification Procedure. The process iterates over k from 3 to trn(e0 , G+ )] (Line 1). For each possible k, the k-span filtering process considers both timestamp insertion and edge insertion. In the case of edge insertion, we employ a modified version of the trussness maintenance algorithm [36] to identify edges that need to be inserted into Tk (G) and assign their initial k-span values, thereby transforming the problem into the timestamps insertion case (lines 3–6). For the timestamp insertion case, we compute the filtered k-span intervals R(et0 ) according to the proposed lemma(lines 7–11). For each k-span interval [δ − , δ + ] in R(et0 ), Algorithm 1 is performed to extract s s the affected local subgraph Tk,δ + , and on Tk,δ + , we perform the decomposition function decomph() in DBA from δ + to s δ − to accurately verify the k-span values of all edges in Tk,δ +. (lines 12–18). With all updated k-span values of the edges, we can update TC-Index or DC-Index by changing the positions of the edges.
Algorithm 2: Filter-and-Verification Input: a temporal graph G t and the inserted temporal edge et0 Output: updated k-spans of edges for each k t t t 1 G+ ← G ∪ e 0 ; 2 for k ← trn(e0 , G+ ) until 3 do 3 if e0 ∈ / E then 4 identify the edge set Tk (G+ ) \ Tk (G) by truss maintenance; 5 for each edge e ∈ Tk (G+ ) \ Tk (G) do 6 k- spn(e) ← δ(e); 7 compute Te∆ using the proposed Lemma 5; 0 8 for each ∆ ∈ Te∆ do 0 − + 9 compute [δ∆ , δ∆ ]; − + 10 R(et0 ) ← R(et0 ) ∪ [δ∆ , δ∆ ]; 11 merge overlapping intervals in R(et0 ); 12 for each [δ − , δ + ] ∈ R(et ) do s ∆ 13 Tk,δ ← GAS(G t , et0 , k, [δ − , δ + ]); +, S + 14 for δ ← δ until δ − do s s 15 Tk,δ−1 , R ← decomph(Tk,δ , S ∆ ); 16 for each e ∈ R do 17 if k- spn(e) ̸= δ then 18 update k- spn(e) to δ; 19 return all updated k-span values of the edges in E(G);
Since the index updating is straightforward, the details are omitted. VII. E XPERIMENTS In this section, we conduct extensive experiments to evaluate the proposed approaches on a Linux machine with Intel Xeon 3.5GHz CPU and 128GB RAM. All algorithms are implemented in C++ 11 and compiled by g++ with O3 optimization. A. Dataset and Empirical Study )We evaluate our proposed approaches on eight publicly available real-world temporal graphs from [42] and [43]. Table I summarizes their statistics, where |V| denotes the number of vertices, |E| the number of static edges, n the number of distinct timestamps, |τ | the average number of timestamps per edge, |∆| the number of triangles, kmax the maximum trussness of edges, and δmax the maximum minimum time span of triangles. The datasets vary widely in scale, with |E| ranging from 16K to 36M. However, regardless of graph size, kmax remains within a narrow range due to the strict static cohesion of k-truss subgraphs. There are two observations that support our motivation of studying (k, δ)-truss on the datasets. Firstly, by comparing n and δmax , we can see there are indeed triangles with minimum time span as long as the duration of whole graph, which are not cohesive in terms of time. Moreover, we conduct an empirical study on these datasets. Fig 9 illustrates the distribution of triangle counts on minimum time span for four of them. We can see that, although the triangles with longer minimum time
(a) Mathoverflow.
(b) Superuser.
(c) Wikitalk.
(d) Youtube.
Fig. 9: Distribution of triangle counts on minimum time span.
Fig. 10: Response time of query processing on different datasets, in which k = 30% · kmax and δ = 60% · δmax . span are less, the distribution does not have a typical long tail. In contrast, the counts are not dropping that fast. Thus, δ is effective to constrain the structure of (k, δ)-truss. B. Query Processing To the best of our knowledge, no existing work investigates the (k, δ)-truss query. Thus, we use the proposed query processing algorithms, Online-Query, TC-Query, and DC-Query to evaluate efficiency. Given k and δ, we record the average running time of 100 times of repeated execution. Since each dataset has different value ranges of k and δ, we adopt relative parameters and set k = 30%kmax and δ = 60%δmax respectively in default for a given dataset. The running time of three algorithms under the default parameters is reported in Fig 10. TC-Query and DC-Query have similar query efficiency, and are 2∼4 orders of magnitude faster than Online-Query. Even for the two largest graphs with tens of millions of edges, index-based approaches can finish within less than 100 ms. Then we test the query efficiency with respect to varying parameters. Firstly, the running time of three algorithms with varying values of k on four datasets is reported in Fig 11. As expected, index-based approaches spend less time on processing queries with greater k, because fewer edges need to be scanned. In contrast, Online-Query spends more time because truss decomposition needs to peel more edges. Note that, even
TABLE I: Statistics of datasets. Dataset Email Mathoverflow Askubuntu Superuser Wikitalk Youtube Stackoverflow Wikipedia
|V| 0.9K 24K 159K 194K 1.1M 322K 2.6M 1.8M
|E| 16K 187K 455K 714K 2.7M 9.3M 28.1M 36.5M
n 803 2450 2613 2773 2320 225 2774 2235
|τ | 11.5 1.6 1.2 1.2 1.4 1.0 1.2 1.1
|∆| 105K 1.4M 680K 1.5M 8.1M 12M 114.2M 126.6M
kmax 23 42 26 35 49 33 79 59
δmax 800 2336 2040 2692 2231 225 2768 2231
Fig. 11: Response time of query processing with varying k and δ = 60%δmax .
Fig. 12: Response time of query processing with varying δ and k = 30%kmax . when k = 10%·kmax (which is usually the minimum value 3), the running time of TC-Query and DC-Query is never greater than 100 ms. Moreover, the running time of three algorithms with varying values of δ on those datasets is reported in Fig 12. Different from k, the running time of index-based approaches increases gradually with increasing δ, because the greater δ relaxes the constraint and more edges need to be scanned. Lastly, we use heat map to visualize the running time of DCQuery under more combinations of query parameters (k = 10%, 20%, · · · , 100% of kmax and δ = 10%, 20%, · · · , 100% of δmax ) in Fig 13. The time cost is at most 0.41 sec on the largest dataset Wikipedia, and generally decreases as k increases or δ decreases. C. Index Construction Firstly, we report the construction time of proposed TCIndex and DC-Index. For each dataset, we use DBA to construct TC-Index and MBA to construct both TC-Index and DC-Index respectively. As illustrated in Fig 14, index construction costs less than 1 sec for the smallest dataset Email with 16K edges and nearly 3000 sec for the largest dataset Wikipedia with 36M edges. The construction time increases evenly with the increasing scale of graph, which implies that DBA and MBA reduce the redundant computation effectively. Moreover, as expected, MBA is more efficient than DBA on all datasets. Moreover, the statistics of constructed indexes are shown in Table II. The total edge number of DC-Index is about 1.5X-10.4X large as the corresponding graph. Compared with
Fig. 13: Response time of DCQuery with varying k and δ.
storing all possible (k, δ)-trusses directly, DC-Index achieves the compression ratio up to 10−4 on most datasets. The only exceptional dataset is Youtube. According to Theorem 1, δmax is the key factor affecting the compression ratio. Since YouTube has a very small δmax , the compression ratio of its DC-Index is worse than other datasets. Due to the effective compression, the space cost of DC-Index is at most 903MB in our experiments. However, we observed that DC-Index is only a little smaller than TC-Index. The rationale is that, since δmax is much greater than kmax for these datasets, the weights of horizontal edges in Eh are generally less than vertical edges in Ev , so that the (k, δ)-truss arborescence has only a few vertical edges. As a result, the space of DC-Index is almost as large as TC-Index. For the above anomaly observed, we conduct an extra experiment to verify the effectiveness of DC-Index. Specifically, we merge every 20, 25, 30, 35, or 40 consecutive timestamps into a single new timestamp for coarsening the time granularity (like from day to month), which will decrease δmax but not change kmax . Thus, the weights of horizontal edges in new Eh will become greater. Fig 15 illustrates the comparison of total edge number between DC-Index and TC-Index with the new settings, on two selected datasets. Clearly, DC-Index regains the advantage in the more balanced temporal graphs. D. Index Maintenance We randomly remove 1000 edges from Mathoverflow, Askubuntu, Superuser, and Wikitalk and reinsert them into the original graphs, for evaluating the time cost of index
TABLE II: Statistics of indexes. dataset Email MathOverflow AskUbuntu Superuser WikiTalk YouTube Stackoverflow Wikipedia
avg. entry (k-span) #
TC-Index total edge #
total edge #
total edge # / |E|
290 1478 1086 1365 1089 170 2028 1304
162K 1959K 959K 2108K 10.60M 16.74M 139.07M 164.24M
154K 1871K 958K 2106K 10.58M 14.25M 138.92M 163.40M
9.57 10.40 2.10 2.95 3.79 1.52 4.93 4.47
DC-Index P space (MB) compression ratio (total edge # / k,δ |Tk,δ |) 0.76 9.35 7.33 13.83 62.01 125.93 746.15 902.63
17.5 × 10−4 6.25 × 10−4 11.43 × 10−4 7.4 × 10−4 7.67 × 10−4 1.11 × 10−2 6.00 × 10−4 8.60 × 10−4
Fig. 14: Construction time of TC-Index and DC-Index using DBA and MBA for different datasets.
Fig. 16: Update time evaluation of (k, δ)-truss index. VIII. R ELATED W ORK
Fig. 15: Comparison of total edge number between DC-Index and TC-Index with different time granularity.
maintenance. Figure 16 (a) compares the average update time per insertion of TC-Index (TC-IM) and DC-Index (DCIM) based on Algorithm 2 against the index reconstruction from scratch based on MBA. Both TC-IM and DC-IM can achieve up to two orders of magnitude speedup compared to the baseline. For example, on WikiTalk, TC-IM processes edge insertions in 0.36s and DC-IM in 0.53s, while index reconstruction takes 107s and 111s, respectively. Moreover, TC-Index slightly outperforms DC-Index, primarily due to the more complex tree-based structure of DC-Index, which requires additional structural adjustments. Figure 16 (b) illustrates the distribution of index update time costs for 1,000 edge insertions. For Askubuntu, Superuser, and Wikitalk, a half of the updates are finished within 0.01ms, demonstrating that our proposed filter of k values, k-span values, and potentially affected edges are effective. In contrast, for Mathoverflow with much higher clustering coefficient (see Table I), the filter of potentially affected edges is not as effective as the other datasets. Additionally, the update time cost distributions of DC-Index and TC-Index are consistent, because the main time costs of both are on Algorithm 2.
Recently, there emerge studies on k-truss for temporal graphs. The (k, ∆, θ)-truss [23] inherits the definition of persistent core [17], and requires its edges to have supports no less than k − 2 in a number of time windows no shorter than ∆, the total duration of which is no less than θ. Such a truss model is not general enough for many application scenarios. The (k, ∆)-truss (also known as span truss) [22] defines the temporal support of edges, which is the support in a projection of temporal graph during a period, and aims to find the ktruss that is cohesive enough in the specific time window ∆. This truss model is more general. However, it always needs the user to give a specific time window in which triangles occur. In contrast, our (k, δ)-truss allows triangles to occur in different time windows that are still short enough. Thus, our (k, δ)-truss is more relaxed than span truss, and meanwhile, can be equivalent to span truss when an extra time window is specified and δ = ∞ if necessary. Since our (k, δ)-truss is designed on top of temporal triangles, we also investigate the related researches [24]–[29]. Different from their typical definitions of triangle/motif duration, we propose another kind of duration, namely, minimum time span that is more meaningful in the context of k-truss. Moreover, the design of our indexes is inspired by (k, l)core [44] and (k, p)-core [45], which also consider the similar property with respect to dual parameters. The various elegant algorithms [31] [36]–[39] to solve k-truss problems provide useful guides to develop our index construction algorithms.
IX. C ONCLUSION In this paper, we study a novel (k, δ)-truss on temporal graphs, which constrains the minimum time span of triangles to guarantee temporal cohesion. Such a constraint tailors the static truss in time dimension effectively. To address the query problem of (k, δ)-truss, we propose both index-free and index-based approaches. The indexes that exploits the dual containment property of (k, δ)-truss to compress the space can deliver efficient query processing. Moreover, we develop scalable index construction algorithms and dynamic index maintenance algorithm. The theoretical proof and experimental evaluation of our approach are provided. R EFERENCES [1] N. Masuda, R. Lambiotte, “A Guide to Temporal Networks,” World Scientific Publishing Europe Ltd, 2016. [2] P. Holme, J. SaramakiJari, “Temporal network,” Springer, 2012. [3] G. Kossinets, D. Watts, “Empirical analysis of an evolving social network,” science, 311(5757): pp. 88-90, 2006. [4] X. Huang, Y. Yang, Y. Wang, et al, “Dgraph: A large-scale financial dataset for graph anomaly detection,” Advances in Neural Information Processing Systems, 35: pp. 22765-22777, 2022. [5] M. Filipovska, H. Mahmassani, “Spatio-Temporal Characterization of Stochastic Dynamic Transportation Networks,” IEEE Transactions on Intelligent Transportation Systems, 24(9): pp. 9929-9939, 2023. [6] C. Hidalgo, C. Rodrı́guez-Sickert, “The dynamics of a mobile phone network,” Physica A: Statistical Mechanics and its Applications, 387(12): pp. 3017-3024, 2008. [7] J. Simeunović, B. Schubnel, et al, “Spatio-temporal graph neural networks for multi-site PV power forecasting,” IEEE Transactions on Sustainable Energy, 13(2): pp. 1210-1220, 2021. [8] N. Masuda, P. Holme, “Introduction to temporal network epidemiology,” Springer Singapore, 2017. [9] E. Galimberti, A. Barrat, F. Bonchi, et al, “Mining (maximal) span-cores from temporal networks,” Proceedings of the 27th ACM international Conference on Information and Knowledge Management, pp. 107-116, 2018. [10] H. Wu, J. Cheng, et al, “Core decomposition in large temporal graphs,” 2015 IEEE International Conference on Big Data (Big Data), pp. 649–658, 2015. [11] J. Yang, M. Zhong, Y. Zhu, T. Qian, M. Liu, and J. Yu, “Scalable timerange k-core query on temporal graphs,” PVLDB, 16(5): pp. 1168–1180, 2023. [12] M. Yu, D. Wen, L. Qin, et al, “On querying historical k-cores,” PVLDB, 14(11): pp. 2033–2045, 2021. [13] Z. Wang, M. Zhong, Y. Zhu, et al. “On More Efficiently and Versatilely Querying Historical k-Cores, “ PVLDB, 18(5): pp. 1335-1347, 2025. [14] M. Zhong, J. Yang, Y. Zhu, T. Qian, M. Liu, J. Yu, “A Unified and Scalable Algorithm Framework of User-Defined Temporal (k, X )-Core Query,” IEEE Transactions on Knowledge and Data Engineering, 2024. [15] W. Bai, Y. Chen, and D. Wu, “Efficient temporal core maintenance of massive graphs,” Information Sciences, 513: pp. 324–340, 2020. [16] Z. Du, M. Zhong, Y. Zhu, et al. “Efficient Frequency-Aware k-Core Query on Temporal Graphs, “ ICDE, pp. 2366-2379, 2025. [17] R. Li, J. Su, L. Qin, J. Yu, and Q. Dai, “Persistent community search in temporal networks,” ICDE, pp. 797–808, 2018. [18] L. Chu, Y. Zhang, Y. Yang, L. Wang, and J. Pei, “Online density bursting subgraph detection from temporal graphs,” PVLDB, 12(13): pp. 2353–2365, 2019. [19] H. Qin, R. Li, Y. Yuan, G. Wang, W. Yang, and L. Qin, “Periodic communities mining in temporal networks: Concepts and algorithms,” IEEE Transactions on Knowledge and Data Engineering, 34(8): pp. 3927-3945, 2020. [20] Y. Li, J. Liu, H. Zhao, J. Sun, Y. Zhao, and G. Wang, “Efficient continual cohesive subgraph search in large temporal graphs,” World Wide Web, 24(5): pp. 1483–1509, 2021. [21] Y. Tang, J. Li, N. Haldar, Z. Guan, J. Xu, and C. Liu, “Reliable community search in dynamic networks,” PVLDB, 15(11): pp. 2826–2838, 2022.
[22] Q. Lotito, A. Montresor, “Efficient Algorithms to Mine Maximal SpanTrusses From Temporal Graphs,” unpublished. [23] L. Xu, R. Li, G. Wang, et al, “Research on K-truss Community Search Algorithm for Temporal Networks,” Journal of Frontiers of Computer Science and Technology, 14(9): pp. 1482-1489, 2020. [24] N. Pashanasangi, and C. Seshadhri, “Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering,” KDD, pp. 1319–1328, 2021. [25] J. Wang, Y. Wang, W. Jiang, Y. Li, and K. Tan, “Efficient Sampling Algorithms for Approximate Temporal Motif Counting,” CIKM, pp. 1505–1514, 2020. [26] A. Paranjape, A. Benson, and J. Leskovec, “Motifs in Temporal Networks,” WSDM, pp. 601–610, 2017. [27] P. Liu, A. Benson, and M. Charikar, “Sampling Methods for Counting Temporal Motifs,” WSDM, pp. 294–302, 2019. [28] P. Liu, V. Guarrasi, and A. Sarıyuce, “Temporal Network Motifs: Models, Limitations, Evaluation,” IEEE Transactions on Knowledge and Data Engineering, 35: pp. 945–957, 2023. [29] L. Kovanen, M. Karsai, K. Kaski, J. Kertész, and J. Saramäki, “Temporal motifs in time-dependent networks,“ Journal of Statistical Mechanics: Theory and Experiment, P11005, 2011. [30] J. Leskovec, J. Kleinberg, C. Faloutsos, “Graphs evolution: Densification and shrinking diameters” ACM transactions on Knowledge Discovery from Data (TKDD), 1(1): pp. 2–42, 2007. [31] J. Wang, J. Cheng, “Truss decomposition in massive networks,” PVLDB, 5(9): pp. 812–823, 2012. [32] P. Chen, C. Chou, and M. Chen, “Distributed algorithms for k-truss decomposition,” IEEE International Conference on Big Data (Big Data), pp. 471–480, 2014. [33] Y. Che, Z. Lai, S. Sun, Y. Wang, and Q. Luo, “Accelerating truss decomposition on heterogeneous processors,” Proceedings of the VLDB Endowment, 13(10): pp. 1751-1764, 2020. [34] H. Kabir, K. Madduri, “Parallel k-truss decomposition on multicore systems,” IEEE High Performance Extreme Computing Conference (HPEC), pp. 1-7, 2017. [35] H. Kabir, K. Madduri, “Shared-memory graph truss decomposition,” IEEE 24th International Conference on High Performance Computing (HiPC), pp. 13–22, 2017. [36] X. Huang, H. Cheng, L. Qin, et al, “Querying k-truss community in large and dynamic graphs,” Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 1311-1322, 2014. [37] Y. Zhang, J. Yu, “Unboundedness and efficiency of truss maintenance in evolving graphs,” Proceedings of the 2019 International Conference on Management of Data, pp. 1024-1041, 2019. [38] R. Zhou, C. Liu, J. Yu, et al, “Efficient truss maintenance in evolving networks,” arXiv preprint arXiv:1402.2807, 2014. [39] Q. Luo, D. Yu, X. Cheng, et al, “Batch processing for truss maintenance in large dynamic graphs,” IEEE Transactions on Computational Social Systems, pp. 1435-1446, 2020. [40] Z. Sun, X. Huang, Q. Liu, et al, “Efficient Star-based Truss Maintenance on Dynamic Graphs,” Proceedings of the ACM on Management of Data, 1(2): pp. 1-26, 2023. [41] V. Batagelj and M. Zaversnik, “An o (m) algorithm for cores decomposition of networks,” arXiv preprint cs/0310049, 2003. [42] J. Leskovec, A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014. [43] J. Kunegis, “Konect: the koblenz network collection,” in Proceedings of the 22nd international conference on world wide web, pp. 1343–1350, 2013. [44] Y. Chen, J. Zhang, Y. Fang, et al, “Efficient community search over large directed graphs: An augmented index-based approach,” Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 3544-3550, 2021. [45] C. Zhang, F. Zhang, W. Zhang, et al, “Exploring finer granularity within the cores: Efficient (k, p)-core computation,” ICDE, pp. 181-192, 2020. [46] C. Hu, M. Zhong, Y. Zhu, et al. “Querying cohesive subgraph regarding span-constrained triangles on temporal graphs,“ ICDE, pp. 3338-3350, 2024.