Date Added: Nov 2009
Online social networks pose significant challenges to computer scientists, physicists, and sociologists alike, for their massive size, fast evolution, and uncharted potential for social computing. One particular problem that has interested one is community identification. Many algorithms based on various metrics have been proposed for identifying communities in networks, but a few algorithms scale to very large networks. Three recent community identification algorithms, namely CNM, Wakita, and Louvain, stand out for their scalability to a few millions of nodes. All of them use modularity as the metric of optimization. However, all three algorithms produce inconsistent communities every time the input ordering of nodes to the algorithms changes.