Finding community structures in networks by playing pass-the-parcel.
Item Type:Working Paper
Citation:Conor Houghton, 'Finding community structures in networks by playing pass-the-parcel' (2008)
Houghton2008b.pdf (working paper) 91.30Kb
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.
Science Foundation Ireland
Author: HOUGHTON, CONOR JAMES
Type of material:Working Paper
Availability:Full text available