Core Decomposition and Maintenance in Bipartite Graphs

In this section, we first solve the core decomposition problem. Specifically, by adapting the algorithm for $(\alpha ,\beta )$ -core computation given in Ref. [ 9 ], we present an algorithm for core decomposition in bipartite graphs in Algorithm 1.

For a bipartite graph $G=(U,V,E)$ , the value of $\alpha$ ranges from 1 to ${\mathrm{deg}}_{\max }(U)$ , since the $\alpha$ value represents the degrees of vertices in $U$ (Line 1). For each $\alpha$ , we calculate the corresponding ${\mathrm{core}}_{\alpha }(*)$ for all vertices. For each fixed $\alpha$ , the vertices in $U$ whose degrees are less than $\alpha$ are removed along with their adjacent edges. The core numbers of these vertices are set as 0 (Lines 3–5). Then we need to compute the core numbers of rest vertices in $V$ and $U$ , respectively.

In the remaining graph $G^{\prime }$ , the vertices in $V$ are handled in the order of increasing degrees. Let the minimum degree in $V(G^{\prime })$ be ${\beta }_{\min }$ , all vertices in $V$ whose degrees are not greater than ${\beta }_{\min }$ and their adjacent edges are deleted. The core numbers of these vertices are set as ${\beta }_{\min }$ (Lines 7–10). For the vertices in $U$ , once there is a vertex $u$ whose degree is less than $\alpha$ , then we set ${\mathrm{core}}_{\alpha }(u)$ = ${\beta }_{\min }$ and remove $u$ and its adjacent edges from $G^{\prime }$ , since $u$ cannot be in any $(\alpha ,\beta )$ -core with $\beta >{\beta }_{\min }$ (Lines 11–13). When $G^{\prime }$ becomes empty, i.e., all the vertices have been processed, then we obtain the core number of each vertex under the fixed $\alpha$ . While traversing through each possible value of $\alpha$ , the core number of each vertex under each possible $\alpha$ can be computed.

The correctness of Algorithm 1 can be easily obtained by the definition of $\alpha$ -core number. We next show the efficiency of the algorithm.

Theorem 1 Given a bipartite graph $G=(U,V,E)$ , the time needed for core decomposition is $O((N+M)\times {\mathrm{deg}}_{\max })$ and the space required to store the core numbers of vertices is $O(N\times {\mathrm{deg}}_{\max })$ , where $N$ , $M$ , and ${\mathrm{deg}}_{\max }=\min \{{\mathrm{deg}}_{\max }(U),{\mathrm{deg}}_{\max }(V)\}$ are the total number of vertices, the total number of edges, and the smaller value between maximum degree of vertices in $U$ and maximum degree of vertices in $V$ , respectively.

Proof Each vertex and each edge only need to be traversed once, and hence the time for core decomposition is $O(N+M)$ . To be more efficient, we can interchange $U$ and $V$ when ${\mathrm{deg}}_{\max }(U)$ $>$ ${\mathrm{deg}}_{\max }(V)$ , then $\alpha$ can be at most ${\mathrm{deg}}_{\max }$ and we will get the time complexity of the algorithm. As for the space required, for each vertex we need to store core numbers for at most ${\mathrm{deg}}_{\max }$ values, and hence the total space used is $O(N\times {\mathrm{deg}}_{\max })$ .

In reality, the graph may change over time, hence the core numbers of vertices have to be updated after the graph changes. Intuitively, we can execute Algorithm 1 to recompute the core numbers of all vertices. However, though the computation time of core numbers for each fixed $\alpha$ is only linear, it is still unacceptable considering that the graph may have billions of vertices and edges. Hence, we next turn our attention to the core maintenance problem, i.e., updating the core numbers of vertices by avoiding recomputations. We will first present the scenario of a single edge insertion/deletion, and then propose a batch processing approach to further improve the efficiency of core maintenance.

Algorithm. The detailed algorithm to maintain the core number of each vertex after inserting an edge is given in Algorithm 2. After inserting $(u,v)$ into $G$ , it iterates over all values of $\alpha$ from 1 to ${\mathrm{deg}}_{G^{\prime }}(u)$ , since the largest value of $\alpha$ that $u$ can have in an $(\alpha ,\beta )$ -core is its own degree (Lines 1 and 2). We set $Q$ and $C$ to preserve the vertices to be checked and the vertices whose core numbers might increase, respectively (Line 3). To prevent repetitive processing of a vertex, we set $\mathrm{visited}[]$ to mark the vertices that have been visited (Line 4). For each possible $\alpha$ , we aim to find the vertices in the graph whose core numbers change after inserting an edge and then increase their core numbers by 1.

According to Lemma 1, we need to compute the pre- ${\mathrm{core}}_{\alpha }(u)$ , to make sure that ${\mathrm{core}}_{\alpha }(u)$ changes by at most 1 (Line 5). We will set $r$ be the vertex with the smaller core number between $u$ and $v$ and add it to $Q$ (Lines 6–8). When a vertex $x$ is ejected from $Q$ , we insert it to $C$ and set $\mathrm{visited}[x]$ as true (Lines 9–11). For each vertex $x$ in $Q$ , we are going to check its each neighbor $y$ , to see if $u$ ’s core number is likely to increase. If ${\mathrm{core}}_{\alpha }(y)>k$ or $y$ is in $C$ , then $y$ must support the increase of $\mathrm{core}(x)$ , because $y$ is already in an $(\alpha ,k+1)$ -core or ${\mathrm{core}}_{\alpha }(y)$ is supposed to increase from $k$ to $k+1$ . Besides that, if ${\mathrm{core}}_{\alpha }(y)=k$ and is not visited, then $y$ is also likely to help ${\mathrm{core}}_{\alpha }(x)$ to increase. So when the neighbor $y$ of $x$ satisfies one of these two conditions, $\mathrm{SN}(x)$ increases by 1 (Lines 12–16). When $\mathrm{SN}(x)$ is larger than the threshold $k$ , it means that it is possible for ${\mathrm{core}}_{\alpha }(x)$ to increase. Based on Lemma 2, each neighbor $y$ of $x$ with ${\mathrm{core}}_{\alpha }(y)$ = ${\mathrm{core}}_{\alpha }(x)$ and not visited is pushed into $Q$ for further checking (Lines 17 and 18). Once $\mathrm{SN}(x)$ is not enough to support the increase in the core number of $x$ , the procedure DfsDelete, which is DFS process, is invoked to delete the vertices from $C$ that cannot increase their core numbers (Lines 19 and 20). While $Q$ becomes empty, we have dealt with all the vertices whose core number might change. Finally, all the vertices in $C$ that have not been deleted will increase their core numbers by 1 (Lines 21 and 22).

