# A Scheme to Design Community Detection Algorithms in Various Networks
## 3 Concrete Problem Reduction
### Transmission Network
In particular, relations of a transmission network should not cancel each other out. Thus, the SRSM is non-negative. In addition, the self-related relation is the strongest as the transmission speed is unbounded. Intuitively, all SRSMs should have the same value  
Figure 1: A typical speed function of time associated with node pair \((u,v)\). in this case and so are assigned value zero. In addition, the relation strength will get weaker if the function value increases. To sum up, we have  
**Definition 4** (Special relation strength measurement (SRSM)). : _For a network, let \(s\) be a real-valued function defined on the set of node pairs that are directly connected by media. Then, \(s\) is an SRSM if_  
1. \(s(u,v)\geq 0\)_, and_
2. \(s(u,v)=0\) _if and only if_ \(u=v\)_._  
**Remark 2**. : _By Remark 1, for a pair of nodes \((u,v)\), \(f_{(u,v)}(t)\
eq f_{(v,u)}(t)\) in general. Thus, for SRSMs, we also have \(s(u,v)\
eq s(v,u)\)._  
By SRSM, the transmission network is reduced to a graph model. Specifically, the nodes are represented by the vertices. Two nodes directly connected by the medium are linked by an edge of the weight given by the SRSM. In general, the graph is directed. If \(s(u,v)=s(v,u)\) for all applicable node pairs, the graph can be considered undirected. Let \(G=(V_{G},E_{G})\) be a weighted graph with vertex set \(V_{G}\) and edge set \(E_{G}\). For edge \(e\in E_{G}\), let \(|e|\) denote its weight. If there is no ambiguity, we abbreviate \(V_{G}\) and \(E_{G}\) to \(V\) and \(E\). In the sequel, _node_ and _vertex_ are used alternatively without considering the difference and thus _relations_ and _edges_ also. SRSM only considers the direct material transmission of two nodes that cannot be redirected by the third one. However, in practice, the redirection happens frequently (such as in express service and internet data transmission). To overcome the deficiency of SRSM, we derive a more general relation strength measurement named _relation strength measurement for transmission network (RSMFTN)_. For the same reason, an analytic expression of RSMFTN cannot be given until a concrete problem is designated. However, a reasonable RSMFTN must hold several key properties. First of all, the relation between any pair of nodes should be measurable. That is, the domain of RSMFTN is \(V\times V\). The properties of SRSM should be inherited. Then, RSMFTN is also non-negative and \(RSMFTN(u,v)=0\) if and only if \(u=v\). In addition, there is no relation between the nodes belonging to two disconnected components. In contrast to the coincidence of two nodes, it is reasonable to set the value of \(RSMFTN\) to infinity (\(\infty\)), an element greater than any real number. A closer-to-zero \(RSMFTN(u,v)\) implies a stronger relation between \(u\) and \(v\). Consider a linear graph (see Figure 2a). The points sent by \(u\) and received by \(v\) must be retransmitted by \(w\). Thus, the difficulty to transfer points from \(u\) to \(v\) is not less than the one from \(u\) to \(v\) through \(w\). Notice that the difficulty for nodes to receive and send points has been included in SRSM and so indicated in the edge's weights. Hence, the equality should hold. In other words, \(RSMFTN(u,v)=RSMFTN(u,w)+RSMFTN(w,v)\) if \(w\) is a cutting node on the path from \(u\) to \(v\). To add on, the transmission difficulty does not increase if we add another node \(s\) for redirection (see Figure 2b). Thus, in general, we have \(RSMFTN(u,v)\leq RSMFTN(u,w)+RSMFTN(w,v)\). In addition, the relation strength of a pair of nodes should be proportional to the weights of the edges taken into account. In addition, for an undirected graph, \(\forall(u,v)\in V\times V\), \(RSMFTN(u,v)=RSMFTN(v,u)\). To sum up, RSMFTN is defined as  
Figure 2: Two nodes (\(u\) and \(v\)) connected by a single path (**a**) and two parallel paths (**b**). **Definition 5** (Relation strength measurement for transmission network (RSMFTN)). : _Suppose \(G\) is a graph and \(g:V\times V\rightarrow\mathbb{R}\cup\{\infty\}\) a function.