# Fuzzy Random Walkers with Second Order Bounds: An Asymmetric Analysis
## 5 Analysis
### Time and Memory Requirements  
In Table 3, the total execution time for Chebyshev Walktrap (CW), Markov Walktrap (MW), Fuzzy Walktrap (FW), and Fuzzy Newman-Girvan (FN-G) is shown. The last two algorithms are outlined in [10], whereas Fuzzy Markov was proposed in [15]. The effect of the escape mechanisms of weight inversion (I) and relocation (R) are also shown for Markov Walktrap and Chebyshev Walktrap. The Fuzzy Newman-Girvan is an exhaustive algorithm that will serve as baseline both for the requirements and the clustering quality. For the Walktrap algorithms, the time for the two phases, namely random walking (RW) and community building (CB), are recorded separately, while for the Fuzzy Newman-Girvan case only, the total time is recorded as there is only a single phase. In addition, the last column of Table 3 lists the number of the vertices visited by the random walker. Fuzzy Newman-Girvan is considerably slower than any member of the Walktrap family of algorithms. This can be attributed to the exhaustive nature of Fuzzy Newman-Girvan as well as to the extensive use of locality by the Walktrap family. Moreover, the probabilistic constraints of Markov Walktrap and Fuzzy Walktrap resulted in the acceleration of both phases of the respective algorithms, with the second order constraints yielding the lowest times in each case. Concerning the escape strategy of the random walker, the relocation option resulted in a slower walking phase but in an accelerated community building phase, with that combination being more efficient than both \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Property** & **Value** & **Property** & **Value** & **Property** & **Value** & **Property** & **Value** \\ \hline Vertices & 117,649 & \(\sigma_{0}\) & \(7.68\times 10^{-4}\) & Triangles & 37127 & Squares & 1981 \\ Edges & 5,315,625 & \(\sigma_{0}^{t}\) & \(0.6631\) & min cost & 5.1891 & max cost & 10.7232 \\ \(\rho_{0}\) & 45.1821 & Diameter length & 19 & avg cost & 72.1149 & avg cost & 106.0012 \\ \(\rho_{0}^{t}\) & 1.3263 & Diameter cost & 124.4021 & max cost & 143.2716 & max cost & 198.2221 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Structural properties of graph \(Y\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Algorithm** & **Distribution** & **RW (s)** & **CB (s)** & **Total (s)** & **Visits** \\ \hline CW & Poisson & 128.1381 & 2000.9831 & 2129.1212 & 471,858 \\ CW & Binomial & 131.2182 & 2000.0304 & 2131.2486 & 470,342 \\ CW + I & Poisson & 144.4752 & 1911.9118 & 2056.3870 & 477,423 \\ CW + I & Binomial & 139.9919 & 1904.0216 & 2044.0132 & 477,216 \\ CW + R & Poisson & 157.0104 & 1840.0013 & 1997.0117 & 476,997 \\ CW + R & Binomial & 157.6633 & 1850.1003 & 2007.7636 & 476,957 \\ CW + IR & Poisson & 164.3779 & 2002.7745 & 2167.1524 & 477,762 \\ CW + IR & Binomial & 162.0222 & 1911.8664 & 2073.8886 & 477,002 \\ \hline MW & Poisson & 157.5248 & 2104.9918 & 2262.5166 & 475,308 \\ MW & Binomial & 156.9924 & 2099.5256 & 2256.5180 & 475,121 \\ MW + I & Poisson & 165.3374 & 1908.6612 & 2073.9986 & 478,313 \\ MW + I & Binomial & 163.0015 & 1902.4319 & 2065.4334 & 478,102 \\ MW + R & Poisson & 173.9016 & 1850.0971 & 2023.9987 & 477,916 \\ MW + R & Binomial & 171.0017 & 1840.0054 & 2011.0071 & 477,831 \\ MW + IR & Poisson & 181.0013 & 2000.9917 & 2181.9930 & 478,514 \\ MW + IR & Binomial & 178.0017 & 2000.8585 & 2178.8602 & 478,333 \\ \hline FW & Poisson & 191.9989 & 2425.1121 & 2617.1110 & 515,444 \\ FW & Binomial & 184.0451 & 2417.3376 & 2601.3827 & 514,312 \\ \hline FN-G & Poisson & – & – & 9322.9514 & – \\ FN-G & Binomial & – & – & 9344.7778 & – \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Performance in terms of time (sec) and vertex visits. weight inversion and the combination of the two escape strategies. Omitting an escape strategy is not advisable. Therefore, it is not recommended to activate both escape strategies at the same time.