The procedure DfsDelete removes the vertex $x$ from $C$ , since it does not satisfy the increasing condition (Line 25). For each neighbor $w$ of $x$ , if it is in $C$ and $\mathrm{core}(w)=\mathrm{core}(x)$ , we will reduce the $\mathrm{SN}(w)$ by 1, since $y$ has lost a neighbor $x$ to support its core number increase (Lines 26–28). When $w$ does not have enough neighbors to hold its core number increase, DfsDelete will be invoked again to recursively remove $w$ (Lines 29 and 30).

Performance analysis. We will analyze the correctness and efficiency of Algorithm 2. Firstly, some notations are defined, which will be used in measuring the time complexity of the algorithm.

When an edge $e=(u,v)$ is inserted into the graph $G=(U,V,E)$ ,   for each $\alpha$ ,   let $U_{\alpha }^1$ and $V_{\alpha }^1$ be the set of vertices whose core numbers are equal to ${\mathrm{core}}_{\alpha }(e)$ in $U$ and $V$ , respectively, where ${\mathrm{core}}_{\alpha }(e)=\min \{{\mathrm{core}}_{\alpha }(u),$ ${\mathrm{core}}_{\alpha }(v)\}$ . Let $U_I={\max }_{1⩽\alpha ⩽{\mathrm{deg}}_{G^{\prime }}(u)}{U}_{\alpha }^1$ and $V_I=$ ${\max }_{1⩽\alpha ⩽{\mathrm{deg}}_{G^{\prime }}(v)}{V}_{\alpha }^1$ . $E_{\alpha }^1$ is the set of edges in the subgraph induced by $U_{\alpha }^1$ to $V_{\alpha }^1$ . Let $E_I=$ ${\max }_{1⩽\alpha ⩽{\mathrm{deg}}_{G^{\prime }}(u)}{E}_{\alpha }^1$ .

Let $N_U^{\alpha }={\max }_{u_i\in U_{\alpha }^1}$ $\{{\mathrm{SN}}_0(u_i)-\alpha ,0\}$ , where ${\mathrm{SN}}_0(u_i)$ denotes the SN value of $u_i$ when $u_i$ is first processed. Let $N_U$ = ${\max }_{1⩽\alpha ⩽{\mathrm{deg}}_{G^{\prime }}(u)}{N}_U^{\alpha }$ . Similarly, we define $N_V^{\alpha }={\max }_{v_i\in V_{\alpha }^1}\{{\mathrm{SN}}_0(v_i)-{\mathrm{core}}_{\alpha },0\}$ and $N_V={\max }_{1⩽\alpha ⩽{\mathrm{deg}}_{G^{\prime }}(u)}{N}_V^{\alpha }$ .

Theorem 2 When inserting an edge $e=(u,v)$ into graph $G$ , Algorithm 2 can correctly update the core numbers of all vertices and the time complexity is $O(de{g}_{G^{\prime }}(u)\times (E_I+U_I\times N_U+V_I\times N_V))$ .

Proof For each $\alpha$ , Algorithm 2 first finds the vertices whose core numbers change and then increases their core numbers by 1. In the algorithm, the core numbers of $u$ and $v$ are compared and the one with smaller core number is labeled as $r$ . The algorithm traverses from $r$ and pushes all vertices $w$ with ${\mathrm{core}}_{\alpha }(w)$ = ${\mathrm{core}}_{\alpha }(r)$ that are reachable from $r$ through a $C$ -path to $Q$ for further identification. According to Lemma 2, only those vertices may change their core numbers.

If ${\mathrm{core}}_{\alpha }(w)$ = ${\mathrm{core}}_{\alpha }(r)$ = $k$ and ${\mathrm{core}}_{\alpha }(w)$ increases after insertion, then $w$ must satisfy one of the following conditions: ( $1$ ) $w$ has a new neighbor whose core numbers are at least $k+1$ . ( $2$ ) Some neighbors of $w$ have their core numbers increased from $k$ to $k+1$ . In the algorithm, $\mathrm{SN}(w)$ records the number of these neighbors that support $w$ ’s core number increase. If $\mathrm{SN}(w)⩽{\mathrm{core}}_{\alpha }(w)$ , it is obvious that $w$ ’s core number will not increase. Once a vertex is identified not to change its core number, the SN values of other vertices are updated by invoking DfsDelete. After all the vertices whose core numbers might change have been processed, the subgraph induced by the vertices in $C$ that are not deleted constitutes an $(\alpha ,k+1)$ -core, as the SN value of these vertices is at least $k+1$ . Then by Lemma 1, all these vertices will increase the core number by 1. Hence, the algorithm can correctly update the core numbers of vertices.

Next, we analyze the time complexity. Firstly, there are ${\mathrm{deg}}_{G^{\prime }}(u)$ iterations in the algorithm execution. For each iteration, since only the vertices $w$ with $\mathrm{core}(w)=k$ are reachable from $r$ through a $C$ -path, and will be processed, so the number of vertices and edges that the algorithm visits are at most $U_I+V_I$ and $E_I$ , respectively. For each vertex, except for the first calculation of the SN value when ejected from $Q$ , the subsequent visits will decrease its SN value by 1. Therefore, the vertex $u\in U$ $(v\in V)$ can be visited at most $N_U^{\alpha }$ ( $N_V^{\alpha }$ ) times for a certain $\alpha$ , since it will be removed when its $SN$ is smaller than $\alpha$ $({\mathrm{core}}_{\alpha })$ . Then we can see that the vertex $u\in U$ $(v\in V)$ will be visited at most $N_U$ ( $N_V$ ) times in any iteration. To sum up, the time complexity of Algorithm 2 can be obtained.

