Scalable and Memory-Efficient Clustering of Large-Scale Social Networks
Clustering of social networks is an important task for their analysis; however, most existing algorithms do not scale to the massive size of today's social networks. A popular class of graph clustering algorithms for large-scale networks, such as PMetis, KMetis and Graclus, is based on a multilevel framework. Generally, these multilevel algorithms work reasonably well on networks with a few million vertices. However, when the network size increases to the scale of 10 million vertices or greater, the performance of these algorithms rapidly degrades.