Partitioning large networks without breaking communities |
| |
Authors: | Anand Narasimhamurthy Derek Greene Neil Hurley Pádraig Cunningham |
| |
Affiliation: | 1. School of Computer Science and Informatics, University College Dublin, Dublin, Ireland
|
| |
Abstract: | The identification of cohesive communities is a key process in social network analysis. However, the algorithms that are effective
for finding communities do not scale well to very large problems, as their time complexity is worse than linear in the number
of edges in the graph. This is an important issue for those interested in applying social network analysis techniques to very
large networks, such as networks of mobile phone subscribers. In this respect, the contributions of this paper are twofold.
First, we demonstrate these scaling issues using a prominent community-finding algorithm as a case study. Then, we show that
a two-stage process, whereby the network is first decomposed into manageable subnetworks using a multilevel graph partitioning
procedure, is effective in finding communities in networks with more than 106 nodes. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|