Example 2 Here is an example to illustrate the execution of Algorithm 2 in Fig. 1 at $\alpha =2$ . We first insert $(u_2,v_2)$ into the graph and compute pre- $\mathrm{core}(u_2)=$ $3$ and $k=3$ . Since $\mathrm{core}(u_2)=\mathrm{core}(v_2)$ , without loss of generality, let $r=u_2$ . We push $u_2$ into $Q$ , and then set $\mathrm{visited}[u_2]=\mathrm{true}$ to avoid repeated visits. We can easily get that $\mathrm{SN}(u_2)=2$ , because the core numbers of its neighbors $v_2$ and $v_3$ are both 3 and not visited. Since $\mathrm{SN}(u_2)⩾\alpha$ and $\mathrm{core}(v_2)=\mathrm{core}(v_3)=k$ , we will next push $v_2$ and $v_3$ to $Q$ . As for $v_2$ , it can be obtained that $\mathrm{SN}(v_2)=4>k$ , so $v_2$ will not be deleted, and we are going to process $v_2$ ’s neighbors. When all the vertices in $Q$ are processed, we find that the vertices that are still in $C$ are $\{u_2,v_2,u_3,v_3,u_4,u_5\}$ . As a result, we increase their core numbers by 1, to give the value 4 and Algorithm 2 terminates.

Similar to Algorithm 2 of core maintainance after single-edge insertion, we here give the core maintenance algorithm after deleting an edge.

Algorithm. The detailed algorithm to update the core number of each vertex after removing an edge is given in Algorithm 3. After deleting $(u,v)$ from $G$ , it iterates over all possible values of $\alpha$ from 1 to ${\text{𝑑𝑒𝑔}}_{G}u$ , since the largest value of $\alpha$ can affect the $(\alpha ,\beta )$ -core while deleting edge $(u,v)$ is the degree of $u$ in $G$ (Lines 1 and 2).

In each iteration of $\alpha$ , the algorithm process is similar to Algorithm 2. The difference is that it compares ${\text{𝑐𝑜𝑟𝑒}}_{\alpha }(u)$ and ${\text{𝑐𝑜𝑟𝑒}}_{\alpha }(v)$ to determine $r$ instead of computing pre- ${\text{𝑐𝑜𝑟𝑒}}_{\alpha }(u)$ (Lines 5–7). When dealing with each vertex $x$ in $Q$ , it computes $\text{𝑆𝑁}(x)$ value by counting $x$ ’s neighbors whose core numbers are not less than $k$ and are not in $C$ (Lines 8–12). Once $\text{𝑆𝑁}(x)$ is not enough to keep the current core number of $x$ , the procedure DfsUpdate is invoked to record the vertices whose core numbers are going to decrease (Lines 13 and 14). Finally, all the vertices in $C$ that have not been deleted will decrease their core numbers by 1 (Lines 15 and 16). Specifically, if ${\text{𝑐𝑜𝑟𝑒}}_{\alpha }(u)$ after deletion is greater than pre- ${\mathrm{core}}_{\alpha }(u)$ , we will set the ${\mathrm{core}}_{\alpha }(u)$ as pre- ${\mathrm{core}}_{\alpha }(u)$ , since the $core(u)$ is at most pre-core( $u$ ) according to Definition 3 (Lines 17 and 18).

The DfsUpdate first adds $x$ to $C$ and then checks its each neighbor (Lines 20 and 21). For those vertices $w$ with $\mathrm{core}(w)=\mathrm{core}(x)$ , we will discuss them in two cases. If $w$ is not visited, then it will be pushed into $Q$ for further detection (Line 22). Otherwise, if it has been visited but not in $C$ , we decrease $\mathrm{SN}(w)$ by 1. Once $\mathrm{SN}(w)$ is less than $\alpha$ or $\mathrm{core}(x)$ , the DfsUpdate will be recursively called (Lines 23–26).

Performance analysis. We will analyze the correctness and efficiency of Algorithm 3. Similar to Algorithm 2, we first give some useful notations.

Given a graph $G=(U,V,E)$ , we delete an edge $e=(u,v)$ from it. For each $\alpha$ , let $U_{\alpha }^2$ and $V_{\alpha }^2$ be the set of vertices whose core numbers are equal to ${\mathrm{core}}_{\alpha }(e)$ in $U$ and $V$ , respectively, where ${\mathrm{core}}_{\alpha }(e)=$ $\min \{{\mathrm{core}}_{\alpha }(u),$ ${\mathrm{core}}_{\alpha }(v)\}$ . Let $U_D={\max }_{1⩽\alpha ⩽{\mathrm{deg}}_G(u)}{U}_{\alpha }^2$ and $V_D={\max }_{1⩽\alpha ⩽{\mathrm{deg}}_G(v)}{V}_{\alpha }^2$ . Let $E_{\alpha }^2$ be the set of edges in the subgraph induced by $U_{\alpha }^2$ to $V_{\alpha }^2$ . Let $E_D=$ ${\max }_{1⩽\alpha ⩽{\mathrm{deg}}_G(u)}{E}_{\alpha }^2$ .

Let ${\tilde{N}}_U^{\alpha }={\max }_{u_i\in U_{\alpha }^2}\{{\mathrm{SN}}_0(u_i)-\alpha ,0\}$ , where ${\mathrm{SN}}_0(u_i)$ denotes the SN value of $u_i$ when $u_i$ is first processed. Let ${\tilde{N}}_U={\max }_{1⩽\alpha ⩽{\mathrm{deg}}_G(u)}{\tilde{N}}_U^{\alpha }$ . Similarly, we define ${\tilde{N}}_V^{\alpha }={\max }_{v_i\in V_{\alpha }^2}\{{\mathrm{SN}}_0(v_i)-{\mathrm{core}}_{\alpha },0\}$ and ${\tilde{N}}_V={\max }_{1⩽\alpha ⩽{\mathrm{deg}}_G(u)}{\tilde{N}}_V^{\alpha }$ .

Using the notations above and an analysis similar to the single-edge insertion case, we can easily obtain the following theorem.

Theorem 3 When deleting an edge $e=(u,v)$ from graph $G$ , Algorithm 3 can update the core numbers of vertices in $O(de{g}_G(u)\times (E_D+U_D\times {\tilde{N}}_U+V_D\times {\tilde{N}}_V))$ time.

