# MINC-NRL: An Information-Based Approach for Community Detection
## 5 Experiments
### Benchmarks  
For non-overlapping community detection, since the data sets are partition-labeled, the number of communities (CN) and normalized mutual information (NMI) [32] are used to measure the accuracy of community detection. As a general rule, it is better that the CN of community detection result is exactly the same as labeled, or at least similar with labeled. NMI can be used to evaluate the difference between the result partition and labeled partition based on an information theory framework. The NMI value between partition \(A\) and \(B\) can be formulated as:  
\[NMI(A,B)=\frac{-2\sum_{i=1}^{C_{A}}\sum_{j=1}^{C_{B}}C_{ij}\cdot\log\left(\frac {C_{ij}\cdot N}{C_{i}\cdot C_{j}}\right)}{\sum_{i=1}^{C_{A}}C_{i}\cdot\log\left( \frac{C_{i}}{N}\right)+\sum_{j=1}^{C_{B}}C_{j}\cdot\log\left(\frac{C_{j}}{N} \right)} \tag{15}\]  
where \(N\) is the total number of nodes, \(C\) is a confusion matrix, whose element \(C_{ij}\) denotes the number of nodes belonging to Community i in Partition \(A\) and also belonging to Community j in Partition \(B\). \(C_{A}\) and \(C_{B}\) denote the number of communities of Partition \(A\) and \(B\), respectively. \(C_{i}\) and \(C_{j}\) denote the sum of all elements of a row or column in Matrix \(C\). The value of NMI is between 0 and 1, and it becomes larger when the two partitions are more similar. If the two partitions are exactly the same, the NMI value reaches 1. The NMI index is used in our experiments to compare the result partitions with the labeled partitions. A higher NMI value stands for a better result. For overlapping community detection, we use overlapping modularity (\(Q_{ov}\)) [33], extended modularity (\(EQ\)) [34], and average conductance (AC) to evaluate the structural merits of the result partitions, instead of comparing the result partition with the labeled networks. Although we did not use the partition labels directly, we still compared the result CN with the labeled CN because the number of communities still has reference value on overlapping community networks. \begin{table}
\begin{tabular}{l l l l l} \hline \hline _Data Set_ & _Node\#_ & _CN_ & \(k\) & \(\mu\) \\ \hline Karate Club & 34 & 2 & 4.6 & - \\ Dolphins & 62 & 2 & 5.1 & - \\ Football & 115 & 12 & 10.7 & - \\ Polbooks & 105 & 3 & 8.4 & - \\ LFR500 & 500 & 3 & 15 & 0.3 \\ LFR2000 & 2000 & 4 & 30 & 0.3 \\ LFR10000\_a & 10,000 & 4 & 15 & 0.3 \\ LFR10000\_b & 10,000 & 87 & 30 & 0.3 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Main properties of data sets. \begin{table}
\begin{tabular}{l l} \hline \hline CPU & Intel(R) Core(TM) i5-9600K \\ Cores & 8 \\ Frequency & 2.4 GHz \\ Memory & 16 GB \\ Operating system & CentOS 7 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Hardware and system information. The extended modularity (\(EQ\)) is a community quality index which extends the definition of [PERSON]'s modularity to overlapping community structures. The definition of \(EQ\) is shown as follows:  
\[EQ=\frac{1}{2m}\sum_{c\in C}\sum_{i,j\in c}\frac{1}{O_{i}O_{j}}\bigg{[}A_{ij}- \frac{k_{i}k_{j}}{2m}\bigg{]} \tag{16}\]  
where \(m\) is the total number of edges in the network, and \(c\) is one of the communities. \(i\) and \(j\) are nodes belonging to Community \(c\); \(k_{i}\) and \(k_{j}\) are their respective degrees. \(A_{ij}\) is the element of the adjacency matrix which follows the condition that when node \(i\) and \(j\) are linked, the value of \(A_{ij}\) is 1, otherwise 0. \(O_{i}\) and \(O_{j}\) are the numbers of communities to which node \(i\) and \(j\) belong, respectively, and give \(EQ\) the ability to deal with the case that a node belongs to more than one community. A high value of \(EQ\) indicates a significant overlapping community structure for a particular network. The overlapping modularity index \(Q_{ov}\) is another quality function proposed by [PERSON] et al.