Exploring complex networks via topological embedding on surfaces

Abstract

We demonstrate that graphs embedded on surfaces are a powerful and practical tool to generate, characterize and simulate networks with a broad range of properties. Remarkably, the study of topologically embedded graphs is non-restrictive because any network can be embedded on a surface with sufficiently high genus. The local properties of the network are affected by the surface genus which, for example, produces significant changes in the degree distribution and in the clustering coefficient. The global properties of the graph are also strongly affected by the surface genus which is constraining the degree of interwoveness, changing the scaling properties from large-world-kind (small genus) to small- and ultra-small-world-kind (large genus). Two elementary moves allow the exploration of all networks embeddable on a given surface and naturally introduce a tool to develop a statistical mechanics description. Within such a framework, we study the properties of topologically-embedded graphs at high and low `temperatures' observing the formation of increasingly regular structures by cooling the system. We show that the cooling dynamics is strongly affected by the surface genus with the manifestation of a glassy-like freezing transitions occurring when the amount of topological disorder is low.

18 pages, 7 figures

References in corpus (9)

• Hyperbolic Geometry of Complex Networks
• A tool for filtering information in complex systems
• Supercooled Liquids for Pedestrians
• Sustaining the Internet with Hyperbolic Mapping
• Hierarchical information clustering by means of topologically embedded graphs
• Integer Networks
• A Topological Glass
• Simplex triangulation induced scale-free networks
• Decay of Correlations in a Topological Glass

Cited by in corpus (11)

• Network geometry with flavor: from complexity to quantum geometry
• Interdisciplinary and physics challenges of Network Theory
• Complex Quantum Network Geometries: Evolution and Phase Transitions
• Complex Quantum Network Manifolds in Dimension $d>2$ are Scale-Free
• Extracting Hidden Hierarchies in 3D Distribution Networks
• Entropy of unimodular Lattice Triangulations
• Bounds of percolation thresholds on hyperbolic lattices
• Genus dependence of the number of (non-)orientable surface triangulations
• A memory-based method to select the number of relevant components in Principal Component Analysis
• Unimodular lattice triangulations as small-world and scale-free random graphs
• Spectral properties of unimodular lattice triangulations