Algorithm. The detailed algorithm to maintain each vertex’s core number with the insertion of multiple edges is given in Algorithm 4. It is executed until all edges in $E_s$ have been processed (Line 1). In each iteration, the algorithm calls the subroutine FindInsertEdges to find a $V$ -independent edge set $E_i$ and deletes it from $E_s$ (Lines 2–4). For each possible $\alpha$ , the InsertChangedSet algorithm is invoked to find the vertices whose core numbers will increase by 1 after insertion and change their core numbers (Lines 5–9).

Algorithm 5 aims to find a $V$ -independent edge set $E_i$ from all unprocessed edges in $E_s$ . Basically, it sets two parameters, $\mathrm{addN}[]$ marking the connection between a node in $V$ and the selected edges, and flag indicating whether an edge is selected or not (Lines 2–4). For each endpoint $u$ of edge $e=(u,v)$ in $E_s$ , there are two cases for the algorithm execution. When $u$ is not in $U_c$ , then it checks if $u$ ’s neighbors and $v$ are already connected to other vertices in $U_c$ (Lines 7 and 8). Once any vertex is found whose $\mathrm{addN}[]$ is not 0, the algorithm will set flag to false indicating this edge cannot be selected (Lines 9–11). Similarly, when $u$ has been in $U_c$ , the algorithm will check if $v$ is already connected to other vertices in $U_c$ (Lines 12 and 13). When flag is true, the edge $e$ will be added into $E_i$ (Lines 14 and 15). If $u$ is not in $U_c$ , it will add $u$ to $U_c$ and update $\mathrm{addN}[]=u$ for each neighbor of $u$ and $v$ (Lines 16–18).

After the VES is found, Algorithm 6 is invoked to find all vertices whose core numbers will change after insertion. Similar to Algorithm 2, we first do the initialization (Lines 1–6). For each edge $(u_i,v_i)$ to be inserted, it computes the pre-core of $u_i$ and then adds the endpoint with the smaller core number to $Q$ (Lines 7–12). When a vertex $x$ is ejected from $Q$ , the algorithm inserts it into $C$ and sets $\mathrm{visited}[x]$ as true (Lines 14–16). For each vertex $x$ in $Q$ , each of its neighbors $y$ is checked to see if $x$ ’s core number is likely to increase. The calculation of SN value is the same as the case of single-edge insertion (Lines 17–22). If $\mathrm{SN}(x)$ reaches the threshold, i.e., $\mathrm{SN}(x)$ is greater than $\mathrm{core}(x)$ when $x$ in $V$ or is not less than $\alpha$ when $x$ in $U$ , then each neighbor $y$ of $x$ which satisfies ${\mathrm{core}}_{\alpha }(y)$ = ${\mathrm{core}}_{\alpha }(x)$ and is not visited is pushed into $Q$ for further checking (Lines 23 and 24). Otherwise, the procedure DfsDelete is invoked to remove $x$ from $C$ , since it is impossible for $\mathrm{core}(x)$ to increase (Line 25).

Performance analysis. To analyze the time complexity of the algorithm, we first provide some useful notations. Let ${\Delta }_I$ be the maximum number of edges inserted for each vertex in $V$ . By the definition of VES, it is easy to see that the inserted edges can be divided into ${\Delta }_I$ $V$ -independent edge sets. When a VES $E_i$ is inserted into graph $G=(U,V,E)$ , the maximum degree of all vertices in $U_c$ is denoted by $\max D_i$ and $\max D_I={\max }_{1⩽i⩽{\Delta }_I}\max D_i$ . For each $\alpha$ , let $U_{\alpha }^3$ and $V_{\alpha }^3$ be the set of vertices whose core numbers are equal to $\mathrm{core}(e_i)$ in $U$ and $V$ , respectively, where $e_i=(u_i,v_i)\in E_i$ and ${\mathrm{core}}_{\alpha }(e_i)=$ $\min \{{\mathrm{core}}_{\alpha }(u_i),{\mathrm{core}}_{\alpha }(v_i)\}$ . Let ${\tilde{U}}_I=$ ${\max }_{1⩽\alpha ⩽\max D_I}{U}_{\alpha }^3$ and ${\tilde{V}}_I={\max }_{1⩽\alpha ⩽\max D_I}{V}_{\alpha }^3$ . Let $E_{\alpha }^3$ be the set of edges in the subgraph induced by $U_{\alpha }^3$ to $V_{\alpha }^3$ , and let ${\tilde{E}}_I={\max }_{1⩽\alpha ⩽\max D_I}{E}_{\alpha }^3$ .

Let $M_U^{\alpha }$ = ${\max }_{u_i\in U_{\alpha }^3}\{{\mathrm{SN}}_0(u_i)-\alpha ,0\}$ , where ${\mathrm{SN}}_0(u_i)$ denotes the SN value of $u_i$ when $u_i$ is processed for the first time. Let $M_U$ = ${\max }_{1⩽\alpha ⩽\max D_I}{M}_U^{\alpha }$ . Similarly, we define $M_V^{\alpha }$ = ${\max }_{v_i\in V_{\alpha }^3}\{{\mathrm{SN}}_0(v_i)-{\mathrm{core}}_{\alpha },0\}$ and $M_V$ = ${\max }_{1⩽\alpha ⩽\max D_I}{M}_V^{\alpha }$ .

The following theorem gives the time complexity of Algorithm 4 and proves its correctness.

Theorem 4 Algorithm 4 can correctly update the core numbers of all vertices after inserting an edge set $E_s$ in $O({\Delta }_I\times (\max D_I\times (({\tilde{E}}_I+{\tilde{U}}_I\times M_U+{\tilde{V}}_I\times M_V))))$ time.

Proof Algorithm 4 is executed in iterations and each iteration includes two parts. The first part finds a $V$ -independent edge set from all unprocessed edges in $E_s$ by executing Algorithm 5. According to Lemma 3, each vertex can change its core number by 1 after inserting a $V$ -independent edge set into the graph.

