# Fuzzy Random Walkers with Second Order Bounds: An Asymmetric Analysis
## 5 Analysis
### Community Coherence  
The following definition will facilitate further analysis of the experimental results. **Definition 7**. : _The (log)scree plot of a set \(S\) is the plot of the (logarithm of the) values of \(S\) versus their sorted frequency._  
Since \(Y\) does not contain ground truth communities, the communities obtained by the Fuzzy Newman-Girvan will be used as a baseline reference since their sizes are closer to a power law distribution, which is an essential feature of large, scale-free graphs. The deviation \(\xi\) of a set of numbers \(\{x\}_{k=1}^{n}\) from a power law  
\[f_{k}\;=\;\alpha_{0}\,k^{-\gamma_{0}},\quad 1\;\leq\;k\;\leq\;n,\alpha_{0}>0, \gamma_{0}>0 \tag{41}\]  
is quantified by the formula [62; 63]  
\[\xi\;=\;\sqrt{\frac{1}{n}\sum_{k=1}^{n}\left(\log f_{k}-\left(\log\alpha_{0}- \gamma_{0}\log k\right)\right)^{2}}, \tag{42}\]  
where parameters \(\alpha_{0}\) and \(\gamma_{0}\) can be estimated by, for instance, a least squares method [25]. Additionally, the estimated value of \(\alpha_{0}\) serves as a quality indicator, as it should be as close to \([2,3]\) as possible. The number of communities for each algorithm are shown in Table 5. Notice that this is not an absolute clustering quality metric, as typically a large number of coherent communities is preferable to a smaller number of sparse ones. Nonetheless, the introduction of the relocation strategy systematically pushes the number of communities towards the reference number, although more evidence is required for determining community coherence. This will be addressed by the two asymmetric indices of this section. In order to evaluate the clustering quality, the Kullback-Leibler divergence between the sorted sizes of the communities generated by the Fuzzy Newman-Girvan and the sorted community sizes of the remaining algorithms was computed. Recall that for two discrete distributions \(p_{k}\) and \(q_{k}\) the Kullback-Leibler divergence is defined as  
\[\left\langle p\,||\,q\right\rangle\stackrel{{\triangle}}{{=}}\sum _{k=1}^{n}p_{k}\log\left(\frac{p_{k}}{q_{k}}\right)\;=\;\sum_{k=1}^{n}p_{k} \log p_{k}-\sum_{k=1}^{n}p_{k}\log q_{k}, \tag{43}\]  
where \(k\) ranges over the union of discrete events. If \(p_{k}\) and \(q_{k}\) have no events in common, then the result is undefined. If for a single event \(p_{k}=0\) or \(q_{k}=0\), then the corresponding summand is zero. Table 6 summarizes the divergence for the Poisson and the binomial cases. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline  & **CW** & **CW + 1** & **CW + R** & **CW + IR** & **MW** & **MW + 1** & **MW + R** & **MW + IR** & **FW** & **FN-G** \\ \hline Poisson & 13,751 & 137,58 & 13,332 & 13,443 & 13,761 & 13,789 & 13,456 & 13,804 & 14,127 & 12,816 \\ Binomial & 18,841 & 18,912 & 16,090 & 17,621 & 18,877 & 18,801 & 17,002 & 18,811 & 18,891 & 15,117 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Number of communities. Chebyshev Walktrap with relocation outperforms the remaining algorithms, as it has less divergence from the reference distribution. A question at this point is whether a correspondence between the communities returned by each algorithm can be found. The asymmetric Tversky index between two sets \(T\) and \(V\) is defined as  
\[\
u_{T,V}\,\overset{\triangle}{=}\,\frac{|T\cap V|}{|T\cap V|+w_{1}|T\setminus V |+w_{2}|V\setminus T|},\quad w_{1},w_{2}>0, \tag{44}\]  
and it quantifies the distance between the template set \(T\) and the variant set \(V\). By the very definition of the index, the template set \(T\) and the variant set \(V\) are not interchangeable, namely \(\
u_{T,V}\
eq\
u_{V,T}\). This agrees with intuition, as it makes sense to ask how much the heuristic results differ from the ground truth community, whereas there is no point in asking the inverse question.