×

Counting spanning trees in self-similar networks by evaluating determinants. (English) Zbl 1272.05187

Summary: 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.{
©2011 American Institute of Physics}

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
28A80 Fractals
65F40 Numerical computation of determinants
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] DOI: 10.1214/aop/1176989121 · Zbl 0785.60007 · doi:10.1214/aop/1176989121
[2] DOI: 10.1006/jagm.1996.0851 · Zbl 0882.68107 · doi:10.1006/jagm.1996.0851
[3] DOI: 10.1017/S096354830500684X · Zbl 1076.05007 · doi:10.1017/S096354830500684X
[4] DOI: 10.1017/S0963548308009188 · Zbl 1160.05336 · doi:10.1017/S0963548308009188
[5] DOI: 10.1088/0305-4470/10/6/004 · doi:10.1088/0305-4470/10/6/004
[6] DOI: 10.1088/0305-4470/33/21/303 · Zbl 0949.05041 · doi:10.1088/0305-4470/33/21/303
[7] DOI: 10.1088/0305-4470/36/31/301 · Zbl 1099.82503 · doi:10.1088/0305-4470/36/31/301
[8] DOI: 10.1007/s10955-006-9262-0 · Zbl 1110.82007 · doi:10.1007/s10955-006-9262-0
[9] DOI: 10.1088/1751-8113/43/41/415001 · Zbl 1251.05080 · doi:10.1088/1751-8113/43/41/415001
[10] DOI: 10.1007/s10955-011-0140-z · Zbl 1213.82024 · doi:10.1007/s10955-011-0140-z
[11] DOI: 10.1109/31.20199 · Zbl 0683.68036 · doi:10.1109/31.20199
[12] DOI: 10.1002/jgt.3190100311 · Zbl 0699.90041 · doi:10.1002/jgt.3190100311
[13] DOI: 10.1016/j.physa.2003.08.031 · Zbl 1027.05024 · doi:10.1016/j.physa.2003.08.031
[14] DOI: 10.1002/net.20300 · Zbl 1200.90057 · doi:10.1002/net.20300
[15] DOI: 10.1103/PhysRevLett.64.1613 · Zbl 0943.82553 · doi:10.1103/PhysRevLett.64.1613
[16] DOI: 10.1016/j.physa.2006.04.004 · doi:10.1016/j.physa.2006.04.004
[17] DOI: 10.1016/j.disc.2004.07.033 · Zbl 1139.91314 · doi:10.1016/j.disc.2004.07.033
[18] DOI: 10.1103/PhysRevLett.59.381 · doi:10.1103/PhysRevLett.59.381
[19] DOI: 10.1103/PhysRevLett.96.018701 · doi:10.1103/PhysRevLett.96.018701
[20] DOI: 10.1103/PhysRevLett.96.148702 · doi:10.1103/PhysRevLett.96.148702
[21] DOI: 10.1007/s13226-010-0004-2 · Zbl 1203.05041 · doi:10.1007/s13226-010-0004-2
[22] DOI: 10.1103/PhysRevLett.92.118701 · doi:10.1103/PhysRevLett.92.118701
[23] DOI: 10.1038/nature06201 · doi:10.1038/nature06201
[24] DOI: 10.1103/PhysRevE.55.R2093 · doi:10.1103/PhysRevE.55.R2093
[25] DOI: 10.1201/9780203497289 · Zbl 1072.90047 · doi:10.1201/9780203497289
[26] DOI: 10.1103/PhysRevLett.86.5076 · doi:10.1103/PhysRevLett.86.5076
[27] DOI: 10.1142/S0217979202011676 · Zbl 1073.82529 · doi:10.1142/S0217979202011676
[28] DOI: 10.1103/PhysRevE.70.046126 · doi:10.1103/PhysRevE.70.046126
[29] DOI: 10.1209/epl/i2005-10232-x · doi:10.1209/epl/i2005-10232-x
[30] DOI: 10.1073/pnas.0808904106 · doi:10.1073/pnas.0808904106
[31] DOI: 10.1137/100805753 · Zbl 1221.05283 · doi:10.1137/100805753
[32] DOI: 10.1007/s00373-010-0973-2 · Zbl 1232.05055 · doi:10.1007/s00373-010-0973-2
[33] DOI: 10.1209/0295-5075/90/68002 · doi:10.1209/0295-5075/90/68002
[34] DOI: 10.1103/PhysRevE.83.016116 · doi:10.1103/PhysRevE.83.016116
[35] DOI: 10.1002/andp.18471481202 · doi:10.1002/andp.18471481202
[36] DOI: 10.1016/0097-3165(78)90067-5 · Zbl 0376.05032 · doi:10.1016/0097-3165(78)90067-5
[37] Biggs N. L., Algebraic Graph Theory, 2. ed. (1993) · Zbl 0284.05101
[38] DOI: 10.1038/nature03248 · doi:10.1038/nature03248
[39] DOI: 10.1126/science.286.5439.509 · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[40] DOI: 10.1073/pnas.252631999 · Zbl 1064.05137 · doi:10.1073/pnas.252631999
[41] DOI: 10.1103/PhysRevLett.90.058701 · doi:10.1103/PhysRevLett.90.058701
[42] DOI: 10.1103/PhysRevE.79.031110 · doi:10.1103/PhysRevE.79.031110
[43] DOI: 10.1038/nphys266 · doi:10.1038/nphys266
[44] DOI: 10.1038/30918 · Zbl 1368.05139 · doi:10.1038/30918
[45] DOI: 10.1088/1367-2630/9/6/175 · doi:10.1088/1367-2630/9/6/175
[46] DOI: 10.1103/PhysRevE.75.061102 · doi:10.1103/PhysRevE.75.061102
[47] DOI: 10.1103/RevModPhys.74.47 · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[48] DOI: 10.1080/00018730110112519 · doi:10.1080/00018730110112519
[49] DOI: 10.1137/S003614450342480 · Zbl 1029.68010 · doi:10.1137/S003614450342480
[50] DOI: 10.1103/PhysRevE.65.066122 · doi:10.1103/PhysRevE.65.066122
[51] DOI: 10.1140/epjb/e2007-00229-9 · doi:10.1140/epjb/e2007-00229-9
[52] DOI: 10.1088/0022-3719/12/22/035 · doi:10.1088/0022-3719/12/22/035
[53] DOI: 10.1103/PhysRevB.24.496 · doi:10.1103/PhysRevB.24.496
[54] DOI: 10.1103/PhysRevB.26.5022 · doi:10.1103/PhysRevB.26.5022
[55] DOI: 10.1103/PhysRevE.73.066126 · Zbl 1244.82013 · doi:10.1103/PhysRevE.73.066126
[56] DOI: 10.1016/j.dam.2008.04.018 · Zbl 1200.05196 · doi:10.1016/j.dam.2008.04.018
[57] DOI: 10.1103/PhysRevLett.94.018702 · doi:10.1103/PhysRevLett.94.018702
[58] DOI: 10.1103/PhysRevE.77.017102 · doi:10.1103/PhysRevE.77.017102
[59] DOI: 10.1103/PhysRevE.79.061113 · doi:10.1103/PhysRevE.79.061113
[60] DOI: 10.1088/1751-8113/43/39/395101 · Zbl 1213.28004 · doi:10.1088/1751-8113/43/39/395101
[61] DOI: 10.1073/pnas.200327197 · doi:10.1073/pnas.200327197
[62] DOI: 10.1073/pnas.29.11.378 · Zbl 0063.03162 · doi:10.1073/pnas.29.11.378
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.