Journal Article

Fast Multi-Scale Detection of Relevant Communities in Large-Scale Networks

Erwan Le Martelot and Chris Hankin

in The Computer Journal

Published on behalf of British Computer Society

Volume 56, issue 9, pages 1136-1150
Published in print September 2013 | ISSN: 0010-4620
Published online January 2013 | e-ISSN: 1460-2067 | DOI:
Fast Multi-Scale Detection of Relevant Communities in Large-Scale Networks

Show Summary Details


Nowadays, networks are almost ubiquitous. In the past decade, community detection received an increasing interest as a way to uncover the structure of networks by grouping nodes into communities more densely connected internally than externally. Yet most of the effective methods available do not consider the potential levels of organization, or scales, a network may encompass and are therefore limited. In this paper, we present a method compatible with global and local criteria that enables fast multi-scale community detection on large networks. The method is derived in two algorithms, one for each type of criterion, and implemented with six known criteria. Uncovering communities at various scales is a computationally expensive task. Therefore, this work puts a strong emphasis on the reduction of computational complexity. Some heuristics are introduced for speed-up purposes. Experiments demonstrate the efficiency and accuracy of our method with respect to each algorithm and criterion by testing them against large generated multi-scale networks. This study also offers a comparison between criteria and between the global and local approaches. In particular, our results suggest that global criteria seem to be more robust to noise and thus more accurate than local criteria.

Keywords: community detection; multi-scale; fast computation; large networks

Journal Article.  0 words. 

Subjects: Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.