# Dynamic Community Detection Based on Evolutionary DeepWalk
## 3 The DeDW Algorithm
### Evolutionary DeepWalk
The addition of node \(i\) at time \(t\) is shown in Equation (3):  
\[HF_{i}^{t}=\varnothing\text{ and }CF_{i}^{t}\
eq\varnothing \tag{3}\]  
The deletion of node \(i\) at time \(t\) is shown in Equation (4):  
\[HF_{i}^{t}\
eq\varnothing\text{ and }CF_{i}^{t}=\varnothing \tag{4}\]  
The detailed calculation processing of node change is given in Figure 2.  
1. Nodes Addition. At time \(t\), if a new node \(i\) is added, there will be a new feature vector \(CF_{i}^{t}\) in the feature vector of \(CF^{t}\). To use Equation (2), we must ensure that the dimension of \(HF^{t}\) and \(CF^{t}\) are \(n\times d\). \(HF^{t}\) does not have node \(i\), so we need to deal with \(HF^{t}\). Our method is to add zero vectors to the position of the corresponding new node \(i\) as the reserved position in \(HF^{t}\), so that there is a position of the corresponding new node \(i\) vector when calculating \(ComF^{t}\). 2. Nodes Deletion. (b). At time \(t\), if there is a node \(i\) leaving the network, the eigenvector of node \(i\) does not exist in the eigenvector of \(CF^{t}\). It only needs to delete the eigenvector \(HF_{i}^{t}\) in \(HF^{t}\) to keep the same number of nodes and dimensions of \(HF^{t}\) and \(CF^{t}\), which is convenient for calculating \(ComF^{t}\). The AddNodes and DelNodes are two sets to store the added and deleted nodes calculated, respectively, according to Equations (3) and (4). If there is a node to be added, a zero vector is added to the corresponding position to complete \(HF^{t}\). If there is a node to be deleted, \(HF^{t}\) directly removes the relevant node vector from it. EvoGE only processes the embedding feature matrix without other complicated steps, so the time complexity is \(O(1)\)During the execution of Algorithm 1, given historical embedding matrix \(H\!F^{t}\) of \(G\) at time step \(t\) and current embedding matrix \(CF^{t}\) of \(G\) at time step \(t\). Taking Figure 2 as an example, Line 1 is used to find nodes added to the graph with the time step. In the top part of Figure 2, we can that node \(i\) is added to the graph from the first two time-steps (from \(t=1\) to \(t=2\)). While from the time step \(t=2\) to \(t=3\), node \(j\) leaves the graph. This step is calculated with Line 2. If any nodes are added to the graph detected by Line 3-5, In order to keep the same size of the embedding matrix, corresponding zero vectors should be added to \(H\!F^{t}\). Meanwhile, if the algorithm detects some nodes are removed from the graph, then corresponding node vectors should be removed from \(CF^{t}\) (Line 6-8). Finally, comprehensive features matrix can be calculated by Line 9. Then, we can obtain the final embedding matrix of the graph at time step \(t\). ```
Input: Historical Features matrix \(H\!F^{t}\); Current Features matrix \(CF^{t}\) Output: Comprehensive Features matrix \(ComF^{t}\)
1 compute AddNodes form Equation (3) //get nodes which are added
2 compute DelNodes from Equation (4) //get nodes which are deleted
3 if AddNodes \(\
eq\partial\)do//Nodes Addition
4\(H\!F^{t}\). Add(\(\overset{\triangle}{0}*\)AddNodes)
5 endif
6 if DelNodes \(\
eq\partial\)do//Nodes Deletion
7\(H\!F^{t}\). Del(DelNodes)
8 endif
9\(ComF^{t}=\alpha HF^{t}+(1-\alpha)\ CF^{t}\)
10 return\(ComF^{t}\)
```  
**Algorithm 1**evolutionary DeepWalk (EDW)