As for the second part, we invoke Algorithm 6 to identify the vertices whose core number can increase after insertion for each $\alpha$ . It starts from the inserted edges and adds each endpoint with the smaller core number to $Q$ for further identification. Similar to Algorithm 2, the algorithm uses $\mathrm{SN}(w)$ to record the number of neighbors that support $w$ ’s core number increase. If $\mathrm{SN}(w)⩽{\mathrm{core}}_{\alpha }(w)$ , it is obvious that $w$ ’s core number will not increase. Once a vertex is identified not to change its core number, the SN values of other vertices are updated by invoking DfsDelete. After all the vertices whose core numbers might change have been processed, the vertices in $C$ that are not deleted will increase their core numbers, as these vertices have enough neighbors to support them in an $(\alpha ,\beta )$ -core with a larger $\beta$ value. When all edges in $E_s$ are handled, the potential vertices are visited and the ones that cannot increase core numbers are removed. All of the above ensure the correctness of Algorithm 4.

As for the time complexity, it is similar to the case of single-edge insertion. The difference is that Algorithm 4 has to deal with multiple edges in ${\Delta }_I$ batches. For each batch, the algorithm needs to iterate at most $\max D_i$ times. Based on Lemma 2, when inserting an edge $e=(u,v)$ (assuming ${\mathrm{core}}_{\alpha }(u)$ $⩽$ ${\mathrm{core}}_{\alpha }(v)$ ), only the vertices $w$ with $\mathrm{core}(w)$ = $\mathrm{core}(u)$ are reachable from $u$ through a $C$ -path, and can change their core numbers. Therefore, when inserting a VES into the graph, the number of vertices and edges visited by Algorithm 4 is at most $U_I+V_I$ and $E_I$ , respectively. For each vertex, except for the first SN value calculation when ejected from $Q$ , all the subsequent visits will decrease its SN value by 1. So for the vertex $u\in U(v\in V)$ , it can be visited by at most $N_u(N_v)$ times, since it will be removed from $C$ when its SN is smaller than $\alpha$ $({\mathrm{core}}_{\alpha })$ . Then we can know that the vertex $u\in U$ $(v\in V)$ will be visited at most $N_U$ ( $N_V$ ) times in any iteration. Therefore, it can be concluded that the time complexity of the Algorithm 4 is the same as stated in Theorem 4.

Discussion. A point we would like to emphasize is that the batch processing algorithm can greatly reduce redundant computations. This is because when processing the insertion of a $VES$ , once a vertex is determined to increase its core number, it is unnecessary to visit this vertex again, as it will not increase the core number anymore. We illustrate this observation with the graph in Fig. 1 . Assuming that $E_s=\{(u_2,v_1),$ $(u_2,v_2),(u_2,v_3)\}$ is the edge set that needs to deal with. If we insert these edges one by one using Algorithm 2, then we need to visit vertex $u_2$ three times, vertex $u_1$ and $v_1$ two times, and the rest vertices once. However, since the $E_s$ satisfies the conditions of $V$ -independent edge set, so we can process these edges using one iteration and visit all vertices in $U$ and $V$ only once. Thus, the time consumed is significantly reduced.

Algorithm. The detailed algorithm to maintain each vertex’s core number with the insertion of multiple edges is given in Algorithm 4. It is executed until all edges in $E_s$ have been processed (Line 1). In each iteration, the algorithm calls the subroutine FindInsertEdges to find a $V$ -independent edge set $E_i$ and deletes it from $E_s$ (Lines 2–4). For each possible $\alpha$ , the InsertChangedSet algorithm is invoked to find the vertices whose core numbers will increase by 1 after insertion and change their core numbers (Lines 5–9).

Algorithm 5 aims to find a $V$ -independent edge set $E_i$ from all unprocessed edges in $E_s$ . Basically, it sets two parameters, $\mathrm{addN}[]$ marking the connection between a node in $V$ and the selected edges, and flag indicating whether an edge is selected or not (Lines 2–4). For each endpoint $u$ of edge $e=(u,v)$ in $E_s$ , there are two cases for the algorithm execution. When $u$ is not in $U_c$ , then it checks if $u$ ’s neighbors and $v$ are already connected to other vertices in $U_c$ (Lines 7 and 8). Once any vertex is found whose $\mathrm{addN}[]$ is not 0, the algorithm will set flag to false indicating this edge cannot be selected (Lines 9–11). Similarly, when $u$ has been in $U_c$ , the algorithm will check if $v$ is already connected to other vertices in $U_c$ (Lines 12 and 13). When flag is true, the edge $e$ will be added into $E_i$ (Lines 14 and 15). If $u$ is not in $U_c$ , it will add $u$ to $U_c$ and update $\mathrm{addN}[]=u$ for each neighbor of $u$ and $v$ (Lines 16–18).

After the VES is found, Algorithm 6 is invoked to find all vertices whose core numbers will change after insertion. Similar to Algorithm 2, we first do the initialization (Lines 1–6). For each edge $(u_i,v_i)$ to be inserted, it computes the pre-core of $u_i$ and then adds the endpoint with the smaller core number to $Q$ (Lines 7–12). When a vertex $x$ is ejected from $Q$ , the algorithm inserts it into $C$ and sets $\mathrm{visited}[x]$ as true (Lines 14–16). For each vertex $x$ in $Q$ , each of its neighbors $y$ is checked to see if $x$ ’s core number is likely to increase. The calculation of SN value is the same as the case of single-edge insertion (Lines 17–22). If $\mathrm{SN}(x)$ reaches the threshold, i.e., $\mathrm{SN}(x)$ is greater than $\mathrm{core}(x)$ when $x$ in $V$ or is not less than $\alpha$ when $x$ in $U$ , then each neighbor $y$ of $x$ which satisfies ${\mathrm{core}}_{\alpha }(y)$ = ${\mathrm{core}}_{\alpha }(x)$ and is not visited is pushed into $Q$ for further checking (Lines 23 and 24). Otherwise, the procedure DfsDelete is invoked to remove $x$ from $C$ , since it is impossible for $\mathrm{core}(x)$ to increase (Line 25).

