A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities

Abstract

The hidden metric space behind complex network topologies is a fervid topic in current network science and the hyperbolic space is one of the most studied, because it seems associated to the structural organization of many real complex systems. The Popularity-Similarity-Optimization (PSO) model simulates how random geometric graphs grow in the hyperbolic space, reproducing strong clustering and scale-free degree distribution, however it misses to reproduce an important feature of real complex networks, which is the community organization. The Geometrical-Preferential-Attachment (GPA) model was recently developed to confer to the PSO also a community structure, which is obtained by forcing different angular regions of the hyperbolic disk to have variable level of attractiveness. However, the number and size of the communities cannot be explicitly controlled in the GPA, which is a clear limitation for real applications. Here, we introduce the nonuniform PSO (nPSO) model that, differently from GPA, forces heterogeneous angular node attractiveness by sampling the angular coordinates from a tailored nonuniform probability distribution, for instance a mixture of Gaussians. The nPSO differs from GPA in other three aspects: it allows to explicitly fix the number and size of communities; it allows to tune their mixing property through the network temperature; it is efficient to generate networks with high clustering. After several tests we propose the nPSO as a valid and efficient model to generate networks with communities in the hyperbolic space, which can be adopted as a realistic benchmark for different tasks such as community detection and link prediction.

References in corpus (18)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Power-law distributions in empirical data
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Community detection in networks: A user guide
• Predicting Missing Links via Local Information
• Hyperbolic Geometry of Complex Networks
• What's in a crowd? Analysis of face-to-face behavioral 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
• Community detection in networks: Structural communities versus ground truth
• Curvature and temperature of complex networks
• Emergence of Soft Communities from Geometric Preferential Attachment

Cited by in corpus (28)

• Network Geometry
• Progresses and Challenges in Link Prediction
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Link prediction with hyperbolic geometry
• Small worlds and clustering in spatial networks
• Soft communities in similarity space
• Navigability evaluation of complex networks by greedy routing efficiency
• Reconstructing networks
• The inherent community structure of hyperbolic networks
• Emergence of geometric Turing patterns in complex networks
• Similarity forces and recurrent components in human face-to-face interaction networks
• A geometry-induced topological phase transition in random graphs
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Link persistence and conditional distances in multiplex networks
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Understanding the network formation pattern for better link prediction
• Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space
• Sizing the length of complex networks
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Network Renormalization
• Maximally modular structure of growing hyperbolic networks
• Greedy routing optimisation in hyperbolic networks
• EC-SBM Synthetic Network Generator
• Community detection in hypergraphs through hyperedge percolation
• Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Nonlinear Markov Clustering by Minimum Curvilinear Sparse Similarity