# A Scheme to Design Community Detection Algorithms in Various Networks
## 4 Communities and Detection Algorithms
: _With the configuration in Lemma 2, \(A^{\mathcal{C}}\subseteq V_{\mathcal{C}}\) is a community if and only if \(eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]\) is complete._  
Proof. : \((\Rightarrow)\) Suppose \(A^{\mathcal{C}}\) is a community. Pick vertices \(u\) and \(v\) in \(A^{\mathcal{C}}\) arbitrary. Since \(A^{\mathcal{C}}\) is a community, then all the relations will be reserved after applying the refinement transformation. Moreover, since \(\mathcal{C}[A^{\mathcal{C}}]\) is complete, then \(u\leftrightarrow v\in E_{\mathcal{C}[A^{\mathcal{C}}]}\). Thus, \((u,v)\in R_{e}(E_{\mathcal{C}[A^{\mathcal{C}}]})\). Since we pick \(u\) and \(v\) arbitrary in \(A^{\mathcal{C}}\), there is an edge between any pair of nodes in \(eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]\). Hence, \(eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]\) is complete. \((\Leftarrow)\) Suppose \(eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]\) is complete. Then, \(\forall(u,v)\in A^{\mathcal{C}}\times A^{\mathcal{C}}\), \((u,v)\in R_{e}(E_{\mathcal{C}[A^{\mathcal{C}}]})\). Since \(eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]\) is complete, all the relations in \(E_{\mathcal{C}[A^{\mathcal{C}}]}\) are reserved after applying the refinement function. Therefore, \(A^{\mathcal{C}}\) is a community. It is easy to check that all single nodes can be considered as a community because they relate to themselves trivially, and the RSM is zero. However, this kind of result does not follow our intuition since the community should be some set of nodes. The definition of the maximal community tackles this problem. For a better understanding of the definition, we introduce a theorem first. **Theorem 2**. : _With the configuration in Lemma 2, let \(A^{\mathcal{C}}\subseteq B^{\mathcal{C}}\subseteq V_{\mathcal{C}}\). If \(B^{\mathcal{C}}\) is a community, then so is \(A^{\mathcal{G}}\)._  
Proof. : Since \(B^{\mathcal{C}}\) is a community, then, by Theorem 1, \(eeg_{(g,e)}(\mathcal{C})[B^{\mathcal{C}}]\) is complete. In addition, since \(A^{\mathcal{C}}\subseteq B^{\mathcal{C}}\), then, by Lemma 1, \(eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]\) is a subgraph of \(eeg_{(g,e)}(\mathcal{C})[B^{\mathcal{C}}]\). Moreover, pick \(u,v\in A^{\mathcal{C}}\) arbitrary. Then, \(u,v\in B^{\mathcal{C}}\) as well. Notice that \(eeg_{(g,e)}(\mathcal{C})[B^{\mathcal{C}}]\) is complete. Thus, the relation \(u\leftrightarrow v\in E_{adj(G,g)[B^{\mathcal{C}}]}\) is reserved, which implies \((u,v)\in E_{eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]}\). Thus, \(eeg_{(g,e)}(\mathcal{C})[A^{\mathcal{C}}]\) is complete. Thus, \(A^{\mathcal{C}}\) is a community as well. Theorem 2 shows that, if \(B^{\mathcal{C}}\) can be considered as a community with respect to some RSM and CP, then all the subsets of \(B^{\mathcal{C}}\) can be considered as a community. This observation leads to the definition of maximal community. **Definition 11** (Maximal community). : _With the configuration in Lemma 2, let \(A^{\mathcal{C}}\) be a subset of \(V_{\mathcal{C}}\). Then, \(A^{\mathcal{C}}\) is a maximal community if and only if_  
1. \(A^{\mathcal{C}}\) _is a community, and_
2. _There is no_ \(B^{\mathcal{C}}\subseteq V_{\mathcal{C}}\) _such that_ \(B^{\mathcal{C}}\) _is a community and_ \(A^{\mathcal{C}}\subsetneq B^{\mathcal{C}}\)_._  
With the maximal community definition in mind, we introduce an algorithm to detect them if RSM and CP are specified. For easier explanation, we define problems A and B as this:  
**Definition 12** (Problem A). : _With the configuration in Lemma 2, find all the maximal communities in \(\mathcal{C}\) (the set of the maximal communities is denoted \(\Psi\))._  
**Definition 13** (Problem B). : _Given the effective edge graph \(eeg_{(g,e)}(C)\), find the all the maximal cliques in \(eeg_{(g,e)}(C)\) (the set of the maximal cliques is denoted by \(\Phi\))._  
The following theorem shows the equivalence of problems A and B. **Theorem 3**. : _With the configuration in Lemma 2. Let \(A^{\mathcal{C}}\) be a subset of \(V_{\mathcal{C}}\).