Performance analysis. To analyze the time complexity of the algorithm, we first provide some useful notations. Let ${\Delta }_I$ be the maximum number of edges inserted for each vertex in $V$ . By the definition of VES, it is easy to see that the inserted edges can be divided into ${\Delta }_I$ $V$ -independent edge sets. When a VES $E_i$ is inserted into graph $G=(U,V,E)$ , the maximum degree of all vertices in $U_c$ is denoted by $\max D_i$ and $\max D_I={\max }_{1⩽i⩽{\Delta }_I}\max D_i$ . For each $\alpha$ , let $U_{\alpha }^3$ and $V_{\alpha }^3$ be the set of vertices whose core numbers are equal to $\mathrm{core}(e_i)$ in $U$ and $V$ , respectively, where $e_i=(u_i,v_i)\in E_i$ and ${\mathrm{core}}_{\alpha }(e_i)=$ $\min \{{\mathrm{core}}_{\alpha }(u_i),{\mathrm{core}}_{\alpha }(v_i)\}$ . Let ${\tilde{U}}_I=$ ${\max }_{1⩽\alpha ⩽\max D_I}{U}_{\alpha }^3$ and ${\tilde{V}}_I={\max }_{1⩽\alpha ⩽\max D_I}{V}_{\alpha }^3$ . Let $E_{\alpha }^3$ be the set of edges in the subgraph induced by $U_{\alpha }^3$ to $V_{\alpha }^3$ , and let ${\tilde{E}}_I={\max }_{1⩽\alpha ⩽\max D_I}{E}_{\alpha }^3$ .

Let $M_U^{\alpha }$ = ${\max }_{u_i\in U_{\alpha }^3}\{{\mathrm{SN}}_0(u_i)-\alpha ,0\}$ , where ${\mathrm{SN}}_0(u_i)$ denotes the SN value of $u_i$ when $u_i$ is processed for the first time. Let $M_U$ = ${\max }_{1⩽\alpha ⩽\max D_I}{M}_U^{\alpha }$ . Similarly, we define $M_V^{\alpha }$ = ${\max }_{v_i\in V_{\alpha }^3}\{{\mathrm{SN}}_0(v_i)-{\mathrm{core}}_{\alpha },0\}$ and $M_V$ = ${\max }_{1⩽\alpha ⩽\max D_I}{M}_V^{\alpha }$ .

The following theorem gives the time complexity of Algorithm 4 and proves its correctness.

Theorem 4 Algorithm 4 can correctly update the core numbers of all vertices after inserting an edge set $E_s$ in $O({\Delta }_I\times (\max D_I\times (({\tilde{E}}_I+{\tilde{U}}_I\times M_U+{\tilde{V}}_I\times M_V))))$ time.

Proof Algorithm 4 is executed in iterations and each iteration includes two parts. The first part finds a $V$ -independent edge set from all unprocessed edges in $E_s$ by executing Algorithm 5. According to Lemma 3, each vertex can change its core number by 1 after inserting a $V$ -independent edge set into the graph.

As for the second part, we invoke Algorithm 6 to identify the vertices whose core number can increase after insertion for each $\alpha$ . It starts from the inserted edges and adds each endpoint with the smaller core number to $Q$ for further identification. Similar to Algorithm 2, the algorithm uses $\mathrm{SN}(w)$ to record the number of neighbors that support $w$ ’s core number increase. If $\mathrm{SN}(w)⩽{\mathrm{core}}_{\alpha }(w)$ , it is obvious that $w$ ’s core number will not increase. Once a vertex is identified not to change its core number, the SN values of other vertices are updated by invoking DfsDelete. After all the vertices whose core numbers might change have been processed, the vertices in $C$ that are not deleted will increase their core numbers, as these vertices have enough neighbors to support them in an $(\alpha ,\beta )$ -core with a larger $\beta$ value. When all edges in $E_s$ are handled, the potential vertices are visited and the ones that cannot increase core numbers are removed. All of the above ensure the correctness of Algorithm 4.

As for the time complexity, it is similar to the case of single-edge insertion. The difference is that Algorithm 4 has to deal with multiple edges in ${\Delta }_I$ batches. For each batch, the algorithm needs to iterate at most $\max D_i$ times. Based on Lemma 2, when inserting an edge $e=(u,v)$ (assuming ${\mathrm{core}}_{\alpha }(u)$ $⩽$ ${\mathrm{core}}_{\alpha }(v)$ ), only the vertices $w$ with $\mathrm{core}(w)$ = $\mathrm{core}(u)$ are reachable from $u$ through a $C$ -path, and can change their core numbers. Therefore, when inserting a VES into the graph, the number of vertices and edges visited by Algorithm 4 is at most $U_I+V_I$ and $E_I$ , respectively. For each vertex, except for the first SN value calculation when ejected from $Q$ , all the subsequent visits will decrease its SN value by 1. So for the vertex $u\in U(v\in V)$ , it can be visited by at most $N_u(N_v)$ times, since it will be removed from $C$ when its SN is smaller than $\alpha$ $({\mathrm{core}}_{\alpha })$ . Then we can know that the vertex $u\in U$ $(v\in V)$ will be visited at most $N_U$ ( $N_V$ ) times in any iteration. Therefore, it can be concluded that the time complexity of the Algorithm 4 is the same as stated in Theorem 4.

Discussion. A point we would like to emphasize is that the batch processing algorithm can greatly reduce redundant computations. This is because when processing the insertion of a $VES$ , once a vertex is determined to increase its core number, it is unnecessary to visit this vertex again, as it will not increase the core number anymore. We illustrate this observation with the graph in Fig. 1 . Assuming that $E_s=\{(u_2,v_1),$ $(u_2,v_2),(u_2,v_3)\}$ is the edge set that needs to deal with. If we insert these edges one by one using Algorithm 2, then we need to visit vertex $u_2$ three times, vertex $u_1$ and $v_1$ two times, and the rest vertices once. However, since the $E_s$ satisfies the conditions of $V$ -independent edge set, so we can process these edges using one iteration and visit all vertices in $U$ and $V$ only once. Thus, the time consumed is significantly reduced.

Algorithm. The detailed algorithm to maintain each vertex’s core number with the insertion of multiple edges is given in Algorithm 4. It is executed until all edges in $E_s$ have been processed (Line 1). In each iteration, the algorithm calls the subroutine FindInsertEdges to find a $V$ -independent edge set $E_i$ and deletes it from $E_s$ (Lines 2–4). For each possible $\alpha$ , the InsertChangedSet algorithm is invoked to find the vertices whose core numbers will increase by 1 after insertion and change their core numbers (Lines 5–9).

