# Dynamic Community Detection Based on Evolutionary DeepWalk
## 3 The DeDW Algorithm
### Evolutionary DeepWalk  
DeepWalk is the first algorithm to combine natural language processing with unsupervised feature learning in complex networks. Firstly, the random walk sequence is obtained for each node. Then, the sequences are input into the skip-gram model [26] of natural language processing in the context of the node, to obtain the embedded feature vector of each node. The time complexity of DeepWalk is mainly divided into two aspects. One is that the time complexity of random walk sampling is \(O(n+m)\), and the other is that the complexity of the skip-gram model is \(O(n\text{log}n)\), so the time complexity of this algorithm is \(O(n+m+n\text{log}n)\). This method aims to analyze the community and its evolution in a unified and smooth time process. That is, the evolution of network community structure from time \(t-1\) to time \(t\) is relatively stable, and there will be no network structure mutation. To achieve this goal, inspired by the cost function of evolutionary clustering (Equation (1)), we try to use the \begin{table}
\begin{tabular}{c c} \hline \hline
**Symbols** & **Descriptions** \\ \hline \(G\) & dynamic networks \\ \(g\) & temporal snapshot network \\ \(t\) & time snapshot \\ \(T\) & the number of temporal snapshot networks \\ \(m\) & the number of edges \\ \(n\) & the number of nodes \\ \(d\) & the dimension of embedding vector \\ \(C\) & community aggregation of dynamic network \\ \(HF_{t}^{t}\) & the embedding vector of node \(i\) in historical embedding matrix at time \(t\) \\ \(CF_{t}^{t}\) & the embedding vector of node \(i\) in current embedding matrix at time \(t\) \\ \(ComF^{t}\) & the comprehensive features matrix of network embedding at time \(t\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Symbols and descriptions. community structure at time \(t-1\) to regulate the community structure at time \(t\). Therefore, we propose the concept of evolutionary DeepWalk. The calculation formula is as follows:  
\[ComF=\alpha HF+(1-\alpha)CF \tag{2}\]  
where \(ComF\) (Comprehensive Features) represents the overall features of the community structure at time \(t\), \(CF\) (Current Features) is the node embedding feature obtained by DeepWalk into the network at time \(t\). \(HF\) (Historical Features) represents comprehensive features of the network at time \(t-1\). The parameter \(\alpha\) is a hyperparameter to control the influence weight of the historical features on the current features. In the real-world network, the nodes in the network will change over time. New nodes will join the current network and establish new connections with other nodes in the network. Some existing nodes in the network will also leave the current network, and the connections established by these nodes will be disconnected accordingly. By analyzing the above situation, we can see that the change in the edge can be divided into two situations. That is, the addition of edges and the deletion of edges, and the change of node can be divided into two situations: The addition of nodes and the deletion of nodes. When the connected edges in the network change, the node binary tree constructed in the DeepWalk algorithm will be different, so the node sequence generated by random walk will change, then the current embedded vector of each node will change. Therefore, there is no need to consider the change of network connection edge in the algorithm. The change of the node will change the size of the overall embedding matrix. When dealing with the change of nodes, our method is used to deal with the embedded feature matrix obtained by DeepWalk. To consider the change of nodes in the network, it is necessary to deal with the historical embedded matrix and the current embedded matrix. We define the type of node change, node change is mainly divided into two cases, one is Node addition, and the other is node deletion.