# A Scheme to Design Community Detection Algorithms in Various Networks
## 3 Concrete Problem Reduction
### Transmission Network
Then, \(g\) is an RSMFTN if and only if for \(u,v,w\in V\),_  
1. \(g(u,v)\geq 0\)_. (non-negativity)_
2. \(g(u,v)=0\) _if and only if_ \(u\) _and_ \(v\) _coincide. (coincidence axiom)_
3. \(g(u,v)=\infty\) _if and only if there is no path between_ \(u\) _and_ \(v\)_._
4. \(g(u,v)\leq g(u,w)+g(w,v)\)_, and the equality holds if the components containing_ \(u\) _and_ \(v\) _are connected by the cutting node_ \(w\)_._
5. _Suppose_ \(G^{\prime}\) _is a graph that is the same as_ \(G\) _except that for_ \(e^{\prime}\in E_{G^{\prime}}\) _and its counterpart_ \(e\in E_{G}\)_,_ \(|e^{\prime}|=\alpha|e|\)_. Then, for_ \(u^{\prime},v^{\prime}\in V_{G^{\prime}}\) _and their counterparts_ \(u,v\in V_{G},g(u^{\prime},v^{\prime})=\alpha g(u,v)\)_._ _In addition, if_ \(G\) _is undirected,_
6. \(g(u,v)=g(v,u)\)_. (symmetry)_  
**Example 1**. : _Some reported measurements are RSMFTNs. A well-known one is the shortest distance function (SDF), which returns the shortest distance between the given pair of nodes. Here is the proof._  
Proof. : Suppose \(u\), \(v\) and \(w\) are vertices in a directed graph \(G\). Let \(g\) denote the SDF. Since \(g(u,v)\) returns the weight sum of over the shortest path from \(u\) to \(v\), \(g(u,v)\geq 0\). Property 1 holds. Properties 2 and 3 hold by the definition of SDF. For property 4, assume \(g(u,v)>g(u,w)+g(w,v)\). Consider the paths \(p\) consisting of the shortest paths from \(u\) to \(w\) and from \(w\) to \(v\). The length of the path is \(g(u,w)+g(w,v)\), which is shorter than \(g(u,v)\). Thus, \(g(u,v)\) cannot be the length of the shortest path. We get a contradiction. Moreover, if there exists a cutting node \(w\) connecting the components containing \(u\) and \(v\) respectively, the shortest path between \(u\) and \(v\) can be split into the one from \(u\) to \(w\) and the one from \(w\) to \(v\). Thus, \(g(u,v)=g(u,w)+g(w,v)\). Therefore, property 4 holds. For property 5, suppose path \(p\) is some shortest path from \(u\) to \(v\) in graph \(G\). Then, \(l(u,v)=g(u,v)\). Let \(p^{\prime}\) denote its counterpart in \(G^{\prime}\). Since the weights in \(G^{\prime}\) are \(\alpha\) times the ones in \(G\), so is the length of path \(p^{\prime}\). That is, \(l(p^{\prime})=\alpha l(p)\). Since path \(p^{\prime}\) connects \(u^{\prime}\) and \(v^{\prime}\) in \(G^{\prime}\), we have \(g(u^{\prime},v^{\prime})\leq l(p^{\prime})\). In other words, \(g(u^{\prime},v^{\prime})\leq\alpha l(u,v)\). Similarly, consider the reverse transformation from \(G^{\prime}\) to \(G\). That is, all the weights of edges in \(G^{\prime}\) are \(\frac{1}{\alpha}\) times in the ones in \(G\). Thus, we have \(\frac{1}{\alpha}l(u^{\prime},v^{\prime})\geq g(u,v)\), which is equivalent to \(l(u^{\prime},v^{\prime})\geq\alpha g(u,v)\). Combining with \(g(u^{\prime},v^{\prime})\leq\alpha l(u,v)\), we conclude that \(g(u^{\prime},v^{\prime})=\alpha l(u,v)=\alpha g(u,v)\). Thus, property 5 holds. If \(G\) is an undirected graph, then by the commutativity and associativity of the addition operator, \(g(u,v)=g(v,u)\). In other words, the order to add the weights of the edges compounding the shortest path does not change the final result. To sum up, SDF is an RSMFTN. By RSMFTN, we get a weighted completed graph \(\mathcal{C}=(V,E_{\mathcal{C}})\) whose edge's weights are designated by RSMFTN. In Section 4, \(\mathcal{C}\) will be use to define and detect communities.