Algorithm 5 aims to find a $V$ -independent edge set $E_i$ from all unprocessed edges in $E_s$ . Basically, it sets two parameters, $\mathrm{addN}[]$ marking the connection between a node in $V$ and the selected edges, and flag indicating whether an edge is selected or not (Lines 2–4). For each endpoint $u$ of edge $e=(u,v)$ in $E_s$ , there are two cases for the algorithm execution. When $u$ is not in $U_c$ , then it checks if $u$ ’s neighbors and $v$ are already connected to other vertices in $U_c$ (Lines 7 and 8). Once any vertex is found whose $\mathrm{addN}[]$ is not 0, the algorithm will set flag to false indicating this edge cannot be selected (Lines 9–11). Similarly, when $u$ has been in $U_c$ , the algorithm will check if $v$ is already connected to other vertices in $U_c$ (Lines 12 and 13). When flag is true, the edge $e$ will be added into $E_i$ (Lines 14 and 15). If $u$ is not in $U_c$ , it will add $u$ to $U_c$ and update $\mathrm{addN}[]=u$ for each neighbor of $u$ and $v$ (Lines 16–18).

After the VES is found, Algorithm 6 is invoked to find all vertices whose core numbers will change after insertion. Similar to Algorithm 2, we first do the initialization (Lines 1–6). For each edge $(u_i,v_i)$ to be inserted, it computes the pre-core of $u_i$ and then adds the endpoint with the smaller core number to $Q$ (Lines 7–12). When a vertex $x$ is ejected from $Q$ , the algorithm inserts it into $C$ and sets $\mathrm{visited}[x]$ as true (Lines 14–16). For each vertex $x$ in $Q$ , each of its neighbors $y$ is checked to see if $x$ ’s core number is likely to increase. The calculation of SN value is the same as the case of single-edge insertion (Lines 17–22). If $\mathrm{SN}(x)$ reaches the threshold, i.e., $\mathrm{SN}(x)$ is greater than $\mathrm{core}(x)$ when $x$ in $V$ or is not less than $\alpha$ when $x$ in $U$ , then each neighbor $y$ of $x$ which satisfies ${\mathrm{core}}_{\alpha }(y)$ = ${\mathrm{core}}_{\alpha }(x)$ and is not visited is pushed into $Q$ for further checking (Lines 23 and 24). Otherwise, the procedure DfsDelete is invoked to remove $x$ from $C$ , since it is impossible for $\mathrm{core}(x)$ to increase (Line 25).

Performance analysis. To analyze the time complexity of the algorithm, we first provide some useful notations. Let ${\Delta }_I$ be the maximum number of edges inserted for each vertex in $V$ . By the definition of VES, it is easy to see that the inserted edges can be divided into ${\Delta }_I$ $V$ -independent edge sets. When a VES $E_i$ is inserted into graph $G=(U,V,E)$ , the maximum degree of all vertices in $U_c$ is denoted by $\max D_i$ and $\max D_I={\max }_{1⩽i⩽{\Delta }_I}\max D_i$ . For each $\alpha$ , let $U_{\alpha }^3$ and $V_{\alpha }^3$ be the set of vertices whose core numbers are equal to $\mathrm{core}(e_i)$ in $U$ and $V$ , respectively, where $e_i=(u_i,v_i)\in E_i$ and ${\mathrm{core}}_{\alpha }(e_i)=$ $\min \{{\mathrm{core}}_{\alpha }(u_i),{\mathrm{core}}_{\alpha }(v_i)\}$ . Let ${\tilde{U}}_I=$ ${\max }_{1⩽\alpha ⩽\max D_I}{U}_{\alpha }^3$ and ${\tilde{V}}_I={\max }_{1⩽\alpha ⩽\max D_I}{V}_{\alpha }^3$ . Let $E_{\alpha }^3$ be the set of edges in the subgraph induced by $U_{\alpha }^3$ to $V_{\alpha }^3$ , and let ${\tilde{E}}_I={\max }_{1⩽\alpha ⩽\max D_I}{E}_{\alpha }^3$ .

Let $M_U^{\alpha }$ = ${\max }_{u_i\in U_{\alpha }^3}\{{\mathrm{SN}}_0(u_i)-\alpha ,0\}$ , where ${\mathrm{SN}}_0(u_i)$ denotes the SN value of $u_i$ when $u_i$ is processed for the first time. Let $M_U$ = ${\max }_{1⩽\alpha ⩽\max D_I}{M}_U^{\alpha }$ . Similarly, we define $M_V^{\alpha }$ = ${\max }_{v_i\in V_{\alpha }^3}\{{\mathrm{SN}}_0(v_i)-{\mathrm{core}}_{\alpha },0\}$ and $M_V$ = ${\max }_{1⩽\alpha ⩽\max D_I}{M}_V^{\alpha }$ .

The following theorem gives the time complexity of Algorithm 4 and proves its correctness.

Theorem 4 Algorithm 4 can correctly update the core numbers of all vertices after inserting an edge set $E_s$ in $O({\Delta }_I\times (\max D_I\times (({\tilde{E}}_I+{\tilde{U}}_I\times M_U+{\tilde{V}}_I\times M_V))))$ time.

Proof Algorithm 4 is executed in iterations and each iteration includes two parts. The first part finds a $V$ -independent edge set from all unprocessed edges in $E_s$ by executing Algorithm 5. According to Lemma 3, each vertex can change its core number by 1 after inserting a $V$ -independent edge set into the graph.

As for the second part, we invoke Algorithm 6 to identify the vertices whose core number can increase after insertion for each $\alpha$ . It starts from the inserted edges and adds each endpoint with the smaller core number to $Q$ for further identification. Similar to Algorithm 2, the algorithm uses $\mathrm{SN}(w)$ to record the number of neighbors that support $w$ ’s core number increase. If $\mathrm{SN}(w)⩽{\mathrm{core}}_{\alpha }(w)$ , it is obvious that $w$ ’s core number will not increase. Once a vertex is identified not to change its core number, the SN values of other vertices are updated by invoking DfsDelete. After all the vertices whose core numbers might change have been processed, the vertices in $C$ that are not deleted will increase their core numbers, as these vertices have enough neighbors to support them in an $(\alpha ,\beta )$ -core with a larger $\beta$ value. When all edges in $E_s$ are handled, the potential vertices are visited and the ones that cannot increase core numbers are removed. All of the above ensure the correctness of Algorithm 4.

