The inherent community structure of hyperbolic networks

Abstract

A remarkable approach for grasping the relevant statistical features of real networks with the help of random graphs is offered by hyperbolic models, centred around the idea of placing nodes in a low-dimensional hyperbolic space, and connecting node pairs with a probability depending on the hyperbolic distance. It is widely appreciated that these models can generate random graphs that are small-world, highly clustered and scale-free at the same time; thus, reproducing the most fundamental common features of real networks. In the present work, we focus on a less well-known property of the popularity-similarity optimisation (PSO) model and the ${\mathbb{S}}^1/{\mathbb{H}}^2$ model from this model family, namely that the networks generated by these approaches also contain communities for a wide range of the parameters, which was certainly not an intention at the design of the models. We extracted the communities from the studied networks using well-established community finding methods such as Louvain, Infomap and label propagation. The observed high modularity values indicate that the community structure can become very pronounced under certain conditions. In addition, the modules found by the different algorithms show good consistency, implying that these are indeed relevant and apparent structural units. Since the appearance of communities is rather common in networks representing real systems as well, this feature of hyperbolic models makes them even more suitable for describing real networks than thought before.

99 pages, 96 figures

References in corpus (14)

• Fast unfolding of communities in large networks
• Near linear time algorithm to detect community structures in large-scale networks
• Comparing community structure identification
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• Hyperbolic Geometry of Complex Networks
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Self-similarity of complex networks and hidden metric spaces
• Maximizing Modularity is hard
• Emergence of Soft Communities from Geometric Preferential Attachment
• Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
• Community Detection in the Hyperbolic Space

Cited by in corpus (9)

• Scaling theory of fractal complex networks
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Maximally modular structure of growing hyperbolic networks
• Augmentations of Forman's Ricci Curvature and their Applications in Community Detection
• Greedy routing optimisation in hyperbolic networks
• Emergence of metastability in frustrated oscillatory networks: the key role of hierarchical modularity
• Community detection in hypergraphs through hyperedge percolation
• Symmetry-driven embedding of networks in hyperbolic space