# A Scheme to Design Community Detection Algorithms in Various Networks
## 4 Communities and Detection Algorithms
Then, \(A^{\mathcal{C}}\) is a maximal community if and only if \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\) is a maximal clique in graph \(\text{eef}_{(g,\epsilon)}(\mathcal{C})\). Therefore, \(\Psi=\Phi\)._  
Proof. : \((\Rightarrow)\) Suppose \(A^{\mathcal{C}}\) is a maximal community. Since \(A^{\mathcal{C}}\) is a community, then \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\) is complete (Theorem 1). Thus, it is a clique. Assume \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\) is not maximal. Then, there exists some vertices set \(B^{\mathcal{C}}\) such that \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\subsetneq\text{eef}_ {(g,\epsilon)}(\mathcal{C})[B^{\mathcal{C}}]\) and \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[B^{\mathcal{C}}]\) is complete. Thus, \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]=\text{eef}_{(g, \epsilon)}(\mathcal{C})[B^{\mathcal{C}}]\). Thus, we have \(A^{\mathcal{C}}\subsetneq B^{\mathcal{C}}\). In addition, since \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[B^{\mathcal{C}}]\) is complete, \(B^{\mathcal{C}}\) is a community. Hence, \(A^{\mathcal{C}}\) cannot be a maximal community, which is a contradiction. \((\Leftarrow)\) Suppose \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\) is a maximal clique. Since \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\) is complete, then \(A^{\mathcal{C}}\) is a community (Theorem 1). Assume \(A^{\mathcal{C}}\) is not maximal; then, there exists some community \(B^{\mathcal{C}}\) such that \(A^{\mathcal{C}}\subsetneq B^{\mathcal{C}}\). Then, \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[B^{\mathcal{C}}]\) is complete. Moreover, we have \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\subsetneq\text{eef}_ {(g,\epsilon)}(\mathcal{C})[B^{\mathcal{C}}]\) by Lemma 1. Therefore, \(\text{eef}_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\) cannot be maximal, which is a contradiction. **Remark 8**. : _The Bron-Kerbosch algorithm [33] is a well-known algorithm to find maximal cliques. Then, by Theorem 3, we can reduce problem \(A\) to problem \(B\) and apply the Bron-Kerbosch algorithm to find \(\Phi\) that equals \(\Psi\). Remarkably, the Bron-Kerbosch algorithm in general has an exponential complexity, which limits the capability of Algorithm 1 over a large scale network. However, in practice, \(\text{eeg}_{(g,\epsilon)}(\mathcal{C})\) is mostly likely to be sparse, in which case a linear complexity can be achieved [34]._  
Figure 3 shows the relationships among the important concepts and transformations introduced. Suppose \(g\) is some RSM, \(\epsilon\) some CP and \(\mathcal{C}\) some complete weighted graph derived in Section 3. Index the vertices of \(\mathcal{C}\) from \(1\) to \(|V_{\mathcal{C}}|\). Then, we have the following algorithm:  
```
for\((i,j)\in V_{\mathcal{C}}\times V_{\mathcal{C}}\) where \(i\leq j\)do if\(g(i,j)\leq\epsilon\ \ \&\ \ g(j,i)\leq\epsilon\)then \(EEG[i,j]=1\) else \(EEG[i,j]=0\) endif endfor Set of Maximal Communities \(\Phi\ \leftarrow\) Bron-Kerbosch algorithm (EEG)
```  
Figure 3: The concept graph of the algorithm.