Distributed Truss Computation in Dynamic Graphs

We propose our distributed truss decomposition algorithm in this section based on our distributed model. We first introduce two auxiliary indexes, namely adjMap and trussMap, which are based on the locality property of the $k$ -truss. We then introduce the procedure and analysis of the proposed algorithm, which is based on the two indexes.

The distributed model encounters the following two truss decomposition challenges.

• The most important metric for calculating the trussness is the support of edges, which is the initial value of trussness for edges. All neighboring nodes of both endpoints of the edge must be identified to calculate the support of an edge.

• Edges are virtual connections for communication between nodes. Thus, the value of support for each edge cannot exist on a nonexistent entity.

To address the above challenges, we calculate the support value of all neighboring edges by utilizing the node to store local topological information regarding its incident edges and two-hop neighboring nodes. Furthermore, the following property bears the calculation of the trussness applied to the support of the edges. The locality property is formally presented as follows.

Property 1 (Locality^{[ 25 ]}). Given a graph $G=(V,$ $E)$ , $\forall e\in E$ , $t(e)=k$ if and only if the following conditions are met.

(1) An edge subset $E_k\subset EN(e)$ such that $|E_k|=2(k-2)$ , edges in $E_k$ form total $(k-2)$ triangles with $e$ , and the trussness of each edge in $E_k$ is not less than $k$ .

(2) There is not a subset $E_{k+1}\subset EN(e)$ does not exist such that $E_{k+1}=2(k-1)$ , edges in $E_{k+1}$ form total $(k-1)$ triangles with $e$ , and the trussness of each edge in $E_{k+1}$ is not less than $k+1$ .

The property describes that if the trussness of an edge $e$ is equal to $k$ , then at least $(k-2)$ triangles contain $e$ and the trussness of each edge in these triangles is at least $k$ . Therefore, the trussness of an edge can be calculated from the trussness of the incident edges of the edge. More specifically, the trussness can be calculated from the trussness of the edges that form triangles with the edge.

We design two indexes according to the locality property to store the neighboring information for each node. For a node $u$ in our distributed system, the first index is adjMap, which is a list of key-value pairs used to store $2$ -hop adjacency nodes of $u$ . The keys of adjMap are the neighbor nodes of $u$ , and the value corresponding to each key is the linked list of neighboring nodes of the stored node by the key. The second index is trussMap, which stores the estimated trussness of $2$ -hop incident edges of a node $u$ . The trussness of the incident edges of $u$ is calculated and maintained by $u$ . Figure 3 shows an example of the adjMap and the trussMap for node 1 in Fig. 2 . In Fig. 3a , the keys of adjMap are maintained by node 1, and the values are received from neighboring nodes of node 1. Figure 3 shows the change of node 1 updating the trussMap after receiving messages from neighbors. The trussMap comprises two parts: one part is the trussness estimates of the incident edges of node 1 (this part is calculated and maintained by node 1 itself), and another part is the trussness estimates of the incident edges of node 1’s neighboring nodes (this part is kept by node1 receiving data from the neighboring nodes).

10.26599/TST.2022.9010019.F003 Fig. 32-hop auxiliary index for node 1 in Fig. 2.

In our distributed model, each node is responsible for computing and updating the estimated trussness of its incident edges by maintaining trussMap. Algorithm 1 shows the execution process of node $u$ . The proposed algorithm has two phases: the initialization and the execution phases.

In the initialization phase (lines 1–8), the adjacency nodes of $u$ exchange their adjMap values with $u$ to compute trussMap. The initially estimated trussness of an edge is the support of the edge plus $2$ (line 6). $u$ sends its trussMap to the neighboring nodes and sets the Changed flag to false to end the process (lines 7 and 8).

The execution phase is the process of iterative execution of the entire distributed system (lines 9–22). In each round of the execution phase, $u$ receives the trussness of incident edges to neighbor nodes (line 11). Thus, each node can receive the trussness of the 2-hop incident edges. Afterward, $u$ updates the trussness of incident edges through the locality property by the function ComputeTruss (line 16). This function then returns the maximum $k$ for which a value not less than $k-2$ exists in the counter, and the algorithm is shown in Algorithm 2. If the updated estimated trussness $t$ of the incident edges is smaller than the value of the current record, then the value in trussMap is updated, and the Changed flag is set to true (lines 17–19). The updated trussMap is sent to the neighboring nodes of $u$ (lines 20 and 21) after all the incident edges of $u$ with their updated trussness are obtained. The steps of the execution phase are repeated until the termination condition is met and the system stops. Finally, the stored values in trussMap are the trussness of the edges.

Termination mechanism. Several alternatives for termination conditions of the distributed computing system are avaliable^{[ 38 ]}. We use the barrier synchronization mechanism as the termination condition. If none of the nodes in the system updates trussMap in a round, that is, no active nodes are avaliable, then the system will stop, and the computation of trussness is complete.

Efficient message strategy. Two strategies that can further reduce the volume of passing messages are avaliable.

