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.

arXiv comment99 pages, 96 figures

References in corpus (41)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Near linear time algorithm to detect community structures in large-scale networks
• Comparing community structure identification
• Temporal Networks
• Analysis of weighted networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• Hyperbolic Geometry of Complex Networks
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Popularity versus Similarity in Growing 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
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• On community structure in complex networks: challenges and opportunities
• Maximizing Modularity is hard
• Emergent Hyperbolic Network Geometry
• Network Mapping by Replaying Hyperbolic Growth
• Multiscale unfolding of real networks by geometric renormalization
• Interdisciplinary and physics challenges of Network Theory
• Emergence of Soft Communities from Geometric Preferential Attachment
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• The hidden geometry of weighted complex networks
• Clustering implies geometry in networks
• Navigable Networks as Nash Equilibria of Navigation Games
• Euclidean versus hyperbolic congestion in idealized versus experimental networks
• Network Geometry and Complexity
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Soft communities in similarity space
• Hyperbolicity Measures "Democracy" in Real-World Networks
• On the Hyperbolicity of Large-Scale Networks
• Optimisation of the coalescent hyperbolic embedding of complex networks
• 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