# MINC-NRL: An Information-Based Approach for Community Detection
## 3 Mutual Information between Network and Communities  
### Original Definition  
It is well known that the key part of community detection approach is to design an effective community evaluation index. A well-defined community evaluation index should satisfy the following: The better the given partition is, the higher its value is. Thus, when an optimal partition is given, the index reaches its maximum value. The mutual information between network and communities (or MINC for short) is a community evaluation index defined in a view of informatic theory. Mutual information is a measure of the mutual dependencies of two random variables, i.e., the amount of information that one random variable contains about the other. If the two variables refer to networks and communities, respectively, we can obtain a definition of the mutual information between network \(X\) and community partition \(C\) as follows:  
\[MINC(X,C)=H(X)-H(X|C) \tag{1}\]  
Note that \(X\) and \(C\) are variables related to the structure of the network and community ownership of nodes, which will be specifically defined in the following section. \(H(X)\) denotes the entropy of network \(X\), which can be defined as the number of bits on average to describe the network. \(H(X|C)\) denotes the conditional entropy of \(X\) and \(C\), which quantifies the amount of information needed to describe \(X\) given that the value of the known variable \(C\). Based on the perspective of information, the following assertions are made:  
1. \(H(X)\) is determined only by the connectivity of nodes of network. 2. For a certain network, the better a given partition of it is, the less the amount of information is needed to describe the network. This results in a smaller value of \(H(X|C)\) and a larger value of \(MINC(X,C)\). Therefore, \(MINC\) can be used as a community evaluation index to quantify the merits of a partition. The value of \(H(X)\) and \(H(X|C)\) can be calculated by:  
\[ \begin{split} H(X)&=-\sum_{x\in X}p(x)\log p(x)\\ &=-\big{[}p(X=1)\log p(X=1)\big{]}-\big{[}p(X=0)\log p(X=0)\big{]} \end{split}  \tag{2}\]\[H(X|C)= -\left[p(C=1)\cdot p(X=1|C=1)\log p(X=1|C=1)\right] \tag{3}\] \[-\left[p(C=1)\cdot p(X=0|C=1)\log p(X=0|C=1)\right]\] \[-\left[p(C=0)\cdot p(X=1|C=0)\log p(X=1|C=0)\right]\] \[-\left[p(C=0)\cdot p(X=0|C=0)\log p(X=0|C=0)\right]\]  
The above equations are derived from the general definition of the mutual information. As for how to calculate the probability distributions (e.g., \(p(C=1)\)), further definition is needed, and here comes the core idea of the MINC approach. First, we consider the random variables \(X\) and \(C\). \(X\) is a variable related to the structure of the network, which can be defined at the micro level of each pair of nodes in the network:  
\[X= \begin{cases}1&\text{if the nodes are adjacent}\\ 0&\text{if the nodes are not adjacent}\end{cases} \]  
In the same way, the variable for community partition \(C\) of the network can be defined as:  
\[C= \begin{cases}1&\text{if the nodes are in the same community}\\ 0&\text{if the nodes are not in the same community}\end{cases} \]  
Then by considering the connectivity and community ownership of nodes, the probability distributions can be defined as:  
\[p(X=1) =\frac{m}{t} \tag{4}\] \[p(X=0) =1-\frac{m}{t}\] (5) \[p(C=1) =\frac{\pi}{t}\] (6) \[p(C=0) =1-\frac{\pi}{t}\] (7) \[p(X=1|C=1.) =\frac{\theta}{\pi}\] (8) \[p(X=0|C=1.) =1-\frac{\theta}{\pi}\] (9) \[p(X=1|C=0.) =\frac{m-\theta}{t-\pi}\] (10) \[p(X=0|C=0.) =1-\frac{m-\theta}{t-\pi} \tag{11}\]  
In the above equations, \(t\) denotes the number of possible node pairs, which is constantly \(\binom{n}{2}\) for a particular network with \(n\) nodes. \(m\) is the number of adjacent node pairs, which is equal to the number of edges. \(\pi\) is the number of node pairs in same community. \(\theta\) is the number of adjacent node pairs in the same community. By using the above definitions, the mutual information between a particular network and one of its partitions can be calculated.