Poster Title:

Finding Community Structure in Mega-scale Social Networks

Authors:

• Ken Wakita (Tokyo Institute of Technology)
• Toshiyuki Tsurumi (Tokyo Institute of Technology)

Abstract:

Community analysis algorithm proposed by Clauset, Newman, and Moore (CNM algorit hm) finds community structure in social networks. Unfortunately, CNM algorithm does not scale well and its use is practically limited to networks whose sizes a re up to 500,000 nodes. We show that this inefficiency is caused from merging c ommunities in unbalanced manner and that a simple heuristics that attempts to me rge community structures in a balanced manner can dramatically improve community structure analysis. The proposed techniques are tested using data sets obtaine d from existing social networking service that hosts 5.5 million users. We have tested three three variations of the heuristics. The fastest method processes a SNS friendship network with 1 million users in 5 minutes (70 times faster than CNM) and another friendship network with 4 million users in 35 minutes, respect ively. Another one processes a network with 500,000 nodes in 50 minutes (7 time s faster than CNM), finds community structures that has improved modularity, and scales to a network with 5.5 million.