(1) The support of an edge is determined by the number of triangles where the edge is contained. Therefore, some edges may not be in any triangle and hence will not participate in any computing. Thus, the trussness of these edges will not be stored in the trussMap.

(2) The trussMap maintained by each node stores the estimated trussness of all incident edges. In the phase of sending messages in each round, the entire trussMap is sent to the neighbor nodes. This approach is substantially inefficient because only some items in trussMap may have changed. Theregore, we only need to send the updated items in trussMap to the neighboring nodes.

We then analyze the accuracy and efficiency of Algorithm 2.

Lemma 1. In Algorithm 1, the estimated trussness $\hat{t}(e)$ of $e$ is always higher than $t(e)$ .

Proof. Assuming $e=(u,v)$ and $t(e)=t$ , at least $t-2$ triangles contain $e$ , and the trussness of each edge in these triangles is no less than $t$ according to the definition of $k$ -truss. Assume $e^{\prime }$ is an edge that forms a triangle with $e$ , $t(e^{\prime })⩾t$ , and $\hat{t}(e)<t$ at time $t_1$ . This assumption indicates that the endpoint $u$ or $v$ updates $\hat{t}(e^{\prime })$ , which causes $\hat{t}(e^{\prime })<t$ at time $t_2$ . By analogy, the endpoints of $e^{\prime }$ update some estimated trussness of the edges that form the triangles with $e^{\prime }$ at $t_3$ . The inference leads to an infinite sequence of $t_1>t_2>t_3>\mathrm{\cdots }>t_i$ . However, this sequence has a loop that yields $t_i=t_1$ , which is a contradiction.

■

Lemma 2. Algorithm 1 ensures the convergence of the estimated trussness $\hat{t}(e)$ to $t(e)$ for $\forall e\in E$ .

Proof. In any round during the entire process, $\hat{t}(e)$ will only decrease and will be no less than $t(e)$ by Lemma 1. Therefore, we only need to prove that $\hat{t}(e)$ will eventually be equal to $t(e)$ for any edge $e$ . We set $\hat{t}(e)=sup(e)+2$ in the initialization phase and provide proof by induction on the values of $t(e)$ .

• $t(e)=2$ . In this case, $sup(e)=0$ , that is, $e$ is not in any triangles. $\hat{t}(e)=t(e)$ in the beginning of the distributed system.

• $t(e)=3$ . Assume that $\hat{t}(e)⩾4$ always holds. Therefore, each edge in at least two triangles has trussness no less than $4$ . Therefore, a subgraph that contains these edges is avaliable, and the support of each edge is larger than $2$ . The subgraph is a $4$ -truss, which is a contradiction.

• Induction step: suppose there is an edge $e$ such that $t(e)=k⩾4$ and $\hat{t}(e)⩾k+1$ forever constantly. Then, $l⩾k-2$ triangles contain $e$ and for each $e^{\prime }\in l\setminus \{e\}$ such that $t(e^{\prime })⩾k$ . According to Lemma 1, $\hat{t}(e^{\prime })⩾k+1$ by $\hat{t}(e)⩾k+1$ .

If $l=k-2$ , then $\hat{t}(e)$ will eventually decrease to $t(e)$ according to Property 1.

If $l⩾k-1$ , then $e$ is in at least $k-1$ triangles and $e^{\prime }\in l\setminus \{e\}$ such that $\hat{t}(e^{\prime })⩾k+1$ . Therefore, $t(e)=k+1$ according to the definition of $k$ -truss, which is a contradiction.

■

Theorem 1. The number of rounds of Algorithm 1 is bound by $2|E|+\underset{e\in E}{\sum }(sup(e)-t(e))$ .

Proof. As long as this distributed system is running, at least one edge will perform the update operation of estimated trussness. In the worst case, only one edge of the estimated trussness is updated in each round, and this edge only changes by 1. For an edge $e$ , the quantity by which its estimated trussness decreases from its initial value to its final value is $(sup(e)+2-t(e))$ . This quantity represents the update error of $e$ . Thus, the execution time is bound by the sum of update errors of all edges, which is $\underset{e\in E}{\sum }(sup(e)+2-t(e))=2|E|+\underset{e\in E}{\sum }(sup(e)-t(e))$ .

■

From the above lemmas and theorem, we derive the following Theorems regearding the time and information complexities of the distributed truss decomposition algorithm.

Theorem 2. Given a graph $G$ , the time complexity of Algorithm 1 to compute the trussness of edges is $O(m-t_{\min })$ , where $m$ is the number of edges in $G$ and $t_{\min }$ is the minimum trussness of the graph.

Proof. As the system is running, at least one edge whose estimated trussness will be updated in each round exists. This condition indicates that at least one minimum trussness must be determined in each round. After the trussness of all edges has been determined, the system requires one round of initialization and one round of deterministic termination. Hence, the number of rounds of the algorithm is no larger than $m-t_{\min }+2$ , and the time complexity is $O(m-t_{\min })$ .

