# Fuzzy Random Walkers with Second Order Bounds: An Asymmetric Analysis
## 4 Family of Walktrap Heuristics
### Markov Walktrap and Chebyshev Walktrap  
Both the Markov Walktrap, proposed in [10], and Chebyshev Walktrap, introduced in this article, algorithms improve Fuzzy Walktrap in two ways. The first is that during the walking phase the Random Walker has two optional safeguards against being confined inside a community for too long. Both of these safeguards are common for Markov Walktrap and Chebyshev Walktrap. The second improvement is that, during the clustering phase, two communities may not merge if the path lengths within the resulting community exceed a certain threshold. The latter is based on first order statistics for the Markov Walktrap and on second order statistics for the Chebyshev Walktrap.  
Regarding the control of community merge, for community \(V_{k}\), the mean path cost \(\pi_{k}\) is the sum of the individual edge costs  
\[\pi_{k}\stackrel{{\triangle}}{{=}}\frac{1}{\left|V_{k}\right|}\, \sum_{e_{j}\in V_{k}}\delta\big{(}e_{j}\big{)}, \tag{26}\]  
and, therefore, is also a random variable. By linearity of expectation,  
\[\mathrm{E}\left[\pi_{k}\right]\;=\;\mathrm{E}\left[\frac{1}{\left|V_{k} \right|}\,\sum_{e_{j}\in V_{k}}\delta\big{(}e_{j}\big{)}\right]\;=\;\frac{ \left|E_{k}\right|}{\left|V_{k}\right|}\,\mathrm{E}\left[\delta\big{(}e_{j} \big{)}\right]. \tag{27}\]  
Moreover, as \(\delta\big{(}e_{j}\big{)}\) are independent,  
\[\mathrm{Var}\left[\pi_{k}\right]\;=\;\mathrm{Var}\left[\frac{1}{\left|V_{k} \right|}\,\sum_{e_{j}\in V_{k}}\delta\big{(}e_{j}\big{)}\right]\;=\;\frac{ \left|E_{k}\right|}{\left|V_{k}\right|^{2}}\,\mathrm{Var}\left[\delta\big{(}e _{j}\big{)}\right]. \tag{28}\]  
In the general case, the distribution of \(\delta\big{(}e_{j}\big{)}\) is unknown, for specific choices of \(h\), it can be computed or estimated. Alternatively, since \(\pi_{k}\) is a sum of random variables, its distribution may be known for certain special cases. For instance, the sum of independent Poisson random variable is another Poisson random variable. In addition, the sum of independent binomial random variables is also a binomial random variable. Finally, the sum of a large number of independent random variables with finite variance is a normal random variable according to the Central Limit Theorem. Nonetheless, in this article, no such assumptions were made and the expected value and the variance of \(\pi_{k}\) were approximated by the Jensen inequality and the delta method, respectively, in Equations (13) and (18).  
Since \(\pi_{k}\) is by construction positive, the Markov inequality can be applied. Therefore,  
\[\mathrm{prob}\left\{\pi_{k}\;\geq\;\gamma_{0}\right\}\;\leq\;\frac{\mathrm{E }\left[\pi_{k}\right]}{\gamma_{0}} \tag{29}\]  
or, equivalently,  
\[\mathrm{prob}\left\{\pi_{k}\;\geq\;\frac{\mathrm{E}\left[\pi_{k}\right]}{ \gamma_{0}}\right\}\;\leq\;\gamma_{0}. \tag{30}\]  
If, for a threshold \(\alpha_{0}\in(0,1)\)\(\pi_{k}\) exceeds \(\alpha_{0}\gamma_{0}\), then that community is excluded from merging for an iteration provided it has at least \(\xi_{0}\) vertices. This is a first order probabilistic safeguard preventing almost formed communities from losing their coherence.  
On similar grounds, a second order such safeguard can be built on the Chebyshev inequality  
\[\mathrm{prob}\left\{\left|\pi_{k}-\mathrm{E}\left[\pi_{k}\right]\right|\;\geq \;\gamma_{1}\sqrt{\mathrm{Var}\left[\pi_{k}\right]}\right\}\;\leq\;\frac{1}{ \gamma_{1}^{2}}. \tag{31}\]