# Large Scale Community Detection Using a Small World Model
## 6 Implementation  
### Metrics for Evaluation Performance  
The following evaluation metrics have been considered for measuring performance of the proposed algorithm. * **Normalized Mutual Information (\(NMI\)):** NMI is a suitable measure to compare the quality of different community partitions. It can be evaluated with the help of confusion matrix (\(CM\)), where each row corresponds to the community, present in the real partition and each column corresponds to the community, detected through the proposed algorithm. Confusion matrix has been obtained based on the number of communities and community memberships for each node, which is available as ground truth in the datasets [34; 35]. Each element in the confusion matrix \(CM_{ij}\) represents the number of vertices in \(i\)th real community, which is also present in \(j\)th detected community. \(NMI\) of the detected partition may be formulated as: \[NMI(X,Y)=\frac{-2\sum_{i=1}^{n_{X}}\sum_{j=1}^{n_{Y}}CM_{ij}log(\frac{CM_{ij} CM_{j}}{CM_{i}\in CM_{j}})}{\sum_{i=1}^{n_{X}}CM_{i}log(\frac{CM_{i}}{CM})+\sum_{j=1}^{ n_{Y}}CM_{i}log(\frac{CM_{j}}{CM})},\] (12) where \(X\) and \(Y\) are the community partition structure corresponding to ground truth and detected structure, respectively. \(CM_{i}\) and \(CM_{j}\) indicate the communities in true and detected community partition, respectively. * **Modularity (\(Q\)):** Modularity is a metric used to quantify the quality of community partition. This measure is proposed by [PERSON] and [PERSON] [13]. It is defined as the difference between the number of edges existing inside the communities and the number of edges, which would have been present in a random assignment in the network with similar degree distribution. The expected number of edges between \(i\) and \(j\) with degree \(d_{i}\) and \(d_{j}\), respectively, is \(d_{i}d_{j}/2\). Modularity value for a given partition \(P=\{c_{1},c_{2},.....c_{k}\}\) in the graph \(G=(V,E)\) is defined as follows [36]: \[Q=\frac{1}{2E}\sum_{C_{i}\in P,(1\leq l\leq k)}\sum_{i,j\in C_{l}}\left(A_{ij} -\frac{d_{i}d_{j}}{2E}\right).\] (13)
* **F-Measure:** F-measure is a metric used to find the accuracy of the proposed algorithm when the ground truth about the communities are available in the dataset. It is the harmonic mean of precision and recall, where precision and recall can be obtained from the confusion matrix obtained from the experiment. Confusion matrix for community detection has been described inTable 1. In this work, all pairs of nodes are considered to get the value of \(a\), \(b\), \(c\) and \(d\) for each dataset considered, where  
* \(a\) = number of pairs, in the same community in ground truth and assigned in same community after community detection. It is treated as True Positive (\(TP\)). * \(b\) = number of pairs, belonging in different communities but assigned in same community after community detection. It is treated as False Positive (\(FP\)). * \(c\) = number of pairs, belonging in same communities but assigned in different communities after community detection. It is treated as False Negative (\(FN\)). * \(d\) = number of pairs, belonging to different communities and assigned in different communities after community detection. It is treated as True Negative (\(TN\)). Precision can be defined as follows:  
\[Precision=\frac{TP}{TP+FN}=\frac{a}{a+c} \tag{14}\]  
Recall can be defined as follows:  
\[Recall=\frac{TP}{TP+FP}=\frac{a}{a+b} \tag{15}\]  
F-measure can be defined as follows:  
\[F-measure=\frac{2\times Precision\times Recall}{Precision+Recall}. \tag{16}\]  
* **Execution Time**: A major issue in community detection algorithms is to uncover communities in a reasonable amount of time. In this paper, performance of different algorithms has been measured in terms of execution time. Execution time includes only CPU running time without considering the external time factor. Execution time for all community detection algorithms has been measured in machines with the i7 processor with 3.4 GHz clock speed. Running times have been measured in units of seconds.