Cargando…

LazyFox: fast and parallelized overlapping community detection in large graphs

The detection of communities in graph datasets provides insight about a graph’s underlying structure and is an important tool for various domains such as social sciences, marketing, traffic forecast, and drug discovery. While most existing algorithms provide fast approaches for community detection,...

Descripción completa

Detalles Bibliográficos
Autores principales: Garrels, Tim, Khodabakhsh, Athar, Renard, Bernhard Y., Baum, Katharina
Formato: Online Artículo Texto
Lenguaje:English
Publicado: PeerJ Inc. 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10280410/
https://www.ncbi.nlm.nih.gov/pubmed/37346513
http://dx.doi.org/10.7717/peerj-cs.1291
_version_ 1785060788133691392
author Garrels, Tim
Khodabakhsh, Athar
Renard, Bernhard Y.
Baum, Katharina
author_facet Garrels, Tim
Khodabakhsh, Athar
Renard, Bernhard Y.
Baum, Katharina
author_sort Garrels, Tim
collection PubMed
description The detection of communities in graph datasets provides insight about a graph’s underlying structure and is an important tool for various domains such as social sciences, marketing, traffic forecast, and drug discovery. While most existing algorithms provide fast approaches for community detection, their results usually contain strictly separated communities. However, most datasets would semantically allow for or even require overlapping communities that can only be determined at much higher computational cost. We build on an efficient algorithm, Fox, that detects such overlapping communities. Fox measures the closeness of a node to a community by approximating the count of triangles which that node forms with that community. We propose LazyFox, a multi-threaded adaptation of the Fox algorithm, which provides even faster detection without an impact on community quality. This allows for the analyses of significantly larger and more complex datasets. LazyFox enables overlapping community detection on complex graph datasets with millions of nodes and billions of edges in days instead of weeks. As part of this work, LazyFox’s implementation was published and is available as a tool under an MIT licence at https://github.com/TimGarrels/LazyFox.
format Online
Article
Text
id pubmed-10280410
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher PeerJ Inc.
record_format MEDLINE/PubMed
spelling pubmed-102804102023-06-21 LazyFox: fast and parallelized overlapping community detection in large graphs Garrels, Tim Khodabakhsh, Athar Renard, Bernhard Y. Baum, Katharina PeerJ Comput Sci Algorithms and Analysis of Algorithms The detection of communities in graph datasets provides insight about a graph’s underlying structure and is an important tool for various domains such as social sciences, marketing, traffic forecast, and drug discovery. While most existing algorithms provide fast approaches for community detection, their results usually contain strictly separated communities. However, most datasets would semantically allow for or even require overlapping communities that can only be determined at much higher computational cost. We build on an efficient algorithm, Fox, that detects such overlapping communities. Fox measures the closeness of a node to a community by approximating the count of triangles which that node forms with that community. We propose LazyFox, a multi-threaded adaptation of the Fox algorithm, which provides even faster detection without an impact on community quality. This allows for the analyses of significantly larger and more complex datasets. LazyFox enables overlapping community detection on complex graph datasets with millions of nodes and billions of edges in days instead of weeks. As part of this work, LazyFox’s implementation was published and is available as a tool under an MIT licence at https://github.com/TimGarrels/LazyFox. PeerJ Inc. 2023-04-20 /pmc/articles/PMC10280410/ /pubmed/37346513 http://dx.doi.org/10.7717/peerj-cs.1291 Text en © 2023 Garrels et al. https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed. For attribution, the original author(s), title, publication source (PeerJ Computer Science) and either DOI or URL of the article must be cited.
spellingShingle Algorithms and Analysis of Algorithms
Garrels, Tim
Khodabakhsh, Athar
Renard, Bernhard Y.
Baum, Katharina
LazyFox: fast and parallelized overlapping community detection in large graphs
title LazyFox: fast and parallelized overlapping community detection in large graphs
title_full LazyFox: fast and parallelized overlapping community detection in large graphs
title_fullStr LazyFox: fast and parallelized overlapping community detection in large graphs
title_full_unstemmed LazyFox: fast and parallelized overlapping community detection in large graphs
title_short LazyFox: fast and parallelized overlapping community detection in large graphs
title_sort lazyfox: fast and parallelized overlapping community detection in large graphs
topic Algorithms and Analysis of Algorithms
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10280410/
https://www.ncbi.nlm.nih.gov/pubmed/37346513
http://dx.doi.org/10.7717/peerj-cs.1291
work_keys_str_mv AT garrelstim lazyfoxfastandparallelizedoverlappingcommunitydetectioninlargegraphs
AT khodabakhshathar lazyfoxfastandparallelizedoverlappingcommunitydetectioninlargegraphs
AT renardbernhardy lazyfoxfastandparallelizedoverlappingcommunitydetectioninlargegraphs
AT baumkatharina lazyfoxfastandparallelizedoverlappingcommunitydetectioninlargegraphs