# Dynamic Community Detection Based on Evolutionary DeepWalk
## 3 The DeDW Algorithm
### Dynamic Community Detection  
According to the proposed EDW, the comprehensive embedding feature vector of each node in each temporal snapshot network can be obtained, and then the community structure of the current temporal snapshot network can be divided by applying the clustering algorithm. Therefore, we propose DEDW. Figure 2 shows an illustrative example to detect the community using DEDW. The algorithm is specified in Algorithm 2. Figure 2: Main framework of DEDW. As shown in Figure 2, in DEDW, the dynamic network \(G\) can be partitioned into three temporal snapshot networks: \(g_{1}\), \(g_{2}\), and \(g_{3}\). 1. Firstly, we perform community detection on \(g_{1}\). Then, we use graph embedding to obtain the comprehensive feature matrix \(ComF^{1}\) and then use the clustering algorithm to cluster the feature matrix to obtain the community result at \(t=1\). 2. Then, observing \(g_{2}\), we can see that the network only adds a new node \(i\) in \(t=2\). First, we use DeepWalk to embed \(g_{2}\) to obtain the current embedding feature matrix \(CF^{2}\) and use \(ComF^{1}\) as the historical embedding feature matrix \(HF^{2}\) in this step. Since there is no corresponding feature vector of node \(i\) in \(HF^{2}\), it is necessary to judge the change of nodes in \(g_{2}\). According to the row number of feature vectors, we can get the embedding features vector of node \(i\) added in \(CF^{2}\), so we can set the node \(i\) vectors with \(0\) vectors as the features in the corresponding position of \(HF^{2}\). Then, we calculate \(ComF^{2}\) according to Equation (2) and use the clustering algorithm for \(ComF^{2}\) to obtain the community structure of \(g_{2}\) when \(t=2\). 3. Finally, we try to deal with the changing of nodes and their relationship in \(g_{3}\). As shown in Figure 2, the main change in \(g_{3}\) is that node \(j\) leaves the current network, and the connections between this node and other nodes are eliminated at the same time. Firstly, we perform graph embedding on \(g_{3}\) to obtain the current embedding feature matrix \(CF^{3}\). Since there is no feature vector of node \(j\) in \(CF^{3}\), the relevant information of node \(j\) needs to be deleted from \(HF^{3}\). Then, we use the Equation (2) to obtain \(ComF^{3}\) and use the clustering algorithm to obtain the community information of \(g_{3}\). In the above method, DeepWalk is a static graph embedding algorithm, K-Means is the clustering algorithm. When dealing with the initial network, the static graph embedding vector is used as the comprehensive features of the network. Analysis of the time complexity of the frame, mainly in four aspects. 1. The time complexity of DeepWalk;
2. The time complexity of evolutionary graph embedding;
3. The time complexity of K-means;
4. The number of temporal snapshot networks. The main time consumption of DeepWalk is random walk strategies and SkipGram training. For a given graph with \(n\) nodes and \(m\) edges, the sampling strategy is used for the random walk sampling sequence with \(O(1)\) time complexity [12]. Suppose the walk length is \(T\), the count of walk sequence for each node is \(L\), and the time complexity to sampling all sequences is \(O(m)+O(n\times T\times L)\). Then the DeepWalk is optimized by skip-gram with the total time complexity is \(O(E\times n\times T\times L\times K\times\text{log}n)\), where \(E\) is the epoch and \(K\) is the window size. The total time complexity is \(O(m)+O(nTL)+O(E\times nLTK\times\text{log}n)\). Because\(L\), \(T\), \(K\) and \(E\) are small constant [27, 28]. Therefore, the time complexity of DeepWalk is \(O(n+m+n\text{log}n)\). The time complexity of EvoGE is \(O(1)\). The time complexity of \(K\)-means is \(O(k\times d\times n)\). Since \(k\ll d\ll n\), \(k\) and \(d\) are small constants, the time complexity of \(K\)-means can be approximated as \(O(n)\). The number of temporal snapshot networks is \(T\).