As for the time complexity, it is similar to the case of single-edge insertion. The difference is that Algorithm 4 has to deal with multiple edges in ${\Delta }_I$ batches. For each batch, the algorithm needs to iterate at most $\max D_i$ times. Based on Lemma 2, when inserting an edge $e=(u,v)$ (assuming ${\mathrm{core}}_{\alpha }(u)$ $⩽$ ${\mathrm{core}}_{\alpha }(v)$ ), only the vertices $w$ with $\mathrm{core}(w)$ = $\mathrm{core}(u)$ are reachable from $u$ through a $C$ -path, and can change their core numbers. Therefore, when inserting a VES into the graph, the number of vertices and edges visited by Algorithm 4 is at most $U_I+V_I$ and $E_I$ , respectively. For each vertex, except for the first SN value calculation when ejected from $Q$ , all the subsequent visits will decrease its SN value by 1. So for the vertex $u\in U(v\in V)$ , it can be visited by at most $N_u(N_v)$ times, since it will be removed from $C$ when its SN is smaller than $\alpha$ $({\mathrm{core}}_{\alpha })$ . Then we can know that the vertex $u\in U$ $(v\in V)$ will be visited at most $N_U$ ( $N_V$ ) times in any iteration. Therefore, it can be concluded that the time complexity of the Algorithm 4 is the same as stated in Theorem 4.

Discussion. A point we would like to emphasize is that the batch processing algorithm can greatly reduce redundant computations. This is because when processing the insertion of a $VES$ , once a vertex is determined to increase its core number, it is unnecessary to visit this vertex again, as it will not increase the core number anymore. We illustrate this observation with the graph in Fig. 1 . Assuming that $E_s=\{(u_2,v_1),$ $(u_2,v_2),(u_2,v_3)\}$ is the edge set that needs to deal with. If we insert these edges one by one using Algorithm 2, then we need to visit vertex $u_2$ three times, vertex $u_1$ and $v_1$ two times, and the rest vertices once. However, since the $E_s$ satisfies the conditions of $V$ -independent edge set, so we can process these edges using one iteration and visit all vertices in $U$ and $V$ only once. Thus, the time consumed is significantly reduced.

Algorithm. The detailed algorithm to maintain each vertex’s core number when multiple edges are deleted is given in Algorithm 7. It is executed until all edges in $E_s$ have been processed (Line 1). In each iteration, the algorithm calls the subroutine FindDeleteEdges to find a $V$ -independent edge set $E_i$ of $E_s$ (Line 2). Then for each $\alpha$ , the DeleteChangedSet algorithm is invoked to find the vertices whose core numbers will decrease by 1 after deleting $E_i$ and set their core numbers (Lines 5– 9). Specifically, for those vertices in $U$ connected to $E_i$ , their current core numbers are compared with pre-core, because deleting $E_i$ may cause their core numbers to change by more than 1 (Lines 10–12).

Algorithm 8 finds a VES from the unprocessed edges in $E_s$ . The algorithm is similar to Algorithm 5 except that for each edge $e=(u,v)$ , we need not to deal with $v$ , because $v$ is no longer a neighbor of $u$ after deletion. When finding the vertices whose core number changes in Algorithm 9, the difference is that it compares ${\mathrm{core}}_{\alpha }(u)$ with ${\mathrm{core}}_{\alpha }(v)$ instead of computing pre- ${\mathrm{core}}_{\alpha }(u)$ for each edge $e=(u,v)$ (Lines 3–6). When dealing with each vertex $x$ in $Q$ , the process of computing $\mathrm{SN}(x)$ value is similar to Algorithm 3 (Lines 11–17). Once the $\mathrm{SN}(x)$ is not enough to keep the current core number of $x$ , the procedure DfsUpdate is invoked to record ${\mathrm{core}}_{\alpha }(x)$ that is going to decrease (Lines 18 and 19).

Performance analysis. Firstly, we will give some notations that are similar to the case of inserting multiple edges and then the correctness and time complexity of Algorithm 7 can be easily obtained.

Let ${\Delta }_D$ be the maximum number of edges deleted from each vertex in $V$ . Similarly, we can get that the number of $VES$ s is ${\Delta }_D$ . When a $VES$ $E_i$ is deleted from graph $G=(U,V,E)$ , the maximum degree of all vertices in $U_c$ is denoted by $\max D_d$ and $\max D_D={\max }_{1⩽i⩽{\Delta }_D}\max D_d$ . For each $\alpha$ , let $U_{\alpha }^4$ and $V_{\alpha }^4$ be the set of vertices whose core numbers equal to $\mathrm{core}(e_i)$ in $U$ and $V$ , respectively, where $e_i=(u_i,v_i)\in E_i$ and ${\mathrm{core}}_{\alpha }(e_i)=\min \{{\mathrm{core}}_{\alpha }(u),{\mathrm{core}}_{\alpha }(v)\}$ . Let ${\tilde{U}}_D={\max }_{1⩽\alpha ⩽\max D_D}{U}_{\alpha }^4$ and ${\tilde{V}}_D={\max }_{1⩽\alpha ⩽\max D_D}{V}_{\alpha }^4$ . Let $E_{\alpha }^4$ be the set of edges in the subgraph induced by $U_{\alpha }^4$ to $V_{\alpha }^4$ and let ${\tilde{E}}_D={\max }_{1⩽\alpha ⩽\max D_D}{E}_{\alpha }^4$ .

Let ${\tilde{M}}_U^{\alpha }={\max }_{u_i\in U_{\alpha }^4}\{{\mathrm{SN}}_0(u_i)-\alpha ,0\}$ , where ${\mathrm{SN}}_0(u_i)$ denotes the SN value of $u_i$ when $u_i$ is processed for the first time. Let ${\tilde{M}}_U={\max }_{1⩽\alpha ⩽\max D_D}{\tilde{M}}_U^{\alpha }$ . Similarly, we define ${\tilde{M}}_V^{\alpha }={\max }_{v_i\in V_{\alpha }^4}\{{\mathrm{SN}}_0(v_i)-{\mathrm{core}}_{\alpha },0\}$ and ${\tilde{M}}_V$ = ${\max }_{1⩽\alpha ⩽\max D_D}{\tilde{M}}_V^{\alpha }$ .