|
Title:
|
FINDING COMMUNITY STRUCTURE IN A MEGA-SCALE SOCIAL NETWORKING SERVICE |
|
Author(s):
|
Ken Wakita , Toshiyuki Tsurumi |
|
ISBN:
|
978-972-8924-44-7 |
|
Editors:
|
Pedro Isaías , Miguel Baptista Nunes and João Barroso (associate editors Luís Rodrigues and Patrícia Barbosa) |
|
Year:
|
2007 |
|
Edition:
|
V I, 2 |
|
Keywords:
|
Community Structure Analysis, Clustering, Web Mining, Social Networking System, Algorithm |
|
Type:
|
Full Paper |
|
First Page:
|
153 |
|
Last Page:
|
162 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
The community analysis algorithm proposed by Clauset, Newman, and Moore (the CNM algorithm) finds a community
structure in social networks by means of a bottom-up merging process. Unfortunately, the CNM algorithm does not scale
well and its use is practically limited to networks whose sizes are up to 500,000 nodes. The paper identifies the
unbalanced manner in which communities are merged as the cause of this inefficiency. The paper introduces three
variants of metrics called consolidation ratio, which can be used in the process of community analysis to control how
well balanced the sizes of the communities being merged are. Three variations of the CNM algorithms are built
incorporating those metrics. The proposed algorithms are tested using data sets obtained from an existing social
networking service that hosts 5.5 million users. All the algorithms exhibit a dramatic improvement in execution
efficiency over the original CNM algorithm and show high scalability. The fastest of the three processes a network with 1
million nodes in 5 minutes, and one with 4 million nodes in 35 minutes. One of the remaining two processes a network
with 500,000 nodes in 50 minutes (7 times faster than the original algorithm), and builds community structures which
have improved modularity. It can also scale to a network with 5.5 million nodes, which would take more than one month
for the original algorithm to complete. |
|
|
|
|
|
|