■

Theorem 3 . Given a graph $G$ , the message complexity of Algorithm 1 to compute the trussness of edges is $O(\underset{e\in E}{\sum }sup(e))$ .

Proof. In the worst case, one of the endpoints of an edge $e$ receives at most $|sup(e)+2-t(e)|$ messages from the neighboring nodes. In whatever graph, the minimum value of trussness of edges is $2$ . Therefore, the number of messages of the algorithm is bound by $\underset{e\in E}{\sum }(sup(e)+sup(e^{\prime }))=2\underset{e\in E}{\sum }(sup(e))$ , and the message complexity is $O(\underset{e\in E}{\sum }sup(e))$ .

■

We propose our distributed truss decomposition algorithm in this section based on our distributed model. We first introduce two auxiliary indexes, namely adjMap and trussMap, which are based on the locality property of the $k$ -truss. We then introduce the procedure and analysis of the proposed algorithm, which is based on the two indexes.

The distributed model encounters the following two truss decomposition challenges.

• The most important metric for calculating the trussness is the support of edges, which is the initial value of trussness for edges. All neighboring nodes of both endpoints of the edge must be identified to calculate the support of an edge.

• Edges are virtual connections for communication between nodes. Thus, the value of support for each edge cannot exist on a nonexistent entity.

To address the above challenges, we calculate the support value of all neighboring edges by utilizing the node to store local topological information regarding its incident edges and two-hop neighboring nodes. Furthermore, the following property bears the calculation of the trussness applied to the support of the edges. The locality property is formally presented as follows.

Property 1 (Locality^{[ 25 ]}). Given a graph $G=(V,$ $E)$ , $\forall e\in E$ , $t(e)=k$ if and only if the following conditions are met.

(1) An edge subset $E_k\subset EN(e)$ such that $|E_k|=2(k-2)$ , edges in $E_k$ form total $(k-2)$ triangles with $e$ , and the trussness of each edge in $E_k$ is not less than $k$ .

(2) There is not a subset $E_{k+1}\subset EN(e)$ does not exist such that $E_{k+1}=2(k-1)$ , edges in $E_{k+1}$ form total $(k-1)$ triangles with $e$ , and the trussness of each edge in $E_{k+1}$ is not less than $k+1$ .

The property describes that if the trussness of an edge $e$ is equal to $k$ , then at least $(k-2)$ triangles contain $e$ and the trussness of each edge in these triangles is at least $k$ . Therefore, the trussness of an edge can be calculated from the trussness of the incident edges of the edge. More specifically, the trussness can be calculated from the trussness of the edges that form triangles with the edge.

We design two indexes according to the locality property to store the neighboring information for each node. For a node $u$ in our distributed system, the first index is adjMap, which is a list of key-value pairs used to store $2$ -hop adjacency nodes of $u$ . The keys of adjMap are the neighbor nodes of $u$ , and the value corresponding to each key is the linked list of neighboring nodes of the stored node by the key. The second index is trussMap, which stores the estimated trussness of $2$ -hop incident edges of a node $u$ . The trussness of the incident edges of $u$ is calculated and maintained by $u$ . Figure 3 shows an example of the adjMap and the trussMap for node 1 in Fig. 2 . In Fig. 3a , the keys of adjMap are maintained by node 1, and the values are received from neighboring nodes of node 1. Figure 3 shows the change of node 1 updating the trussMap after receiving messages from neighbors. The trussMap comprises two parts: one part is the trussness estimates of the incident edges of node 1 (this part is calculated and maintained by node 1 itself), and another part is the trussness estimates of the incident edges of node 1’s neighboring nodes (this part is kept by node1 receiving data from the neighboring nodes).

10.26599/TST.2022.9010019.F003 Fig. 32-hop auxiliary index for node 1 in Fig. 2.

In our distributed model, each node is responsible for computing and updating the estimated trussness of its incident edges by maintaining trussMap. Algorithm 1 shows the execution process of node $u$ . The proposed algorithm has two phases: the initialization and the execution phases.

In the initialization phase (lines 1–8), the adjacency nodes of $u$ exchange their adjMap values with $u$ to compute trussMap. The initially estimated trussness of an edge is the support of the edge plus $2$ (line 6). $u$ sends its trussMap to the neighboring nodes and sets the Changed flag to false to end the process (lines 7 and 8).

The execution phase is the process of iterative execution of the entire distributed system (lines 9–22). In each round of the execution phase, $u$ receives the trussness of incident edges to neighbor nodes (line 11). Thus, each node can receive the trussness of the 2-hop incident edges. Afterward, $u$ updates the trussness of incident edges through the locality property by the function ComputeTruss (line 16). This function then returns the maximum $k$ for which a value not less than $k-2$ exists in the counter, and the algorithm is shown in Algorithm 2. If the updated estimated trussness $t$ of the incident edges is smaller than the value of the current record, then the value in trussMap is updated, and the Changed flag is set to true (lines 17–19). The updated trussMap is sent to the neighboring nodes of $u$ (lines 20 and 21) after all the incident edges of $u$ with their updated trussness are obtained. The steps of the execution phase are repeated until the termination condition is met and the system stops. Finally, the stored values in trussMap are the trussness of the edges.

