全部 标题 作者
关键词 摘要


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

DOI: 10.12677/CSA.2014.43009, PP. 43-49

Keywords: 复杂网络;四正则网络;生成树
Complex Network
, Four Regular Network, Spanning Tree

Full-Text   Cite this paper   Add to My Lib

Abstract:

生成树是表征网络结构性质的一个重要物理量,然而精确地确定网络上的生成树数目是一个巨大的理论挑战。本文提出了一个四正则小世界网络模型。介绍了其概念及演化过程,详细计算了四正则图的相关拓扑特性,例如直径、聚类系数等。给出了此类四正则网络的生成树数目计算方法,得出生成树数目公式及熵。研究发现,所研究网络的生成树的熵与具有相同平均度的其他网络形成了鲜明的对比,因为后者的生成树的熵小于所研究网络。因此,这一四正则小世界网络上的生成树数目比其他具有自相似结构网络生成树的数目要多
Spanning tree is 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 four regular network model with small world phenomenon. We introduce the concept and evolving process and determine the relevant topological characteristics of the four regular network, such as diameter and clustering coefficient. We give a calculation method of number of spanning trees in such four 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, of which the entropy is less than the studied network. Thus, the number of spanning trees in such four regular network is more than that of other self-similar networks.

References

[1]  Zhang, Z.Z., Gao, S.Y., Chen, L.C., Zhou, S.G., Zhang, H.J. and Guan, J.H. (2010) Mapping Koch curves into scalefree small-world networks. Journal of Physics A: Mathematical and Theoretical, 43, Article ID: 395101.
[2]  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.
[3]  Boesch, F.T. (1986) On unreliabillity polynomials and graph connectivity in reliable network synthesis. Journal of Graph Theory, 10, 339-352.
[4]  Nishikawa, T. and Motter, A.E. (2006) Synchronization is optimal in non-diagonalizable networks. Physical Review E, 73, Article ID: 065106.
[5]  Noh, J.D. and Rieger, H. (2003) Random walks on complex networks. Physical Review, 92, Article ID: 118701.
[6]  Dhar, D. and Dhar, A. (1997) Distribution of sizes of erased loops for loop-erased random walks. Physical Review E, 55, 2093.
[7]  Zhang, Z.Z., Shan, T. and Chen, G.R. (2013) Random walks on weighted networks. Physical Review E, 87, Article ID: 012112.
[8]  Bapat, R.B. (1999) Resistance distance in graphs. The Mathematics Student, 68, 87-98.
[9]  Chang, S.C., Chen, L.C. and Yang, W.S. (2007) Spanning Trees on the Sierpinski Gasket. Journal of Physics, 126, 649.
[10]  Lyons, R., Peled, R. and Schramm, O. (2008) Growth of the number of spanning trees of the Erd?s-Rényi giant component. Combinatorics, Probability and Computing, 17, 711.
[11]  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.
[12]  Zhang, Z.Z., Wu, B. and Lin, Y. (2012) Counting spanning trees in a small-world Farey graph. Physica A, 391, 33423349.
[13]  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.
[14]  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.
[15]  Bondy, J.A. and Murty, U.S.R. (1976) Graph theory with application. American Elsevier, New York, 10-12.

Full-Text

comments powered by Disqus