Home >

news Help

Publication Information


Title
Japanese: 
English:Finding community structure in Mega-scale social networks [extended abstract] 
Author
Japanese: 脇田 建, 鶴見 敏行.  
English: KEN WAKITA, Toshiyuki Tsurumi.  
Language English 
Journal/Book name
Japanese: 
English:Proceedings of the 16th international conference on World Wide Web 
Volume, Number, Page         pp. 1275-1276
Published date May 2007 
Publisher
Japanese: 
English:ACM 
Conference name
Japanese: 
English:16th international conference on World Wide Web 
Conference site
Japanese: 
English:Banff, Canada 
Official URL http://doi.acm.org/10.1145/1242572.1242805
 
DOI https://doi.org/10.1145/1242572.1242805
Abstract Community analysis algorithm proposed by Clauset, Newman, and Moore (CNM algorithm) finds community structure in social networks. Unfortunately, CNM algorithm does not scale well and its use is practically limited to networks whose sizes are up to 500,000 nodes. We show that this inefficiency is caused from merging communities in unbalanced manner and that a simple heuristics that attempts to merge community structures in a balanced manner can dramatically improve community structure analysis. The proposed techniques are tested using data sets obtained 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, respectively. Another one processes a network with 500,000 nodes in 50 minutes (7 times faster than CNM), finds community structures that has improved modularity, and scales to a network with 5.5 million.

©2007 Tokyo Institute of Technology All rights reserved.