Termination mechanism. Several alternatives for termination conditions of the distributed computing system are avaliable^{[ 38 ]}. We use the barrier synchronization mechanism as the termination condition. If none of the nodes in the system updates trussMap in a round, that is, no active nodes are avaliable, then the system will stop, and the computation of trussness is complete.

Efficient message strategy. Two strategies that can further reduce the volume of passing messages are avaliable.

(1) The support of an edge is determined by the number of triangles where the edge is contained. Therefore, some edges may not be in any triangle and hence will not participate in any computing. Thus, the trussness of these edges will not be stored in the trussMap.

(2) The trussMap maintained by each node stores the estimated trussness of all incident edges. In the phase of sending messages in each round, the entire trussMap is sent to the neighbor nodes. This approach is substantially inefficient because only some items in trussMap may have changed. Theregore, we only need to send the updated items in trussMap to the neighboring nodes.

We then analyze the accuracy and efficiency of Algorithm 2.

Lemma 1. In Algorithm 1, the estimated trussness $\hat{t}(e)$ of $e$ is always higher than $t(e)$ .

Proof. Assuming $e=(u,v)$ and $t(e)=t$ , at least $t-2$ triangles contain $e$ , and the trussness of each edge in these triangles is no less than $t$ according to the definition of $k$ -truss. Assume $e^{\prime }$ is an edge that forms a triangle with $e$ , $t(e^{\prime })⩾t$ , and $\hat{t}(e)<t$ at time $t_1$ . This assumption indicates that the endpoint $u$ or $v$ updates $\hat{t}(e^{\prime })$ , which causes $\hat{t}(e^{\prime })<t$ at time $t_2$ . By analogy, the endpoints of $e^{\prime }$ update some estimated trussness of the edges that form the triangles with $e^{\prime }$ at $t_3$ . The inference leads to an infinite sequence of $t_1>t_2>t_3>\mathrm{\cdots }>t_i$ . However, this sequence has a loop that yields $t_i=t_1$ , which is a contradiction.

■

Lemma 2. Algorithm 1 ensures the convergence of the estimated trussness $\hat{t}(e)$ to $t(e)$ for $\forall e\in E$ .

Proof. In any round during the entire process, $\hat{t}(e)$ will only decrease and will be no less than $t(e)$ by Lemma 1. Therefore, we only need to prove that $\hat{t}(e)$ will eventually be equal to $t(e)$ for any edge $e$ . We set $\hat{t}(e)=sup(e)+2$ in the initialization phase and provide proof by induction on the values of $t(e)$ .

• $t(e)=2$ . In this case, $sup(e)=0$ , that is, $e$ is not in any triangles. $\hat{t}(e)=t(e)$ in the beginning of the distributed system.

• $t(e)=3$ . Assume that $\hat{t}(e)⩾4$ always holds. Therefore, each edge in at least two triangles has trussness no less than $4$ . Therefore, a subgraph that contains these edges is avaliable, and the support of each edge is larger than $2$ . The subgraph is a $4$ -truss, which is a contradiction.

• Induction step: suppose there is an edge $e$ such that $t(e)=k⩾4$ and $\hat{t}(e)⩾k+1$ forever constantly. Then, $l⩾k-2$ triangles contain $e$ and for each $e^{\prime }\in l\setminus \{e\}$ such that $t(e^{\prime })⩾k$ . According to Lemma 1, $\hat{t}(e^{\prime })⩾k+1$ by $\hat{t}(e)⩾k+1$ .

If $l=k-2$ , then $\hat{t}(e)$ will eventually decrease to $t(e)$ according to Property 1.

If $l⩾k-1$ , then $e$ is in at least $k-1$ triangles and $e^{\prime }\in l\setminus \{e\}$ such that $\hat{t}(e^{\prime })⩾k+1$ . Therefore, $t(e)=k+1$ according to the definition of $k$ -truss, which is a contradiction.

■

Theorem 1. The number of rounds of Algorithm 1 is bound by $2|E|+\underset{e\in E}{\sum }(sup(e)-t(e))$ .

Proof. As long as this distributed system is running, at least one edge will perform the update operation of estimated trussness. In the worst case, only one edge of the estimated trussness is updated in each round, and this edge only changes by 1. For an edge $e$ , the quantity by which its estimated trussness decreases from its initial value to its final value is $(sup(e)+2-t(e))$ . This quantity represents the update error of $e$ . Thus, the execution time is bound by the sum of update errors of all edges, which is $\underset{e\in E}{\sum }(sup(e)+2-t(e))=2|E|+\underset{e\in E}{\sum }(sup(e)-t(e))$ .

■

