# Large Scale Community Detection Using a Small World Model
## 4 Random Walk  
Community detection in a large complex network can be carried out by capturing the topological structure using random walk in the network. The intuition behind random walk is that the network tends to be trapped inside a denser region (community) for a longer period of time. This idea can be used for inclusion of nodes in the community. In this paper, an efficient similarity metric based on the random walk has been proposed to include a node in the community. This metric may provide the following features:  
* Structure of the network is well captured in the process of community detection;
* It can be used in an agglomerative hierarchal clustering;
* Computation to find community may be more efficient. Social network can be represented in the form of a graph, where nodes represent social entities and edges represent relationships between the entities. The graph can be stored in the form of adjacency matrix \(A\), where \(A_{ij}=1\), if there is an edge, existing between nodes \(i\) and \(j\), and 0 otherwise. Random walk in a graph is the process of visiting a neighboring node randomly from the source node and continuing the process of visiting throughout the graph. Random walk process is well explained on the basis of Markov chain in which each node corresponds to vertices in the visited path [33]. In this paper, transition matrix obtained by Random walk in the graph has been considered for detection of communities. Transition matrix describes the probability of visiting each node from every other node in \(k\) number of steps i.e., \(T_{ij}^{k}\) corresponds to the probability of visiting node \(j\) from \(i\) in \(k\) number of steps. \(T^{1}\), \(T^{2}\), \(T^{3}\) and \(T^{k}\) are the transition matrices for random walk corresponding to 1, 2, 3 and \(k\) walk length, respectively. Transition probability from vertex \(i\) to vertex \(j\) in one length random walk is defined by the following equation:  
\[T_{ij}^{1}=\frac{A_{ij}}{d_{i}}, \tag{6}\]  
where \(A_{ij}\) is the adjacency matrix of the network and \(d_{i}\) is the degree of vertex \(i\). **Property 1**: _Probability for a random walker to visit a node \(j\) from node \(i\) in walk length that tends to infinity depends only on the degree of \(j\), rather than degree of the source or the intermediate node. It may be represented as:_  
\[\lim_{k\rightarrow\infty}T_{i,j}^{k}=\frac{d_{j}}{2E}, \tag{7}\]  
_where \(d_{i}\) is the degree of \(i\) and \(E\) is the total number of edges in the network._  
**Property 2**: _Ratio of probabilities for a random walker that visits a node from \(i\) to \(j\) and \(j\) to \(i\) through a fixed walk length depends only on the degree of \(i\) and \(j\). It may be represented as follows:_  
\[\frac{T_{i,j}^{k}}{T_{j,i}^{k}}=\frac{d_{j}}{d_{i}}. \tag{8}\]  
_Vertex Similarity Based on Random Walk_  
Vertices belonging to the same community seems to have similar behavior as compared to vertices outside the communities. Any two nodes inside a community look the same way as other nodes in the network. We may consider an example of a random walk of length \(k\) in graph \(G(V,E)\), which representsa social network. The probability of visiting all nodes from all other nodes in the network through \(k\) length random walk is represented by transition matrix \(T^{k}\). Each tuple in the transition matrix corresponds to probabilities of visiting all other nodes from node \(i\) in \(k\) walk length. These probabilities are based on structural information in the network. From the structure of the network, the following inferences may be drawn:  
* If two nodes \(i\) and \(j\), are in the same community, the probability of visiting node \(j\) from \(i\) would be higher as compared to visiting a node outside the community. In addition, converse may not be true i.e., if the probability is high, it does not mean that they belong to the same community. * The probability \(T^{k}_{i,j}\) depends on the degree of \(j\) because the walker tends to visit towards vertices, where the degree is high.