# An Information-Theoretic Approach for Detecting Community Structure Based on Network Representation
## 3 The Approach
### Community Evaluation Index Based on Average Mutual Information
\(Y_{j}\subseteq X_{i}\), which denotes that community \(Y_{j}\) in partition \(P_{b}\) comes from a splitting community \(X_{i}\) in partition \(P_{a}\). 3. \(X_{i}\cap Y_{j}=\varnothing\), which denotes that in partitions \(P_{a}\) and \(P_{b}\), the member nodes of \(X_{i}\) and \(Y_{j}\) are totally different; in other words, the two communities have no relations on the timeline. For Case 1, \(P\big{(}Y_{j}\big{|}X_{j}\big{)}=1\). For Case 2, \(P\big{(}Y_{j}\big{|}X_{j}\big{)}=\frac{n_{Y_{j}}}{n_{X_{i}}}\), where \(n_{X_{i}}\) and \(n_{Y_{j}}\) are, respectively, the number of member nodes of communities \(X_{i}\) and \(Y_{j}\). Figure 1: Community evolution process of top-down division. For Case 3, \(P\big{(}Y_{j}\big{|}X_{j}\big{)}=0\). From Equations (4) and (5), we can further derive that \(\omega_{ij}\cdot I\big{(}X_{i};Y_{j}\big{)}\) in Case 3 is 0, but in Case 1 and 2, the value of \(I\big{(}X_{i};Y_{j}\big{)}\) still needs to be calculated to obtain \(I_{P_{n},P_{0}}\). To achieve this, we use the following formula:  
\[ \begin{split} I\big{(}X_{i};Y_{j}\big{)}&=\sum \limits_{a}\sum\limits_{b}P\big{(}X_{i}=a,Y_{j}=b\big{)}\left[\log_{2}P\big{(}X_ {i}=a,Y_{j}=b\big{)}\right.\\ &\left.-\left(\log_{2}P(X_{i}=a)+\log_{2}P\big{(}Y_{j}=b\big{)} \right)\right]\end{split}  \tag{6}\]  
where \(a,b\in 0,1\), \(P\big{(}X_{i}=a,Y_{j}=b\big{)}=P\big{(}Y_{j}=b\big{|}X_{i}=a\big{)}\cdot P(X_ {i}=a)\). \(P(X_{i}=1)\) denotes the probability of taking a random node, and it belongs to community \(X_{i}\). Thus, \(P(X_{i}=1)=\frac{n_{X_{i}}}{n}\), where \(n_{X_{i}}\) is the number of the member nodes of community \(X_{i}\), and \(n\) is the total number of nodes of the whole network. \(P(X_{i}=0)\) denotes the probability of taking a random node, and it does not belong to community \(X_{i}\). Thus, \(P(X_{i}=0)=\frac{n-n_{X_{i}}}{n}\). \(P\big{(}Y_{j}=1\big{)}\) and \(P\big{(}Y_{j}=0\big{)}\) can be calculated in a similar way. \(P\big{(}Y_{j}=1\big{|}X_{i}=1\big{)}\) denotes the probability of taking a random member node of community \(X_{i}\), and it is also a member node of community \(Y_{j}\). Therefore,  
\[P\big{(}Y_{j}=1\big{|}X_{i}=1\big{)}=\frac{n_{Y_{j}}}{n_{X_{i}}}\]  
For Case 1 and Case 2, if a node does not belong to community \(X_{i}\), then it certainly cannot belong to community \(Y_{j}\). Therefore, \(P(Y_{j}=1\big{|}X_{i}=0)=0,P(Y_{j}=0\big{|}X_{i}=0)=1\). For a community evolution process of bottom-up cohesion, by inverting its states, it can be transformed into a top-down division community evolution process. For instance, if \(P_{bottom-up}=\{P_{0},P_{1},P_{2},\cdots,P_{N}\}\) is a bottom-up cohesion community evolution process, then \(P_{top-down}=\{P_{N},P_{N-1},\cdots,P_{2},P_{1}\}\) is its corresponding top-down division community evolution process. Thereby, the AMI value of any pair of the adjacent states of it can be calculated by the method above. Here, we do not go into detail. After the AMI value of the adjacent partitions, the entropies of each partition also need to be calculated. For partition \(P_{a}\), the entropy \(H_{P_{a}}\) of it is defined as  
\[H_{P_{a}}= -\sum\limits_{i}P(X_{i}=0)\cdot\log_{2}P(X_{i}=0)-\sum\limits_{i} P(X_{i}=1)\cdot\log_{2}P(X_{i}=1) \tag{7}\]  
where \(X_{i}\) denotes the \(i\)th community of partition \(P_{a}\). Finally, the community evaluation index \(Q_{P_{a}}\) of each state in the community evolution process \(P\) can be calculated. The state that has the largest \(Q_{P_{n}}\) is the best partition in the community evolution process.