From the above lemmas and theorem, we derive the following Theorems regearding the time and information complexities of the distributed truss decomposition algorithm.

Theorem 2. Given a graph $G$ , the time complexity of Algorithm 1 to compute the trussness of edges is $O(m-t_{\min })$ , where $m$ is the number of edges in $G$ and $t_{\min }$ is the minimum trussness of the graph.

Proof. As the system is running, at least one edge whose estimated trussness will be updated in each round exists. This condition indicates that at least one minimum trussness must be determined in each round. After the trussness of all edges has been determined, the system requires one round of initialization and one round of deterministic termination. Hence, the number of rounds of the algorithm is no larger than $m-t_{\min }+2$ , and the time complexity is $O(m-t_{\min })$ .

■

Theorem 3 . Given a graph $G$ , the message complexity of Algorithm 1 to compute the trussness of edges is $O(\underset{e\in E}{\sum }sup(e))$ .

Proof. In the worst case, one of the endpoints of an edge $e$ receives at most $|sup(e)+2-t(e)|$ messages from the neighboring nodes. In whatever graph, the minimum value of trussness of edges is $2$ . Therefore, the number of messages of the algorithm is bound by $\underset{e\in E}{\sum }(sup(e)+sup(e^{\prime }))=2\underset{e\in E}{\sum }(sup(e))$ , and the message complexity is $O(\underset{e\in E}{\sum }sup(e))$ .

■

We first introduce the properties related to the trussness update of the insertion/deletion of an edge. The distributed algorithms for truss maintenance are then presented.

At most, one triangle is formed for destroyed after the insertion/deletion of an edge. The support of an edge is the number of triangles contained in that edge, and the trussness of an edge is related to the minimum support of the surrounding edges. The insertion or deletion of an edge may cause an increase or decrease in the trussness of other edges by at most 1, which has been proven in Ref. [ 15 ]. A new graph $G^{\prime }$ is formally generated after inserting $e_0$ in G. The increase in the trussness of edge $e$ in $G^{\prime }$ may be performed in two ways: (1) $e$ , $e_0$ , and another edge form a new triangle, which increases the support of $e$ ; (2) the trussness of some edges of the triangle in which $e$ is located increases by one. After deleting $e_0$ in $G$ , the trussness of edge $e$ in the newly generated graph $G^{\prime }$ may decrease in two ways: (1) $e$ and $e_0$ belong to the same triangle in $G$ , and the deletion of $e_0$ reduces the support of $e$ ; (2) the trussness of some edges in the triangle where $e$ is located decreases by one.

For the trussness of the inserted edge $e_0=(u,v)$ , we set the bounds for $e_0$ based on the trussness of the edges before the insertion of $e_0$ . Assume $t_{\text{LB}}(e_0)$ is the lower bound of $t(e_0)$ and $t_{\text{UB}}(e_0)$ is the upper bound of $t(e)$ . According to the definition of $k$ -truss,

(3) $$t_{\text{LB}}(e_0)=\arg \underset{k⩾2}{\max }\{|\{w|t_{\min }^w⩾k\}|⩾(k-2)\}$$

where $w\in N_G(u)\cap N_G(v)$ . The trussness of edges forming triangles with $e_0$ will increase by at most $1$ . Therefore, we can deduce that

(4) $$t_{\text{UB}}(e_0)-t_{\text{LB}}(e_0)⩽1$$

The above can be formally summarized as the following property^{[ 37 ]}.

Property. If inserting edge $e_0=(u,v)$ to $G=(V,E)$ , then $e_1,e_2\in E$ may increase trussness by $1$ , where $t(e_1)=k<t_{\text{UB}}(e_0)$ and $e_2$ is $k$ -triangle connected with $e_1$ . If deleting edge $e_0$ from $G=(V,E)$ , then $e_1,e_2\in E\setminus e_0$ may decrease trussness by $1$ , where $t(e_1)=k⩽t(e_0)$ and $e_2$ is $k$ -triangle connected with $e_1$ .

An example of inserting edges is shown in Fig. 2 , which demonstrates the formation of new triangles after edge insertion. The trussness of part of the edges may increase due to the new triangles.

After an edge $e_0=(u,v)$ is inserted, the two endpoints $u$ and $v$ initially update their adjMap and send the updated adjMap to their neighbors. Then, the two nodes both calculate the upper bound of $e_0$ (i.e., $t_{\text{UB}}(e_0)$ ). An edge $e$ will be marked if $e$ forms a triangle with $e_0$ and $t(e)<t_{\text{UB}}(e_0)$ , and these edges will also be marked if they are $k$ -triangle connected with $e$ . All marked edges are potential edges whose trussness may increase by $1$ . Therefore, we increase the trussness estimates in the trussMap of these potential edges by $1$ , and perform the same process as Algorithm 1 for the system until the convergence of the trussness estimates of all edges to the final stable values.

