Hierarchical multiresolution method to overcome the resolution limit in complex networks

Abstract

The analysis of the modular structure of networks is a major challenge in complex networks theory. The validity of the modular structure obtained is essential to confront the problem of the topology-functionality relationship. Recently, several authors have worked on the limit of resolution that different community detection algorithms have, making impossible the detection of natural modules when very different topological scales coexist in the network. Existing multiresolution methods are not the panacea for solving the problem in extreme situations, and also fail. Here, we present a new hierarchical multiresolution scheme that works even when the network decomposition is very close to the resolution limit. The idea is to split the multiresolution method for optimal subgraphs of the network, focusing the analysis on each part independently. We also propose a new algorithm to speed up the computational cost of screening the mesoscale looking for the resolution parameter that best splits every subgraph. The hierarchical algorithm is able to solve a difficult benchmark proposed in [Lancichinetti & Fortunato, 2011], encouraging the further analysis of hierarchical methods based on the modularity quality function.

References in corpus (13)

• Modularity and community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Resolution limit in community detection
• Comparing community structure identification
• Finding statistically significant communities in networks
• Limits of modularity maximization in community detection
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• Narrow scope for resolution-limit-free community detection
• Size reduction of complex networks preserving modularity
• Analysis of community structure in networks of correlated data
• Mesoscopic analysis of networks: applications to exploratory analysis and data clustering
• Unsupervised clustering analysis: a multiscale complex networks approach

Cited by in corpus (8)

• Community detection in networks: A user guide
• Community Detection via Maximization of Modularity and Its Variants
• Surprise maximization reveals the community structure of complex networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Network community detection using modularity density measures
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Structural patterns in complex systems using multidendrograms
• Towards a robust algorithm to determine topological domains from colocalization data