A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure.
Community detection is the process of assigning nodes and links in significant communities (e.g. clusters, function modules) and its development has led to a better understanding of complex networks. When applied to sizable networks, we argue that most detection algorithms correctly identify promine...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2015-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC4603673?pdf=render |
| _version_ | 1817982028123996160 |
|---|---|
| author | Jean-Gabriel Young Antoine Allard Laurent Hébert-Dufresne Louis J Dubé |
| author_facet | Jean-Gabriel Young Antoine Allard Laurent Hébert-Dufresne Louis J Dubé |
| author_sort | Jean-Gabriel Young |
| collection | DOAJ |
| description | Community detection is the process of assigning nodes and links in significant communities (e.g. clusters, function modules) and its development has led to a better understanding of complex networks. When applied to sizable networks, we argue that most detection algorithms correctly identify prominent communities, but fail to do so across multiple scales. As a result, a significant fraction of the network is left uncharted. We show that this problem stems from larger or denser communities overshadowing smaller or sparser ones, and that this effect accounts for most of the undetected communities and unassigned links. We propose a generic cascading approach to community detection that circumvents the problem. Using real and artificial network datasets with three widely used community detection algorithms, we show how a simple cascading procedure allows for the detection of the missing communities. This work highlights a new detection limit of community structure, and we hope that our approach can inspire better community detection algorithms. |
| first_indexed | 2024-04-13T23:15:12Z |
| format | Article |
| id | doaj.art-7cfc3f6dd8c34954b42fee18624b282d |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-04-13T23:15:12Z |
| publishDate | 2015-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-7cfc3f6dd8c34954b42fee18624b282d2022-12-22T02:25:26ZengPublic Library of Science (PLoS)PLoS ONE1932-62032015-01-011010e014013310.1371/journal.pone.0140133A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure.Jean-Gabriel YoungAntoine AllardLaurent Hébert-DufresneLouis J DubéCommunity detection is the process of assigning nodes and links in significant communities (e.g. clusters, function modules) and its development has led to a better understanding of complex networks. When applied to sizable networks, we argue that most detection algorithms correctly identify prominent communities, but fail to do so across multiple scales. As a result, a significant fraction of the network is left uncharted. We show that this problem stems from larger or denser communities overshadowing smaller or sparser ones, and that this effect accounts for most of the undetected communities and unassigned links. We propose a generic cascading approach to community detection that circumvents the problem. Using real and artificial network datasets with three widely used community detection algorithms, we show how a simple cascading procedure allows for the detection of the missing communities. This work highlights a new detection limit of community structure, and we hope that our approach can inspire better community detection algorithms.http://europepmc.org/articles/PMC4603673?pdf=render |
| spellingShingle | Jean-Gabriel Young Antoine Allard Laurent Hébert-Dufresne Louis J Dubé A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure. PLoS ONE |
| title | A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure. |
| title_full | A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure. |
| title_fullStr | A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure. |
| title_full_unstemmed | A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure. |
| title_short | A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure. |
| title_sort | shadowing problem in the detection of overlapping communities lifting the resolution limit through a cascading procedure |
| url | http://europepmc.org/articles/PMC4603673?pdf=render |
| work_keys_str_mv | AT jeangabrielyoung ashadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure AT antoineallard ashadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure AT laurenthebertdufresne ashadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure AT louisjdube ashadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure AT jeangabrielyoung shadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure AT antoineallard shadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure AT laurenthebertdufresne shadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure AT louisjdube shadowingprobleminthedetectionofoverlappingcommunitiesliftingtheresolutionlimitthroughacascadingprocedure |