一类四正则小世界网络的生成树数目的算法

Spanning Trees in a Class of Four Regular Small World Network

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

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.