| Autor: |
Wakita, Ken, Tsurumi, Toshiyuki |
| Předmět: |
|
| Zdroj: |
Proceedings of the IADIS International Conference on WWW/Internet; Nov2007, p153-162, 10p, 1 Diagram, 4 Graphs |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
