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 detects fuzzy and crisp overlapping communities in a weighted network and simultaneously reveals their hierarchy. Using a local fitness function, the algorithm greedily expands natural communities of seeds until the whole graph is covered. The hierarchy of communities is obtained analytically by calculating resolution levels at which communities grow rather than numerically by testing different resolution levels. This analytic procedure is not only more exact than its numerical alternatives such as LFM and GCE but also much faster. Critical resolution levels can be identified by searching for intervals in which large changes of the resolution do not lead to growth of communities. We tested our algorithm on benchmark graphs and on a network of 492 papers in information science. Combined with a specific post-processing, the algorithm gives much more precise results on LFR benchmarks with high overlap compared to other algorithms and performs very similar to GCE.

25 pages, 10 figures

References in corpus (7)

• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Detecting the overlapping and hierarchical community structure of complex networks
• Detect overlapping and hierarchical community structure in networks
• Multi-scale Modularity in Complex Networks
• Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels

Cited by in corpus (17)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Markov random walk under constraint for discovering overlapping communities in complex networks
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Leveraging disjoint communities for detecting overlapping community structure
• Memetic search for overlapping topics based on a local evaluation of link communities
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Community detection based on significance optimization in complex networks
• Local multiresolution order in community detection
• Evaluating Overlapping Communities with the Conductance of their Boundary Nodes
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
• Metrics for Community Analysis: A Survey
• Estimating Thematic Similarity of Scholarly Papers with Their Resistance Distance in an Electric Network Model
• Ensemble-based Overlapping Community Detection using Disjoint Community Structures
• Understanding Vulnerability of Communities in Complex Networks