# A Scheme to Design Community Detection Algorithms in Various Networks
## 5 Demonstration
### The Current Model and Klein and Randic's Effective Resistance  
In this section, we introduce Klein and Randic's effective resistance function (ERF) Zachary (1965). In addition, we show that it is an RSM. The definition of communities indicates that a certain RSM is required. We have shown that SDF is RSMFTN in Example 1, so that SDF is RSM. Although many community detection algorithms work on SDF, they may not always give a reasonable result. Intuitively, the relation of a pair of nodes will get stronger if there are more paths between them. However, the SDF does not consider this case (see Figure 4). More specifically, in SDF view, the relation will not get stronger unless a path shorter than the previous shortest path is added. To avoid this problem, we use the Klein and Randic's effective resistance function (ERF) [PERSON] (1965) to measure the relation strength, which is later proved to be an RSM. Suppose \(G\) is an indirectly connected graph. Then, \(G\) can be considered as an electrical network that all the edges are resistances with the corresponding weight values (if \(G\) is an unweighted graph, then the resistances of all edges are one). Let \(u\) and \(v\) be two vertices in the graph. Then, the effective resistance of these two vertices is  
**Definition 14**. : _Let the voltage of \(u\) be U and the one of \(v\) be 0. We can measure the current \(I\) from \(u\) to \(v\). Then, the efficient resistance \(R(u,v)\) between \(u\) and \(v\) is \(\frac{U}{I}\). Briefly, \(R(u,v)=\frac{U}{I}\)._  
[PERSON] and [PERSON] (1965) provide an algorithm to compute the resistance distance for a connected indirect weighted graph. Suppose graph \(G\) is connected. Let \(A\) be the adjacent matrix and \(D\) the diagonal degree matrix of \(G\). It is worth noting that, in a weighted undirected graph, the degree of a vertex is the sum of the weights of all its adjacent edges. Then, the Laplacian matrix \(L\) can be computed using formula \(L=D-A\). Let \(L^{\dagger}\) be the generalized inverse [PERSON] (1965) of \(L\). Then, the efficient resistance distance \(R_{i,j}\) of any pair of vertices \((i,j)\) in graph \(G\) can be obtained by  
\[R_{i,j}=L^{\dagger}_{i,j}+L^{\dagger}_{j,j}-2L^{\dagger}_{i,j},\]  
Figure 4: In both (**a**,**b**), the shortest distance between Node 1 and Node 3 is 2. Thus, in SDF’s view, the relation strengths between Node 1 and Node 3 in these two cases are identical. However, there is one more path between Node 1 and Node 3 in (**a**). Thus, intuitively, the relation between Node 1 and Node 3 in (**a**) should be stronger than the one in (**b**). and we usually call the corresponding matrix \(R\)_resistance matrix_. Then, we show that ERF is an RSM. In this case, the relations among the nodes are derived from the electron flow in the wires among the vertices. Thus, we need to consider the criteria of RSMFTN. **Lemma 4**. : _Resistance is distance. That is, the resistance satisfies the following properties:_  
1. \(R_{a,b}\geq 0\)_,_
2. \(R_{a,b}=0\Leftrightarrow a=b\)_,_
3. \(R_{a,b}=R_{b,a}\)_,_
4. \(R_{a,c}+R_{c,b}\geq R_{a,b}\)_._  
**Lemma 5**. : _Let \(x\) be a cut-point of a connected graph, and let \(a\) and \(b\) be points occurring in different components which arise upon deletion of \(x\). Then,_  
\[R_{a,b}=R_{a,x}+R_{x,b}.\]  
**Remark 9**. : _The proofs of Lemmas 4 and 5 have been given by [PERSON] and [PERSON] [36]._  
**Lemma 6**. : _RDF satisfies property 5 of RSM._  
Proof. : Suppose \(G\) is some graph and \(G^{\prime}\) is the same as \(G\) but the edges weights in \(G^{\prime}\) are all \(\alpha\) times greater than the ones in \(G\). Let \(A\) and \(A^{\prime}\) be the adjacent matrices of \(G\) and \(G^{\prime}\), respectively. Then, we have \(A^{\prime}=\alpha A\). Thus, for the corresponding degree matrices \(D\) and \(D^{\prime}\), we also have \(D^{\prime}=\alpha D\).