Community Detection in the Hyperbolic Space

Abstract

Embedding a network in hyperbolic space can reveal interesting features for the network structure, especially in terms of self-similar characteristics. The hidden metric space, which can be thought of as the underlying structure of the network, is able to preserve some interesting features generally observed in real-world networks such as heterogeneity in the degree distribution, high clustering coefficient, and small-world effect. Moreover, the angular distribution of the nodes in the hyperbolic plane reveals a community structure of the embedded network. It is worth noting that, while a large body of literature compares well-known community detection algorithms, there is still no consensus on what defines an ideal community partition on a network. Moreover, heuristics for communities found on networks embedded in the hyperbolic space have been investigated here for the first time. We compare the partitions found on embedded networks to the partitions obtained before the embedding step, both for a synthetic network and for two real-world networks. The second part of this paper presents the application of our pipeline to a network of retweets in the context of the Italian elections. Our results uncover a community structure reflective of the political spectrum, encouraging further research on the application of community detection heuristics to graphs mapped onto hyperbolic planes.

Preprint from Complexity 72H Workshop, held at IMT School for Advanced Studies Lucca, 17-21 June 2019

References in corpus (12)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Critical phenomena in complex networks
• Navigability of Complex Networks
• The ground truth about metadata and community detection in networks
• Sustaining the Internet with Hyperbolic Mapping
• A small-world of weak ties provides optimal global integration of self-similar modules in functional brain networks
• Self-similarity of complex networks and hidden metric spaces
• Topological strata of weighted complex networks
• Limited resolution in complex network community detection with Potts model approach
• Complex Networks on Hyperbolic Surfaces
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

Cited by in corpus (1)

• The inherent community structure of hyperbolic networks