# MINC-NRL: An Information-Based Approach for Community Detection
## 3 Mutual Information between Network and Communities
### Extending the Definition of MINC for Overlapping Communities  
The original definition of \(MINC\) is not compatible with overlapping communities. This is due to the fact that it divides the edges of a network into two types: intra-community edges and inter-community edge to calculate the probability distributions by counting the number of them. For instance, \(p(X=1|C=1)=\frac{\theta}{\pi}\) denotes the probability that a pair of randomly selected nodes in the same community have an edge between them in network \(X\). The value of this probability is equal to the number of intra-community edges divided by the combinatorial number of selecting a pair of nodes in the same community.  
However, in the case of overlapping communities, an edge can be ambiguous, which can hardly be defined as being inside or outside the community. As shown in Figure 1, edge \(a\) is an internal edge in community \(A\), and edge \(b\) is an inter-community edge between communities \(A\) and \(B\). However, edge \(c\) can be considered either as an internal edge of community \(A\) or as an edge between communities \(A\) and \(B\) because the nodes at both ends of such an edge can either belong to the same community \(A\) or to two different communities \(A\) and \(B\). This makes it difficult to count the number of edges and calculate the probability distributions in Equations (4)-(11).  
This problem can be solved by appending definitions for the ambiguous edges in overlapping communities. A possible solution is that for such an ambiguous edge, it is counted as 0.5 intra-community edges and 0.5 inter-community edges. However, such a solution is not reasonable in some more complicated cases. Consider edges \(m\) and \(n\) in Figure 2:  
For edge \(m\):  
* In one case, it can be regarded as an internal edge (in community \(C\));
* In two cases, it can be regarded as an inter-community edge (between communities \(A\) and \(C\) and between communities \(B\) and \(C\)). For edge \(n\):
* In two cases, it can be regarded as an internal edge (in community \(B\) and in community \(C\));
* In three cases, it can be regarded as an inter-community edge (between communities \(A\) and \(B\), between communities \(B\) and \(C\), and between communities \(A\) and \(C\)).  
Figure 1: Ambiguous edges between two communities.  
Figure 2: Ambiguous edges among three communities.  
The two edges \(m\) and \(n\) are in obviously different conditions, but if using the solution above, they will both be counted as 0.5 intra-community edges and 0.5 inter-community edges. Therefore, a more rigorous method is proposed to count the number of edges within and between communities, when there is overlap between communities. The number of edges in the same community is defined as:  
\[\theta=\sum_{l\in M}p(l_{a},l_{b}) \tag{12}\]  
where \(l_{a}\) and \(l_{b}\) denote the ends of edge \(l\), and \(M\) denotes the set of all the edges of the network. \(p(r,s)\) is defined as:  
\[p(r,s)=\frac{\sum_{R_{i}\in R}\sum_{S_{j}\in S}\delta_{R_{i}S_{j}}}{|R|\cdot|S|} \tag{13}\]  
where \(R\) and \(S\) denote the community sets to which node \(r\) and \(s\) belong, respectively. \(R_{i}\) and \(S_{j}\) are the \(i\)-th and \(j\)-th communities in \(R\) and \(S\), respectively. \(\delta_{R_{i}S_{j}}\) is the Kronecker delta, which equals to 1 if \(R_{i}=S_{j}\) and 0 otherwise. \(|R|\) and \(|S|\) are the numbers of communities in \(R\) and \(S\), respectively.  
For the number of node pairs \(\pi\) in same community, it can be calculated in the same way by replacing \(l\in M\) with \(l\in L\), where \(L\) denotes the edge set formed by selecting any pair of two nodes in the network:  
\[\pi=\sum_{l\in L}p(l_{a},\,l_{b}) \tag{14}\]  
After appending the above definitions for counting the ambiguous edges in overlapping communities, the \(MINC\) index is able to be applied to overlapping community partitions.