Counting spanning trees in self-similar networks by evaluating determinants

Abstract

Spanning trees are relevant to various aspects of networks. Generally, the number of spanning trees in a network can be obtained by computing a related determinant of the Laplacian matrix of the network. However, for a large generic network, evaluating the relevant determinant is computationally intractable. In this paper, we develop a fairly generic technique for computing determinants corresponding to self-similar networks, thereby providing a method to determine the numbers of spanning trees in networks exhibiting self-similarity. We describe the computation process with a family of networks, called $(x,y)$-flowers, which display rich behavior as observed in a large variety of real systems. The enumeration of spanning trees is based on the relationship between the determinants of submatrices of the Laplacian matrix corresponding to the $(x,y)$-flowers at different generations and is devoid of the direct laborious computation of determinants. Using the proposed method, we derive analytically the exact number of spanning trees in the $(x,y)$-flowers, on the basis of which we also obtain the entropies of the spanning trees in these networks. Moreover, to illustrate the universality of our technique, we apply it to some other self-similar networks with distinct degree distributions, and obtain explicit solutions to the numbers of spanning trees and their entropies. Finally, we compare our results for networks with the same average degree but different structural properties, such as degree distribution and fractal dimension, and uncover the effect of these topological features on the number of spanning trees.

Definitive version published in Journal of Mathematical Physics

References in corpus (15)

• Extracting the multiscale backbone of complex weighted networks
• First-passage times in complex scale-invariant media
• Fractal and Transfractal Recursive Scale-Free Nets
• Transport in weighted networks: Partition into superhighways and roads
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Spanning trees on the Sierpinski gasket
• Scale-free trees: the skeletons of complex networks
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Percolation in Hierarchical Scale-Free Nets
• Enumeration of spanning trees in a pseudofractal scale-free web
• Exact analytical solution of average path length for Apollonian networks
• Evolving small-world scale-free networks consist of cliques
• Mapping Koch curves into scale-free small-world networks
• Different thresholds of bond percolation in scale-free networks with identical degree sequence
• Random Walks on Complex Networks

Cited by in corpus (3)

• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• Exact eigenvalue spectrum of a class of fractal scale-free networks
• Tutte polynomial of a small-world farey graph