# An Information-Theoretic Approach for Detecting Community Structure Based on Network Representation
## 3 The Approach
### Basic Process of the Approach  
The basic idea of AMI-NRL is to form a community evolution process using the representation of the nodes and then to select the most stable partition in process as the final result. The following steps show the basic process of the approach:  
1. Random walks through out the network, recording the passing nodes to obtain the node sequences. 2. Obtaining the vectorial representation of each node by inputting these sequences into the Word2 vec model. 3. Cluster these vectors with aggregation hierarchical clustering, regarding the clusters as communities, in order to form a bottom-up cohesion community evolution process \(P=\{P_{0},P_{1},P_{2},\cdots,P_{N}\}\)
4. Calculating the AMI value \(I_{P_{n},P_{n+1}}\) of each two adjacent partitions, as well as the entropy \(H_{P_{n}}\) of each partition. Calculating the \(Q_{P_{n}}\) value of each partition and selecting the partition \(P_{a}\) with largest \(Q_{P_{n}}\) to output as the result partition. Steps 1 and 2 are used to obtain the representation of each node of the network using Deepwalk [21]. We conducted experiments on a number of different network representation learning methods, including Deepwalk [21], Node2 Vec [22], Walklets [23], NMFADMM [24], NetMF [25], GLEE [26], RandNE [27], BoostNE [28], and GraRep [29]. By comparing the results of applying them to our approach, we finally selected Deepwalk because of its clearer and more stable boundaries in its clustering results on multiple real-world datasets. In Step 1, a random walk iteration of \(R\) times is designed. According to our experiments, better results can be achieved in our experiments when setting \(R\) from 10 to 25. In each iteration, each node of the network is correspondingly set as the starting point of the random walker. Then, it randomly moves to its neighboring nodes equiprobably. After \(L-1\) moves, it generates \(N\) node sequences with length \(L\). In our experiments, we found that for larger networks, larger \(L\) values were needed to be set. Step 1 finally generates \(R\cdot N\) node sequences with length \(L\). In Step 2, the sequences are input into the Skip-gram model, which is a two-layer neural network used in Word2 vec. In the training phase, a specific node is input at one time, and the model is required to output the predict nodes accurately within its window, that is, the context of the input node. After multiple iterations, a weight matrix from the input layer to the hidden layer can be learned. Each row of the weight matrix represents the weight of each node in the input layer corresponding to the neurons in the hidden layer. This is a vectorial representation of the node. A good result can be obtained by setting the context window size to 7 and the number of hidden-layer neurons to 50. After obtaining the representation of the nodes, Step 3 performs an agglomerative hierarchical clustering on them to construct a bottom-up cohesion community evolution process. While clustering, Euclidean distance and Ward's method [30] are used to calculate the distance between vectors and between clusters, respectively. The hierarchical clustering will produce a dendrogram. Each layer of the dendrogram naturally corresponds to a community partition. In adjacent layers, there will be a pair of communities merged into one. A bottom-up cohesion community evolution process can be generated in this way. Finally, in Steps 4 and 5, by using the community evaluation index based on AMI, the \(Q_{P_{n}}\) value of each partition of the process is calculated. The partition \(P_{a}\) with largest \(Q_{P_{n}}\) value is selected as the result of community detection.