Another approach to identify communities is by simulating random walks inside the network.
The general idea is that, given a graph and a starting point, if we select a
neighbour at random and move to the selected neighbour and repeat the same
process till a termination condition, this walk, namely a random sequence of nodes,
is more likely to stay within the same community as there are only a few edges that lead outside a given community. In other words, a random walker will tend to wander inside densely connected areas of the graph. This concepts inspired the Walktrap algorithm [1]} and the Infomap algorithm [2]}. Walktrap makes use of short random walks (of 3-4-5 steps) to compute distances between nodes.
Based on (small) intra and (larger) inter-community distances, nodes are being assigned to groups, via bottom-up hierarchical clustering. In this respect, modularity score can be used to select where to cut the dendrogram. It should be pointed out that this algorithm considers only one community per node, which in some cases can be an incorrect hypothesis.
