一类五正则小世界网络模型的生成树数目的算法
Spanning Trees in a Class of Five Regular Small World Network

作者: 贾环身 * , 吴廷增 :青海民族大学数学与统计学院,青海 西宁;

关键词: 复杂网络五正则网络图论生成树Complex Network Five Regular Network Graph Theory Spanning Tree

摘要:
生成树是表征网络结构性质的一个重要物理量,然而精确地确定网络上的生成树数目是一个巨大的理论挑战。本文提出了一类五正则小世界网络模型,介绍了其概念及演化过程,详细计算了五正则图的相关拓扑特性,例如直径、聚类系数等。给出了此类五正则网络模型的生成树数目的计算方法,得出生成树数目公式及熵。研究发现,所研究网络的生成树的熵与具有相同平均度的其他网络形成了鲜明的对比,因为后者的生成树的熵小于所研究网络。因此,这一五正则小世界网络上的生成树数目比其他具有自相似结构网络生成树的数目要多。

Abstract: Spanning trees are an important quantity characterizing the reliability of a network, however, explicitly determining the number of spanning trees in networks is a theoretical challenge. In this paper, we present a class of five regular network model with small world phenomenon, and introduce the concept and evolving process. We determine the relevant topological characteristics of the five regular network, such as diameter, clustering coefficient. We give a calculation method of number of spanning trees in such five regular network and derive the formulas and the entropy of number of spanning trees. We find that the entropy of spanning trees in the studied network is in sharp contrast to other small world with the same average degree, the entropy of which is less than the studied network. Thus, the number of spanning trees in such five regular network is more than that of other self-similar networks.

文章引用: 贾环身 , 吴廷增 (2017) 一类五正则小世界网络模型的生成树数目的算法。 理论数学, 7, 401-407. doi: 10.12677/PM.2017.75052

参考文献

[1] Zhang, Z.Z., Liu, H.X., Wu, B. and Zou, T. (2011) Spanning Trees in a Fractal Scale-Free Lattice. Physical Review E, 83, Article ID: 016116.
https://doi.org/10.1103/PhysRevE.83.016116

[2] Boesch, F.T. (1986) On Unreliability Polynomials and Graph Connectivity in Reliable Network Synthesis. Journal of Graph Theory, 10, 339-352.
https://doi.org/10.1002/jgt.3190100311

[3] Nishikawa, T. and Motter, A.E. (2006) Synchronization Is Optimal in Non-Diagonalizable Networks. Physical Review E, 73, Article ID: 065106.
https://doi.org/10.1103/PhysRevE.73.065106

[4] Noh, J.D. and Rieger, H. (2003) Random Walks on Complex Networks. Physical Review, 92, Article ID: 118701.

[5] Dhar, D. and Dhar, A. (1997) Distribution of Sizes of Erased Loops for Loop-Erased Random Walks. Physical Review E, 55, R2093.
https://doi.org/10.1103/PhysRevE.55.R2093

[6] Bapat, R.B. (1999) Resistance Distance in Graphs. The Mathematics Student, 68, 87-98.

[7] Wu, F.-Y. (1977) Number of Spanning Trees on a Lattice. Journal of Physics A, 10, 113-115.
https://doi.org/10.1088/0305-4470/10/6/004

[8] Chang, S.C., Chen, L.C. and Yang, W.S. (2007) Spanning Trees on the Sierpinski Gasket. Journal of Physics, 126, 649-667.
https://doi.org/10.1007/s10955-006-9262-0

[9] Zhang, Z.Z., Liu, H.X., Wu, B. and Zhou, S.G. (2010) Enumeration of Spanning Tree in a Pseudofractal Scale-Free Web. Europhysics Letters, 90, Article ID: 68002.
https://doi.org/10.1209/0295-5075/90/68002

[10] Hu, G.N., Xiao, Y.Z., Jia, H.S. and Zhao, H.X. (2013) A New Class of the Planar Networks with High Clustering and High Entropy. Abstract and Applied Analysis, 2013, Article ID: 795682.
https://doi.org/10.1155/2013/795682

[11] Xiao, Y.Z. and Zhao, H.X. (2013) New Method for Counting the Number of Spanning Trees in a Two -Tree Network. Physica A: Statistical Mechanics and Its Applications, 392, 4576-4583.
https://doi.org/10.1016/j.physa.2013.05.007

[12] Jia, H.S. and Zhao, H.X. (2014) Spanning Trees in a Class of Four Regular Small World Network. Computer Science and Application, 4, Article ID: 13291.

[13] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Application. American Elsevier, New York, 10-12.

[14] Lin, Y., Wu, B., Zhang, Z.Z., et al. (2011) Counting Spanning Trees in Self-Similar Networks by Evaluating Determinants. Journal of Mathematical Physics, 52, Article ID: 113303.
https://doi.org/10.1063/1.3659687

分享
Top