Finding community structure in mega-scale social networks: [extended abstract]

By Ken Wakita, Toshiyuki Tsurumi. The Web Conference, 2007

448 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/b7f398fc16680954e0984cc60137c3b9313dbdfb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Mapping Change in Large Networks (2008, methodology): “gorithm is as fast as the previous high-speed algorithms (the greedy search presented in the supporting appendix of ref. (1)), which were based on the method introduced in ref. (7) and rened in ref. (8). At the same time, it is also more accurate than our previous high-accuracy algorithm (a simulate”
A classification for community discovery methods in complex networks (2011, background): “5 million nodes [98], with this improvement it is possible to scale up to 100 million nodes.”
Community detection in graphs (2009, background): “By construction, each vertex has more neighbors in its community than in any other community.”
Towards real-time community detection in large networks. (2008, background): “[21] Ken Wakita and Toshiyuki Tsurumi, Finding community structure in mega-scale social networks: [extended abstract], WWW ’07: Proceedings of the 16th international conference on World Wide Web (New York, NY, USA), ACM, 2007, pp.”
Community Detection and Mining in Social Media (2010, background): “1 NETWORK MODELING Since the seminal work by Watts and Strogatz (1998), and Barabási and Albert (1999), network modeling has gained some significant momentum (Chakrabarti and Faloutsos, 2006).”