Finding community structures in networks by playing pass-the-parcel.

Abstract

Many data sets can be represented by undirected networks. Often, an interesting and important feature of these networks is the existence of communities; groups of nodes whose interconnectivity is higher than the average for the network. Finding these communities can be a difficult problem; exhaustive search and even simulated annealing methods are impractical for larger networks. Here, a different approach is suggested, a measure of the similarity between a pair of nodes is calculated by simulating a game of pass-the-parcel. This similarity is greater for nodes in the same community and so the pass-the-parcel similarity matrix reduces this problem to the better studied problem of clustering. To demonstrate this approach, it is applied to a number of standard data sets. It shows comparable performance to the state-of-the-art extremal optimization and spectral methods. This algorithm, however, is very similar to one described by Pons and Latapy and so the work described here is not novel.