# An Information-Theoretic Approach for Detecting Community Structure Based on Network Representation
## 3 The Approach  
### Community Evaluation Index Based on Average Mutual Information  
The community evaluation index is used to measure the quality of a partition for a specific network. The approach uses a community evaluation index based on average mutual information (AMI) to measure the stability of each state of a bottom-up cohesion or top-down division community evolution process by calculating the average mutual information and information entropy of adjacent states, which finally leads to the optimal community partition of such a process. Definition 1: Community evolution process of top-down division. In a community evolution process: \(P=P_{0},P_{1},P_{2},\cdots,P_{N}\); each state is a community partition. If adjacent partitions \(P_{n}\) and \(P_{n+1}\) satisfy  
\[\forall Y_{j}\in P_{n+1},\exists X_{i}\big{(}X_{i}\in P_{n}\to Y_{j}\subseteq X _{i}\big{)} \tag{1}\]  
where \(X_{i}\) and \(Y_{j}\) denote communities in a partition, \(n\) is an integer, and \(n<N\), then community evolution process \(P\) is named a top-down division community evolution process. In other words, partition \(P_{n+1}\) comes from \(P_{n}\) where one or several of the communities split into more communities. Figure 1 shows an example of community evolution process of top-down division. Definition 2: Community evolution process of bottom-up cohesion. Correspondingly, if adjacent partitions \(P_{n}\) and \(P_{n+1}\) satisfy  
\[\forall Y_{j}\in P_{n+1},\exists X_{i}\big{(}X_{i}\in P_{n}\to X_{i} \subseteq Y_{j}\big{)} \tag{2}\]then community evolution process \(P\) is named a community evolution process of bottom-up cohesion. In other words, partition \(P_{n+1}\) comes from \(P_{n}\), where some of the communities merge into one._  
For a partition \(P_{n}\) in a bottom-up cohesion or top-down division community evolution process, the community evaluation index \(Q_{P_{n}}\) based on AMI is defined as  
\[Q_{P_{n}}=max\big{(}I_{P_{n-1},P_{n}},I_{P_{n},P_{n+1}}\big{)}+\frac{1}{k\cdot H _{P_{n}}} \tag{3}\]  
where \(I_{P_{n-1},P_{n}}\) and \(I_{P_{n},P_{n+1}}\) are the AMI value between the partition of current state with that of the previous state, and that of the next state, respectively. \(H_{P_{n}}\) is the entropy of \(P_{n}\), and \(k\) is the scale factor. Better results can be achieved in our experiments when setting \(k\) to the total number of nodes \(N\) of the target network. The community evaluation index \(Q_{P_{n}}\) can be used to measure the stability of each state. This is because when a state has a high AMI-value with its adjacent states and a low entropy, it is considered instantaneously stable on the category of information theory. Since the essence of a community is a node set and the essence of a partition is a set of communities, the AMI value \(I_{P_{n},P_{n}}\) between two partitions \(P_{a}\) and \(P_{b}\) (\(a\
eq b\)) can be calculated using the AMI formula between sets, namely,  
\[I_{P_{a},P_{b}}=\sum_{i}\sum_{j}\omega_{ij}\cdot I\big{(}X_{i};Y_{j}\big{)} \tag{4}\]  
where \(X_{i}\in P_{a}\), which denotes the \(i\)th community in partition \(P_{a}\); \(Y_{j}\in P_{b}\), which denotes the \(j\)th community in partition \(P_{b}\). \(I\big{(}X_{i};Y_{j}\big{)}\) denotes the mutual information between communities \(X_{i}\) and \(Y_{j}\), and \(\omega_{ij}\) denotes the relevancy degree between communities \(X_{i}\) and \(Y_{j}\), which is defined as  
\[\omega_{ij}=P\big{(}X_{i},Y_{j}\big{)}=P\big{(}Y_{j}\big{|}X_{i}\big{)}\cdot P (X_{i}) \tag{5}\]  
Consider a top-down division community evolution process \(P=P_{0},P_{1},P_{2},\cdots,P_{N}\). Since states of such a process are essentially partitions, there are only three possible cases for a pair of random communities \(X_{i}\in P_{a}\), \(Y_{j}\in P_{b}\), \(a<b\):  
1. \(X_{i}=Y_{j}\), which denotes that in partitions \(P_{a}\) and \(P_{b}\), the member nodes of communities \(X_{i}\) and \(Y_{j}\) are totally the same. \(X_{i}\) and \(Y_{j}\) are actually the same community, which remain unchanged in two states. 2.