Unimodular lattice triangulations as small-world and scale-free random graphs

Abstract

Real-world networks, e.g. the social relations or world-wide-web graphs, exhibit both small-world and scale-free behaviour. We interpret lattice triangulations as planar graphs by identifying triangulation vertices with graph nodes and one-dimensional simplices with edges. Since these triangulations are ergodic with respect to a certain Pachner flip, applying different Monte-Carlo simulations enables us to calculate average properties of random triangulations, as well as canonical ensemble averages using an energy functional that is approximately the variance of the degree distribution. All considered triangulations have clustering coefficients comparable with real world graphs, for the canonical ensemble there are inverse temperatures with small shortest path length independent of system size. Tuning the inverse temperature to a quasi-critical value leads to an indication of scale-free behaviour for degrees $k\ge 5$. Using triangulations as a random graph model can improve the understanding of real-world networks, especially if the actual distance of the embedded nodes becomes important.

arXiv comment17 pages, 6 figures, will appear in New J. Phys

References in corpus (24)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• An efficient, multiple range random walk algorithm to calculate the density of states
• Renormalization group analysis of the small-world network model
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Parallel Tempering: Theory, Applications, and New Perspectives
• Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
• Connectivity of Growing Random Networks
• Growing Scale-Free Networks with Tunable Clustering
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Reconstructing the Universe
• Highly clustered scale-free networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Scale-free Networks on Lattices
• Structural transitions in scale-free networks
• Mean-field theory for clustering coefficients in Barabasi-Albert networks
• Geographical Embedding of Scale-Free Networks
• Glass transition in self organizing cellular patterns
• Surface realization with the intersection edge functional
• Exploring complex networks via topological embedding on surfaces
• Epidemic spreading in lattice-embedded scale-free networks
• Freezing of Triangulations

Cited by in corpus (2)

• Tuning the Clustering Coefficient of Generalized Circulant Networks
• Spectral properties of unimodular lattice triangulations