Partitioning large networks without breaking communities
| Autor: | Anand Narasimhamurthy, Neil Hurley, Derek Greene, Pádraig Cunningham |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Theoretical computer science
Dynamic network analysis Wireless network business.industry Computer science Graph partition Mobile computing Graph theory Human-Computer Interaction Evolving networks Artificial Intelligence Hardware and Architecture Graph (abstract data type) Artificial intelligence business Time complexity Software Information Systems |
| Zdroj: | Knowledge and Information Systems. 25:345-369 |
| ISSN: | 0219-3116 0219-1377 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink