Finding community structures in networks by playing pass-the-parcel.
Citation:
Conor Houghton, 'Finding community structures in networks by playing pass-the-parcel' (2008)Download Item:
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.
Sponsor
Grant Number
Science Foundation Ireland
Author's Homepage:
http://people.tcd.ie/houghtcjDescription:
PUBLISHED
Author: HOUGHTON, CONOR JAMES
Type of material:
Working PaperSeries/Report no:
TCDMATH08--18
Availability:
Full text availableKeywords:
Clustering, Community detectionsMetadata
Show full item recordLicences: