# MINC-NRL: An Information-Based Approach for Community Detection
## 4 Community Detection Based on MINC
### Time Complexity Analysis  
The time complexity of this algorithm can be calculated in three parts:  
Figure 5: MINC value of community evolution process generated from Polbooks.  
1. **Network Representation Learning** Firstly, random walks are perform in the network. Starting from each node, the random walker need to go \(L\) steps in the network, and such process will iterate \(R\) times. Hence the time complexity for random-walk is \(O(nLR)\), where \(n\) is the number of nodes of the network. Then the sequences will be input into the Word2 vec model. The model first uses a window of size \(W\) sliding through these sequences to count the co-occurrence frequency between nodes, which need a time complexity of \(O(nLRW)\). Meanwhile, the representation vectors for the nodes will be updated using a stochastic gradient descent process of \(E\) epochs in \(O(E\log(n))\) time, with the acceleration of the hierarchical softmax. To sum up, the overall time complexity of the network representation learning part is \(O(nLR)+O(nLRWE\log(n))\).
2. **Hierarchical Clustering** With the acceleration by a nearest neighbor chain, the agglomerative hierarchical clustering (AHC) needs a time complexity of \(O(n^{2})\). For the overlapping hierarchical clustering (OHC), in each iteration, or each level of the dendrogram, each cluster should traverse all nodes to decide which one is the closest, this leads to \(O(Cn)\) time, where \(C\) is the number of clusters for each level. The number of levels of the dendrogram created by OHC is proportional to the number of nodes \(n\). Thus, the total time complexity for OHC is \(O(Cn^{2})\).
3. **Find the Peak Value of MINC** For a partition, the main time cost for MINC calculation comes form obtaining \(\theta\) and \(\pi\), which need a traverse of all edges for their belonging community. To achieve this, a map is first built to store which community each node belongs to, with a time complexity of \(O(n)\). Hence, \(O(n+m)\) is needed, where \(m\) is the number of edges of the network. Since the dendrogram created by hierarchical clustering has \(O(n)\) levels, and each level will be regraded as a partition for MINC calculation, the overall time complexity for this part is \(O(n(n+m))\).  
In conclusion, the time complexity for the approach is \(O(nLR)+O(nLRWE\log(n))+O(n^{2})+O(n(n+m))\) for non-overlapping community detection and \(O(nLR)+O(nLRWE\log(n))+O(Cn^{2})+O(n(n+m))\) for overlapping community detection. During the actual running of the approach, random-walk length \(L\), iteration \(R\), window size \(W\), and update epochs \(E\) are much smaller than the number of nodes \(n\) and the number of edges \(m\), the main time cost comes from the clustering part and MINC calculation part. For non-overlapping community detection, the total time complexity is \(O(n^{2})+O(n(n+m))=O(n(n+m))\); for overlapping community detection, it is \(O(Cn^{2})+O(n(n+m))\). It should be noted that the number of clusters \(C\) for each level in OHC depends on the merging criterion \(\lambda\) in OHC algorithm. When the \(\lambda\) increases, clusters are more likely to merge, which decrease \(C\). When setting \(\lambda=0.1\), the OHC algorithm tends to have a time cost of about \(O(n^{245})\)[25]. Hence, the \(O(Cn^{2})\) time for OHC becomes the major bottleneck in computational efficiency of the approach in overlapping community detection tasks.