# A Scheme to Design Community Detection Algorithms in Various Networks
## 3 Concrete Problem Reduction
### Similarity Network  
The other typical relation type is derived by attribute similarities (for example, people buying similar books might be considered as a community). In usual cases, we believe that the objects in the same community should have similar patterns. Then, we can make reasonable predictions on the community level (for example, Amazon uses this trick to recommend commodities). We name the objects _nodes_ that have similarity relations. Each node may have various _properties_ that own a few options (for example, red, blue, yellow are possible options for property color), and we name these options _cases_. The similarity network is constructed according to the similarities among the nodes. We assume that, for a certain problem, there exists a fixed number of properties with the corresponding real-valued functions (named the _similarity function_) that measure the similarity of any two options. Intuitively, the measure of similarity should not be negative, which implies that thesimilarity function is non-negative. In addition, to keep the consistency with the definition of SRSM given in Section 3.1, the function value increases while the similarity decreases. Moreover, for some objects \(A\) and \(B\), if \(A\) is similar to \(B\), then \(B\) is also similar to \(A\). Then, we formalize the preliminary idea as follows. Definition 6: Let \(P\) be some property of the nodes and \(C_{P}\) its set of possible cases, then we say \(s\) is a similarity function \(s:P\times P\rightarrow\mathbb{R}\) if for \((\gamma_{1},\gamma_{2})\in C_{P}\times C_{P}\)  
1. \(s(\gamma_{1},\gamma_{2})\geq 0\), (non-negativity)
2. \(s(\gamma_{1},\gamma_{2})=0\) if and only if \(p_{1}=p_{2}\), and (coincidence axiom)
3. \(s(\gamma_{1},\gamma_{2})=s(\gamma_{2},\gamma_{1}).\) (symmetry)  
If multiple properties \(P_{1},P_{2},\cdots\) are under the consideration, we need to define a list of similarity functions \(s_{P_{1}},s_{P_{2}},\cdots\). For convenience, we write them in a matrix form. That is, \([P_{1}\ P_{2}\cdots]\) and \([s_{P_{1}}\ s_{P_{2}}\cdots]\). Considering that it is hard to analyze a list of similarities simultaneously and the properties may be of different importance, we need a function (called _weight function_) to translate it into an index. Definition 7 (Weight function): Let \(N\) be a set of nodes having properties \(P_{1}\), \(P_{2}\ \cdots\) and \([s_{P_{1}}\ s_{P_{2}}\cdots]\) the list of the corresponding similarity functions. A function \(w\) mapping \([s_{P_{1}}\ s_{P_{2}}\cdots]\) to a non-negative function \(f\) is called a weight function. Remark 3: The choice of the weight function depends on the practical problem. A trivial weight function is just a list of weights. In more detail, suppose \([s_{P_{1}}\ s_{P_{2}}\cdots s_{P_{n}}]\) is a list of similarity functions. Let \(\alpha_{1},\alpha_{2}\cdots,\alpha_{n}\) be the weights indicating their importance (a method to determine the importance is discussed by [PERSON] and [PERSON] [32]). Then, \(w=[\alpha_{1}\ \alpha_{2}\cdots\ \alpha_{n}]\) can be a potential weight function that generates non-negative  
\[f=[\alpha_{1}\ \alpha_{2}\cdots\ \alpha_{n}]\times[s_{P_{1}}\ s_{P_{2}}\cdots s _{P_{n}}]^{T}=\sum_{i=1}^{n}\alpha_{i}\cdot s_{P_{i}}.\]  
Example 2: Suppose we take two properties \(P_{1}\) and \(P_{2}\) into account. In addition, we have the possible cases \(\gamma_{1},\gamma_{2},\gamma_{3}\) for \(P_{1}\) and \(\zeta_{1},\zeta_{2}\) for \(P_{2}\). For two nodes \(u\) and \(v\), assume \(u\) has properties \(\gamma_{1}\) and \(\zeta_{2}\), and \(v\) has properties \(\gamma_{3}\) and \(\zeta_{1}\). Let \(s_{P_{1}}\) and \(s_{P_{2}}\) be the similarity function we created for \(P_{1}\) and \(P_{2}\). If we apply the method in Remark 3 to define \(w\), we have \(w=[\alpha_{1}\ \alpha_{2}]\). Thus, \(f(s,t)=\alpha_{1}s_{P_{1}}(s\text{'s}\ P_{1},t\text{'s}\ P_{1})+\alpha_{2}s_{P_{ 2}}(\text{'s}\text{'s}\ P_{2},t\text{'s}\ P_{2})\).