# A Scheme to Design Community Detection Algorithms in Various Networks
## 4 Communities and Detection Algorithms  
Based on the network model we discussed in Section 3, we formally define the communities and provide an algorithm to detection them. In most of the cases, a community relation is not transitive. That is, that \(A\) and \(B\) are contained in one community and so as \(B\) and \(C\) cannot imply that \(A\) and \(C\) are in one community. A typical counterexample is \"your friend's friends may not be your friends\". In addition, since only the groups of nodes having mutually strong enough relations are considered as communities, a relation strength threshold (named _community parameter_) needs to be designated. Thus, a community is defined as  
**Definition 8** (Community): _Suppose that vertex set \(W^{\mathcal{C}}\subseteq V_{\mathcal{C}}\) is a weighted complete graph \(\mathcal{C}\) derived in Section 3, \(\epsilon\in\mathbb{R}^{*}\), and \(g\) is some RSM. Then, \(W^{\mathcal{C}}\) is a community with respect to RSM \(g\) and constant \(\epsilon\) if and only if for all \((u,v)\in W^{\mathcal{C}}\times W^{\mathcal{C}}\), \(g(u,v)\leq\epsilon\). Moreover, we say \(\epsilon\) is the community parameter (CP) of \(W^{\mathcal{C}}\) with respect to \(g\). If there is no ambiguity of the choice of RSM and CP, we briefly say \(W^{\mathcal{C}}\) is a community._  
Since CP gives a threshold of the relation strength, whichever pair of nodes we choose in a community, the relation strength of the pair cannot be weaker than the ones the CP represents. Thus, for those problems considering the worst cases, the CP can be designated according to some CM with some certain threshold (in Section 3.1). Then, the inner structure of the community can be ignored since the poorest performance of the community satisfies the requirement. In other words, a community can be considered as a relatively independent entity, and the CP is a global property of it. **Remark 5**: _A small CP implies that a set of vertices is considered as community only if their mutual relations are very strong. In the extreme case, by setting CP equal to zero, each node is a community because only the self-related relation strength satisfies the requirement. In contrast, a large CP means the internal relation strength of a community is weak. If CP is greater than any edge's weights within the graph \(\mathcal{C}\), the whole vertex set \(V_{\mathcal{C}}\) is considered as a single community. To sum up, when CP decreases, the number of communities increases and reaches the maximum, the number of nodes in \(\mathcal{C}\), when \(\text{CP}=0\). If CP increases, the community number decreases and finally reduces to one when CP is greater than any edge's weights within the graph._  
**Remark 6**: _Notice that the definition is based on the set of vertices instead of the subgraph used in many other papers. In addition, the choice of communities considers the whole graph's topology rather than the local ones (this shows that the community is some higher level structure based on the original graph). Since the results might be different for various choices of the graph topology, the superscripts are used to make the description clear (for example, \(W^{\mathcal{C}}\) means \(W\) is a vertex set and graph \(\mathcal{C}\) is the working topology)._The definition of communities uses CP to give a threshold of the relation strength. That means, if the relation strength is not strong enough, the relation is ignored during the community detection. Moreover, for any pair of nodes, the definition of communities requires enough strengths of the relations in both two directions. Hence, we can remove the relations not satisfying the requirement to simplify our graph without altering the community detection result. With this trick in mind, we have the following transformation. **Definition 9** (Refinement transformation). : _Suppose \(G\) is a directed weighted graph, \(D_{G}\subseteq E_{G}\), and \(\epsilon\in\mathbb{R}^{*}\) is some CP.