# Detect Overlapping Community Based on the Combination of Local Expansion and Label Propagation
## 4 Experimental Result  
### Evaluation Criteria  
The normalized mutual information (\(NMI\)) is used to evaluate algorithms by comparing the similarity between the ground truth and detected community [26]. The extended \(NMI\) to evaluate the algorithm for overlapping communities was proposed by [PERSON] [14]. The membership of the node \(i\) that belongs to multiple communities can be regarded as a binary array with \(|C^{{}^{\prime}}|\) entries, which is the community number of partition \(C^{{}^{\prime}}\). The \(k\)-th entry can be represented as a random variable \(X_{k}=(\mathbf{X})_{k}\). If node \(i\) belongs to the \(k\)-th community \(C^{{}^{\prime}}_{k^{\prime}}(x_{i})k=1\); otherwise, \((x_{i})k=0\). Then, the probability distribution can be obtained by the number of nodes in \(C^{{}^{\prime}}_{k}\) and all nodes. The same holds for the random variable \(Y_{l}\) associated with the community \(C^{{}^{\prime\prime}}_{l}\) of partition \(C^{{}^{\prime\prime}}\). Due to the independence of \(X_{k}\) and \(Y_{l}\), the joint distribution and conditional distribution can be obtained. We can define the amount of information to infer \(X_{k}\) given a certain \(Y_{l}\) as \(H(X_{k}|Y_{l})=H(X_{k},Y_{l})-H(Y_{l})\), and its minimum can be defined as the conditional entropy of \(X_{k}\) with respect to all the components of \(\mathbf{Y}\) for which the average is \(H(\mathbf{X}|\mathbf{Y})_{norm}\). Finally, the extended \(NMI\) is defined as follows:  
\[N(\mathbf{X}|\mathbf{Y})=1-\frac{1}{2}[H(\mathbf{X}|\mathbf{Y})_{norm}+H( \mathbf{X}|\mathbf{Y})_{norm}], \tag{6}\]  
which is between 0 and 1. The function \(N(\mathbf{X}|\mathbf{Y})\) is equal to 1 if and only if \(X_{k}=f(Y_{l})\) for a certain \(l\), and vice versa.  
The extended \(NMI\) can only evaluate the algorithm of detecting overlapping communities at the overall level, but it cannot work at the node level. Therefore, we adopt the F-score to measure the accuracy of the algorithms at the node level [27]. The F-score is defined as the harmonic mean of _precision_ and _recall_, as follows:  
\[\text{F-score}=\frac{2\cdot precision\cdot recall}{precision+recall}, \tag{7}\]  
where _precision_ represents the proportion of the detected overlapping nodes that are true overlapping nodes, and _recall_ is defined as the number of correctly detected overlapping nodes divided by the true number of overlapping nodes. The F-score accounts for the balance between the detection quantity and quality, and it reaches its best and worst values at 1 and 0, respectively.  
The performance of algorithms can be measured by \(NMI\) and the F-score when the ground truth of the community is known. Given that the ground truth of most real world networks are not available, we adopted an extended modularity: the overlapping modularity \(Q^{e}_{ov}\) proposed in [28], as our measure. \(Q^{e}_{ov}\) takes the membership of a node as a weight for modularity. The function is as follows:  
\[Q^{e}_{ov}=\frac{1}{2m}\sum_{c}\sum_{i,j\in c}[A_{ij}-\frac{k_{i}k_{j}}{2m}] \frac{1}{\mathcal{O}_{i}\mathcal{O}_{j}}, \tag{8}\]  
where \(\mathcal{O}_{i}\) is the number of memberships that node \(i\) owns. One may argue that \(Q^{e}_{ov}\) is close to extended modularity \(Q^{ne}_{ov}\), proposed by [PERSON] et al. [29], where the degree of membership of node \(i\) in the community is the substitution of \(\mathcal{O}_{i}\) in \(Q^{e}_{ov}\).