TY  - JOUR
A1  - Garrels, Tim
A1  - Khodabakhsh, Athar
A1  - Renard, Bernhard Y.
A1  - Baum, Katharina
T1  - LazyFox: fast and parallelized overlapping community detection in large graphs
T2  - PEERJ Computer Science
N2  - 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.
KW  - Overlapping community detection
KW  - Large networks
KW  - Weighted clustering coefficient
KW  - Heuristic triangle estimation
KW  - Parallelized algorithm
KW  - C++ tool
KW  - Runtime improvement
KW  - Open source
KW  - Graph algorithm
KW  - Community analysis
Y1  - 2023
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/64332
SN  - 2376-5992
VL  - 9
PB  - PeerJ Inc.
CY  - London
ER  -