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

Spanning Trees in a Class of Five Regular Small World Network

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

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.