# A Scheme to Design Community Detection Algorithms in Various Networks
## 4 Communities and Detection Algorithms
The refinement transformation is defined like this:_  
\[R_{\epsilon}(D_{G}):=\{(u,v)\in D_{G}:|(u,v)|\leq\epsilon\wedge|(v,u)|\leq \epsilon\}.\]  
_In addition, all the edges' weights are set to one after applying the transformation._  
**Remark 7**. : _For convenience, the relations \((u,v)\) and \((v,u)\) are together denoted by \(u\leftrightarrow v\). In this case, the weight is not applicable._  
The definition of refinement transformation shows that, if some edges \((u,v)\) are in \(R_{\epsilon}(D_{G})\), then so is \((v,u)\). Moreover, the weights become unnecessary since they all equal one. Therefore, in \(R_{\epsilon}(D_{G})\), there is no need to consider the directions and weights of the edges anymore. Thus, from now on, \(R_{\epsilon}(D_{G})\) is thought of as a set of undirected unweighted edges. Moreover, if \((u,v)\in R_{\epsilon}(D_{G})\), then we say the relation between \(u\) and \(v\) is reserved, or, in brief, \(u\leftrightarrow v\) is reserved. In fact, the refinement transformation is a higher order function that applies a Boolean function to all the edges. The Boolean function checks whether the corresponding relation is strong enough for consideration in the community detection. Thus, for a certain refinement transformation, the reservation of the relation depends on the strength of the relation itself rather than the topology that contains it. **Lemma 1**. : _Suppose \(G\) is some directed graph. If \(F_{1}\subseteq F_{2}\subseteq E_{G}\), then \(R_{\epsilon}(F_{1})\subseteq R_{\epsilon}(F_{2})\)._  
Proof. : Pick \((u,v)\in R_{\epsilon}(F_{1})\) arbitrary. Thus, \(u\leftrightarrow v\) is in \(F_{1}\) and reserved after applying the refinement transformation. Since \(F_{1}\subseteq F_{2}\), then \(u\leftrightarrow v\in F_{2}\). Thus, \((u,v)\in R_{\epsilon}(F_{2})\). Then, the complete graph \(\mathcal{C}\) developed in Section 3 can be simplified to an undirected unweighted graph whose edges indicate bidirectional relations strong enough to construct communities. **Definition 10** (Effective edge graph). : _Suppose \(\mathcal{C}\) is some complete weighted directed graph derived in Section 3, \(g\) is some RSM, and \(\epsilon\) is some CP. Then, the effective edge graph (denoted by \(eeg_{(g,\epsilon)}(\mathcal{C})\)) is \((V_{\mathcal{C}},R_{\epsilon}(E_{\mathcal{C}}))\). Moreover, suppose the vertices set \(A^{\mathcal{C}}\) is a subset of \(V_{\mathcal{C}}\). The full subgraphs of \(eeg_{(g,\epsilon)}(\mathcal{C})\) over \(A^{\mathcal{C}}\) are denoted by \(eeg_{(g,\epsilon)}(\mathcal{C})[A^{\mathcal{C}}]\)._  
**Lemma 2**. : _Let \(g\) be some RSM, \(\epsilon\in\mathbb{R}^{*}\) some CP and \(\mathcal{C}\) some complete weighted graph derived in Section 3. Assume that \(W^{\mathcal{C}}\subseteq V_{\mathcal{C}}\). Then, the vertices set \(W^{\mathcal{C}}\) is a community if and only if, for all \(u,v\in W^{\mathcal{C}}\), \(u\leftrightarrow v\) is reserved after applying the refinement transformation._  
Proof. : The refinement transformation will remove all the relations that cannot be used in a community structure. In other words, if all relations are reserved after applying refinement transformation, the relation in any pair of nodes is strong enough. This is exactly what the definition of communities requires. Thus, \(W^{\mathcal{C}}\) is a community. On the other hand, if \(W^{\mathcal{C}}\) is a community, the relation (in both directions) in any pair of nodes should be strong enough. Thus, all of them are reserved after applying the refinement transformation. **Lemma 3**. : _Any full subgraph of a complete graph is again complete._  
Proof. : Suppose \(S\) is a full subgraph of \(C_{n}\) for some \(n\). Then, for arbitrary vertices \(u\) and \(v\) in \(S\), edge \((u,v)\in E_{C_{n}}\). Thus, by the definition of full subgraphs, \((u,v)\in E_{S}\). That is, there is an edge in an arbitrary pair of nodes in \(S\). Thus, \(S\) is a complete graph. **Theorem 1**.