# Fuzzy Random Walkers with Second Order Bounds: An Asymmetric Analysis
## 4 Family of Walktrap Heuristics  
### Deterministic Walktrap  
The original Walktrap algorithm [9] simulates an edge crossing random walker in order to estimate the stationary distribution of a homogeneous Markov chain. The walker can commence from any vertex and cross edges by randomly selecting destination vertices, systematically moving to vertices with high edge density as vertices are selected with probability proportional to their degree. Since vertices can be visited an arbitrary number of times, unlike algorithms like BFS and DFS, eventually some patterns in the vertex visiting sequence will emerge. As a community is from a structural perspective, essentially a locally dense graph segment, the walker is more likely to move along vertices belonging to the same community for a large time interval before moving to another community. Thus, analysis of the vertex sequence generated by the random walker can reveal the underlying graph community structure. The Walktrap algorithm is outlined in Algorithm 1.  
```
0: graph \(G(V,E)\), termination criterion \(\tau_{0}\)
0: vertex pair sequence \(\left\langle s_{k},s_{k}^{*}\right\rangle\) is generated
1: pick a random vertex \(v\)
2: repeat
3: pick a neighboring vertex \(v^{*}\) with probability proportional to its degree as in (23)
4: store current vertex in \(v\)and move the walker to the new vertex \(v^{*}\)and\(\left\langle s_{k+1},s_{k+1}^{*}\right\rangle\;\leftarrow\;(v,v^{*})\)
5:until\(\tau_{0}\)is true
6:return vertex sequence \(\left\langle s_{k},s_{k}^{*}\right\rangle\)
```  
**Algorithm 1**Deterministic Walktrap  
The degree of any neighboring vertex can be determined by the graph adjacency matrix \(\mathbf{A}\) defined as  
\[\mathbf{A}[i,j]\;\triangleq\;\begin{cases}1,&i\;=\;j\vee(i,j)\in E\\ 0,&i\;\
eq\;j\wedge(i,j)\
ot\in E\end{cases}\;\;\;\;\in\{0,1\}^{|V|\times|V|}. \tag{22}\]Specifically, the degree of \(v_{k}\) is the sum of the \(k\)-th column of \(\mathbf{A}\). The probability that from vertex \(v_{p}\) a neighbor \(v_{q}\) is selected at the next step is directly proportional to  
\[\frac{\deg\left(v_{q}\right)}{\sum_{\left(v_{p},v_{j}\right)\in E}\deg\left(v_{j }\right)}\;=\;\frac{\mathbf{1}_{|V|}^{T}\,\mathbf{A}\,\mathbf{\varepsilon}_{| V|}^{q}}{\sum_{\left(v_{p},v_{j}\right)\in E}\mathbf{1}_{|V|}^{T}\,\mathbf{A}\, \mathbf{\varepsilon}_{|V|}^{j}}. \tag{23}\]  
In contrast to many graph algorithms, each vertex may be visited more than once. In fact, vertices must be visited many times in order for meaningful patterns to emerge regarding community structure. Typically, for deterministic graphs, a constant number of visits per vertex may suffice resulting in a total of \(\mathrm{O}\left(|V|\right)\) visits, though techniques exploiting the self-similarity nature of large, scale free graphs may yield somewhat lower bounds of \(\mathrm{O}\left(\log^{1+\epsilon}|V|\right)\), \(\epsilon>0\). For fuzzy graphs, the linear bound is as of yet unknown as to whether it can be improved.  
In a distributed setting such as Hadoop, the Deterministic Walktrap can be scaled up since graph segments can be distributed to the nodes. The map part will be the parallel random walkers crossing edges. If such a walker must cross a segment, it can either bounce back or be transferred to the appropriate node. The reduce part will be the frequency count of a large number of vertex pairs.  
Once the random walker has finished crossing the graph, the communities are discovered by means of hierarchical clustering using the frequency of pairs \(\left(s,s^{*}\right)\) as weights. It should be noted that other methods such as Hidden Markov Models and text mining techniques dealing with missing values [54] may be used for discerning community patterns in the sequence \(\left\langle s_{k},s_{k}^{*}\right\rangle\).