We classify the endpoints of edges that may update trussness into two categories. (1) The nodes are the endpoints of the inserted edges, denoted by promoter node set; (2) the nodes are the endpoints of those edges that are $k$ -triangle connected to the inserted edges, denoted by spread node set. Each node in the promoter node set is a promoter node, and each node in the spread node set is a spread node.

The promoter nodes are responsible for computing the upper bound trussness of inserting edges and recording edges that may be affected. Meanwhile, the spread nodes are responsible for sending messages to the nodes where the requirements are met. We first describe the distributed algorithm for inserting an edge, and then briefly discuss the algorithm for deleting one edge. Figure 4 shows an example of promoter nodes and spread nodes. After inserting edge $(2,6)$ in the graph, nodes $2$ and $6$ become promoter nodes, and the initial trussness of the newly inserted edge $(2,6)$ is $3$ . Neighboring nodes connected to nodes $2$ and $6$ by trussness not larger than $3$ become spread nodes.

10.26599/TST.2022.9010019.F004 Fig. 4An example of promoter nodes and spread nodes.

Distributed truss maintenance with one-edge insertion. In our algorithm, each node maintains two auxiliary sets: updated edge set (UES) is a set that stores the neighboring edges of the node, and the trussness of these neighboring edges may change; updated node set (UNS) is a set of nodes that stores the nodes adjacent to this node and the trussMap of these nodes may change.

For the promoter node, the edges stored in its UES are all the edges whose trussness is lower than the upper bound of the inserted edge’s trussness; its UNS stores another endpoint of those edges in its UES. The edges stored in UES are those whose trussness may increase by $1$ . We reinitialize the trussness estimates of these edges to their current trussness plus $1$ . All nodes in the system perform the same process as in Algorithm 1 after the reinitialization is completed. The initialization pseudocodes of the promoter and spread nodes are shown in Algorithms 3 and 4, respectively.

For a promoter node $u$ , the procedure is divided into two parts, prepare phase (lines 1–11 in Algorithm 3) and propose phase (lines 12–16 in Algorithm 3). Due to the insertion of a new edge $e_0$ , the adjMap of $u$ is first updated, and then compute the upper bound of $e_0$ (lines 2–5 in Algorithm 3). Each edge that forms a triangle with $e_0$ is then traversed: if the edge satisfies the condition for possible updates, then the edge is added to $UES$ , and another endpoint of the edge is added to $UNS$ (lines 6–11 in Algorithm 3). In the Propose phase, the trussness of each edge in $UES$ plus one, and each node in $UNS$ spreads the Change signal (lines 12–16 in Algorithm 3).

For a spread node $p$ , the procedure is still divided into two parts. In prepare phase, the edge whose trussness may change (lines 3 and 4 in Algorithm 4) is first determined. Each edge that forms a triangle with the potential edge and has the same trussness as the potential edge is then added to the $UES$ (lines 5–11 in Algorithm 4). The propose phase of the spread node is the same as the promoter node, and the difference lies in the additional trussness of edges by 1 that no longer changes.

Analysis. The reinitialization stage ends when no node receives UES. The time complexity of the re-initialization stage depends on the diameter of the induced subgraph generated by UNS. The induced graph generated by UNS is denoted as $H$ , which is a $k$ -truss. The diameter of a connected $k$ -truss with $n$ nodes is not greater than $[\frac{2n-2}{k}]$ ^{[ 8 ]}. As shown in Ref. [ 9 ], for a graph $G(V,E)$ and a node set $Q\subset V$ , we have $dis{t}_G(G,Q)⩽diam(G)⩽2dis{t}_G(G,Q)$ , where $dis{t}_G(u,v)$ is the length of the shortest path between $u$ and $v$ in $G$ and $diam(G)={\max }_{u,v\in G}\{dis{t}_G(u,v)\}$ is the diameter of graph $G$ . The time complexity of reinitialization stage is $O(diam(H))$ . Algorithm 1 will be terminated for two rounds of the execution phase in most cases (one round ensures that all nodes will not update trussMap) after resetting the estimated trussness of edges.

Distributed truss maintenance with one-edge deletion. The algorithm for a single edge deletion is simpler than the insertion case. After an edge is deleted, the two endpoints of this edge first update their adjMap and remove the nonexistent items from the trussMap due to the change in the graph structure. The execution phase of Algorithm 1 is then performed, and the estimated trussness of edges will converge to the real trussness. In this case, only nodes in UNS will participate in the calculation, and only a few rounds will be needed in most cases.

We do not need to label nodes in $UNS$ simliar to the insertion scenario due to the absence of potential edges to determine. Hence, the distributed truss maintenance algorithm for edge deletion is efficient and fast.

We first introduce the properties related to the trussness update of the insertion/deletion of an edge. The distributed algorithms for truss maintenance are then presented.

