Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels

Abstract

We propose a new local, deterministic and parameter-free algorithm that\ndetects fuzzy and crisp overlapping communities in a weighted network and\nsimultaneously reveals their hierarchy. Using a local fitness function, the\nalgorithm greedily expands natural communities of seeds until the whole graph\nis covered. The hierarchy of communities is obtained analytically by\ncalculating resolution levels at which communities grow rather than numerically\nby testing different resolution levels. This analytic procedure is not only\nmore exact than its numerical alternatives such as LFM and GCE but also much\nfaster. Critical resolution levels can be identified by searching for intervals\nin which large changes of the resolution do not lead to growth of communities.\nWe tested our algorithm on benchmark graphs and on a network of 492 papers in\ninformation science. Combined with a specific post-processing, the algorithm\ngives much more precise results on LFR benchmarks with high overlap compared to\nother algorithms and performs very similar to GCE.\n