At most, one triangle is formed for destroyed after the insertion/deletion of an edge. The support of an edge is the number of triangles contained in that edge, and the trussness of an edge is related to the minimum support of the surrounding edges. The insertion or deletion of an edge may cause an increase or decrease in the trussness of other edges by at most 1, which has been proven in Ref. [ 15 ]. A new graph $G^{\prime }$ is formally generated after inserting $e_0$ in G. The increase in the trussness of edge $e$ in $G^{\prime }$ may be performed in two ways: (1) $e$ , $e_0$ , and another edge form a new triangle, which increases the support of $e$ ; (2) the trussness of some edges of the triangle in which $e$ is located increases by one. After deleting $e_0$ in $G$ , the trussness of edge $e$ in the newly generated graph $G^{\prime }$ may decrease in two ways: (1) $e$ and $e_0$ belong to the same triangle in $G$ , and the deletion of $e_0$ reduces the support of $e$ ; (2) the trussness of some edges in the triangle where $e$ is located decreases by one.

For the trussness of the inserted edge $e_0=(u,v)$ , we set the bounds for $e_0$ based on the trussness of the edges before the insertion of $e_0$ . Assume $t_{\text{LB}}(e_0)$ is the lower bound of $t(e_0)$ and $t_{\text{UB}}(e_0)$ is the upper bound of $t(e)$ . According to the definition of $k$ -truss,

(3) $$t_{\text{LB}}(e_0)=\arg \underset{k⩾2}{\max }\{|\{w|t_{\min }^w⩾k\}|⩾(k-2)\}$$

where $w\in N_G(u)\cap N_G(v)$ . The trussness of edges forming triangles with $e_0$ will increase by at most $1$ . Therefore, we can deduce that

(4) $$t_{\text{UB}}(e_0)-t_{\text{LB}}(e_0)⩽1$$

The above can be formally summarized as the following property^{[ 37 ]}.

Property. If inserting edge $e_0=(u,v)$ to $G=(V,E)$ , then $e_1,e_2\in E$ may increase trussness by $1$ , where $t(e_1)=k<t_{\text{UB}}(e_0)$ and $e_2$ is $k$ -triangle connected with $e_1$ . If deleting edge $e_0$ from $G=(V,E)$ , then $e_1,e_2\in E\setminus e_0$ may decrease trussness by $1$ , where $t(e_1)=k⩽t(e_0)$ and $e_2$ is $k$ -triangle connected with $e_1$ .

An example of inserting edges is shown in Fig. 2 , which demonstrates the formation of new triangles after edge insertion. The trussness of part of the edges may increase due to the new triangles.

After an edge $e_0=(u,v)$ is inserted, the two endpoints $u$ and $v$ initially update their adjMap and send the updated adjMap to their neighbors. Then, the two nodes both calculate the upper bound of $e_0$ (i.e., $t_{\text{UB}}(e_0)$ ). An edge $e$ will be marked if $e$ forms a triangle with $e_0$ and $t(e)<t_{\text{UB}}(e_0)$ , and these edges will also be marked if they are $k$ -triangle connected with $e$ . All marked edges are potential edges whose trussness may increase by $1$ . Therefore, we increase the trussness estimates in the trussMap of these potential edges by $1$ , and perform the same process as Algorithm 1 for the system until the convergence of the trussness estimates of all edges to the final stable values.

We classify the endpoints of edges that may update trussness into two categories. (1) The nodes are the endpoints of the inserted edges, denoted by promoter node set; (2) the nodes are the endpoints of those edges that are $k$ -triangle connected to the inserted edges, denoted by spread node set. Each node in the promoter node set is a promoter node, and each node in the spread node set is a spread node.

The promoter nodes are responsible for computing the upper bound trussness of inserting edges and recording edges that may be affected. Meanwhile, the spread nodes are responsible for sending messages to the nodes where the requirements are met. We first describe the distributed algorithm for inserting an edge, and then briefly discuss the algorithm for deleting one edge. Figure 4 shows an example of promoter nodes and spread nodes. After inserting edge $(2,6)$ in the graph, nodes $2$ and $6$ become promoter nodes, and the initial trussness of the newly inserted edge $(2,6)$ is $3$ . Neighboring nodes connected to nodes $2$ and $6$ by trussness not larger than $3$ become spread nodes.

10.26599/TST.2022.9010019.F004 Fig. 4An example of promoter nodes and spread nodes.

Distributed truss maintenance with one-edge insertion. In our algorithm, each node maintains two auxiliary sets: updated edge set (UES) is a set that stores the neighboring edges of the node, and the trussness of these neighboring edges may change; updated node set (UNS) is a set of nodes that stores the nodes adjacent to this node and the trussMap of these nodes may change.

For the promoter node, the edges stored in its UES are all the edges whose trussness is lower than the upper bound of the inserted edge’s trussness; its UNS stores another endpoint of those edges in its UES. The edges stored in UES are those whose trussness may increase by $1$ . We reinitialize the trussness estimates of these edges to their current trussness plus $1$ . All nodes in the system perform the same process as in Algorithm 1 after the reinitialization is completed. The initialization pseudocodes of the promoter and spread nodes are shown in Algorithms 3 and 4, respectively.

For a promoter node $u$ , the procedure is divided into two parts, prepare phase (lines 1–11 in Algorithm 3) and propose phase (lines 12–16 in Algorithm 3). Due to the insertion of a new edge $e_0$ , the adjMap of $u$ is first updated, and then compute the upper bound of $e_0$ (lines 2–5 in Algorithm 3). Each edge that forms a triangle with $e_0$ is then traversed: if the edge satisfies the condition for possible updates, then the edge is added to $UES$ , and another endpoint of the edge is added to $UNS$ (lines 6–11 in Algorithm 3). In the Propose phase, the trussness of each edge in $UES$ plus one, and each node in $UNS$ spreads the Change signal (lines 12–16 in Algorithm 3).

For a spread node $p$ , the procedure is still divided into two parts. In prepare phase, the edge whose trussness may change (lines 3 and 4 in Algorithm 4) is first determined. Each edge that forms a triangle with the potential edge and has the same trussness as the potential edge is then added to the $UES$ (lines 5–11 in Algorithm 4). The propose phase of the spread node is the same as the promoter node, and the difference lies in the additional trussness of edges by 1 that no longer changes.

Analysis. The reinitialization stage ends when no node receives UES. The time complexity of the re-initialization stage depends on the diameter of the induced subgraph generated by UNS. The induced graph generated by UNS is denoted as $H$ , which is a $k$ -truss. The diameter of a connected $k$ -truss with $n$ nodes is not greater than $[\frac{2n-2}{k}]$ ^{[ 8 ]}. As shown in Ref. [ 9 ], for a graph $G(V,E)$ and a node set $Q\subset V$ , we have $dis{t}_G(G,Q)⩽diam(G)⩽2dis{t}_G(G,Q)$ , where $dis{t}_G(u,v)$ is the length of the shortest path between $u$ and $v$ in $G$ and $diam(G)={\max }_{u,v\in G}\{dis{t}_G(u,v)\}$ is the diameter of graph $G$ . The time complexity of reinitialization stage is $O(diam(H))$ . Algorithm 1 will be terminated for two rounds of the execution phase in most cases (one round ensures that all nodes will not update trussMap) after resetting the estimated trussness of edges.

Distributed truss maintenance with one-edge deletion. The algorithm for a single edge deletion is simpler than the insertion case. After an edge is deleted, the two endpoints of this edge first update their adjMap and remove the nonexistent items from the trussMap due to the change in the graph structure. The execution phase of Algorithm 1 is then performed, and the estimated trussness of edges will converge to the real trussness. In this case, only nodes in UNS will participate in the calculation, and only a few rounds will be needed in most cases.

We do not need to label nodes in $UNS$ simliar to the insertion scenario due to the absence of potential edges to determine. Hence, the distributed truss maintenance algorithm for edge deletion is efficient and fast.

In this section, we study the truss maintenance after the insertion/deletion of multiple edges. The main challenges of maintaining trussness in the case of multiple edges dynamics remain as follows: determining which edges change in trussness and by how much. Algorithms for the case of a single edge dynamic can be used iteratively when multiple edges are inserted/deleted. However, we can further optimize the algorithms when inserting/removing multiple edges for efficient computation.

Insertion of multiple edges. Algorithm 5 shows the procedure of truss maintenance after the insertion of multiple edges. Suppose the set of inserted edges is $\text{Δ}E$ . For each edge $e_0\in \text{Δ}E$ , Algorithms 3 and 4 are first executed after $e_0$ is inserted (lines 1–5). After all edges in $\text{Δ}E$ are inserted, the execution phase of Algorithm 1 is executed until termination (line 6).

Deletion of multiple edges. Algorithm 5 shows the procedure of truss maintenance after the deletion of multiple edges. Suppose the set of deleted edges is $\text{Δ}E\subset E$ . The adjMap and trussMap of all nodes are directly updated after deleting all the edges in $\text{Δ}E$ . That is, each node deletes the nonexistent neighbors, and then sends the adjacency list to the remaining neighbors. Afterward, each node deletes the item whose key does not exist in the trussMap and then sends the trussMap of incident edges to the neighbors. Finally, nodes perform the execution phase of Algorithm 1 until termination. In the case of deleting numerous edges, the endpoints of each deleted edge can recalculate the value of $sup(e)+2$ of the incident edges. An endpoint $u$ updates $\mathrm{trussMap}[e]=\min \{sup(e)+2,\mathrm{trussMap}[e]\}$ if $e$ is an incident edge of $u$ . Given a large number of deleted edges and broken triangles, the value of $sup(e)+2$ for $e\in G\backslash \text{Δ}E$ may even be smaller than $t(e)$ . Storing the smaller values in trussMap enables the rapid termination of the algorithm.

Analysis. The analysis of previous sections indicate that the time complexity of single edge insertion is $O(diam(H))$ . Thus the time complexity for multiple edges insertion is $O(diam(G)\cdot |\text{Δ}E|)$ , where $diam(G)$ is the diameter of $G$ .