信，皇，技术 Ｄ０Ｉ １０．３９６９６．ｉｓｓｎ．１６７２—６３７５．２０１７．０６．００１ ２０１７年（第４６卷）第６期 一类确定型的小世界等级指数型复杂网络模型 赵倩 兰州７３００３０） （兰州市卫生统计信息中心，甘肃摘要：小世界效应在实际生活中是随处可见的，例如复杂网络中的六度分离理论。本论述为了更好地研究小世界网络的 拓扑结构，采用完全三部图 为基本元素，通过循环迭代的算法程序，设计了一类小世界网络模型。首先，分析了它的重 要拓扑参数：聚类系数、直径和平均距离，得证该模型具有小世界效应，而后通过计算机仿真还获知该模型具有等级结构。 其次，通过计算其顶点的累积度分布得知，该模型拥有指数分布特性。最后，利用特殊的演化过程，得到了其最多叶子生成 树的叶子数目。 关键词：复杂网络模型；小世界效应；等级结构；指数分布；最多叶子生成树 中图分类号：Ｎ９４；Ｏ１７３ 文献标识码：Ｂ １引言及背景 近年来随着互联网技术的不断发展与更新，人们 对复杂网络的研究，迎来了一个热潮，越来越多的科研 工作者们对其投入了大量的研究精力，因此获得了很 多研究成果和大批网络模型，如：物联网、地震网、食物 链网、电力网、细胞新陈代谢网、神经信号传送网、股市 ｇａｎｎ 建立了可随机替换的ＷＳ小世界模型，２０００年， Ｋｌｅｉｎｂｅｒｇ［８ 介绍了一类演化的小世界网络模型，其中的 构成元素是二维的方格子。在国内，章忠志 ｍ 等人在 Ｐｈｙｓｉｃａ Ａ杂志上分别于２００６年提出了一类边循环迭 代演化的确定型小世界网络模型和２０１２年提出了以 Ｆａｒｅｙ图为基本生成元素的小世界网络模型。除了小 世界效应之外，复杂网络还具有指数分布特性 ］，即：顶 网等。事实上，关于复杂网络的研究经过了一段很长 的时间，上世纪６０年代，匈牙利数学家Ｅｒｄｏｓ和Ｒｅｎｙｉ 提出了随机网络模型，称为ＥＲ模型…。上世纪末，统计 物理学家Ａ．Ｌ．Ｂａｒａｂａｓｉ和他的研究生Ｒ．Ａｌｂｅｒｔ 通过对 万维网随时间演化过程的研究，发现很多现实中的复 点的累积度分布服从指数分布。Ｄｏｒｏｇｏｖｔｓｅｖ、Ｇｏｌｔｓｅｖ 和Ｍｅｎｄｅｓ等人ｎ¨也发现了网络中存在等级结构，即： 度为ｋ的顶点的聚类系数ｃ 满足ｃ ．１｝～。随着网 络研究的不断深入，网络安全［１２－２０］引起了人们的高度重 视，生成树的数目就是其中一个与安全性能相关的重 杂网络都具有两个基本的形成机制：增长和择优连 接。１９９８年，Ｗａｔｔｓ和Ｓｔｒｏｇａｔｚｂ 首次构造了一类具有 高聚类系数和低平均距离的网络模型，叫做ＷＳ模型， 要指标，其作为网络的一个不变量，与渗流、疾病传播、 网络同步性能和随机游走等都是密切相关的。 也称为小世界网络模型（ｓｍａｌｌ—ｗｏｒｌｄ ｍｏｄｅ１），为此把高 聚类系数和低平均距离（或小直径）作为小世界效应的 两个重要的拓扑参数，之后为了更好地揭示小世界网络 背后所蕴藏的拓扑结构与演化机理，Ｎｅｗｍａｎ和Ｗａｔｔｓ［５刮 丰富了已有的ＷＳ模型。除此之外１９９９年，Ｋａｓｔｕｒｉｒａｎ一 ２定义和命题 （１）作为衡量一个网络传输性能与效率的重要参 数直径Ｄ和平均距离 ，它们的定义如下： 对于Ⅳ 中的任意两个互异的顶点ｉ和 来说，它 们之间的距离ｄ 表示连接顶点ｉ和 的所有路中内部 收稿日期：２０１７—０３—１２ 作者简介：赵倩（１９７８一），女，汉族，甘肃武威人，硕士，工程师，主要研究方向：计算机技术。 ４ ２０１７年（第４６卷）第６期 信，皇，技术 边最少的那条路所含边数的数目，直径Ｄ就是指网络 中任意一对互异顶点ｉ和 距离ｄ 的最大值，记为 式中 ＝Ｕ ，Ｅ。＝ＵＥＵ （１）， （１）表示由任 』＝１ Ｊ １ Ｄ＝ｍａｘ｛ａ ｌｉ，ｊ∈Ⅳ ；平均距离 指网络中所有顶点对 和＿『距离 的和与—ＩＶ（ｔ）ｌＯ ｖ（ｔｘ－Ｉ）的比值—一意一个拷贝图Ｇ ，Ｅ ）中的核心集合中的任意一个顶 点与其余ｎ一１个拷贝图中核心图中的每一个顶点连线 所产生的边集合，连边运算中不允许重边和自环的出 ，记为 ∑ｄ ｄ＝ Ｅｖ（ｏ 现，把由这一组拷贝图中核心点集合通过映射厂（１Ｊ作用 后产生的子图称为图Ｇ， ，Ｅ，）的核心图日（１），从核 ０Ｖ（ｔ）ｌＯＶ（ｔ）ｌ一１）１／２。 （２）结合大量的实际网络模型的研究数据和相应 的计算机仿真模拟，一些网络模型具有如下的拓扑性 质： （ａ）低的平均度＜ ＞（稀疏性） ：当时间ｔ很大 时，存在一个常数Ａ，使得＜ｋ＞＿÷Ａ成立； （ｂ）指数分布：对于任意选取的度为ｋ顶点，其概 率服从指数分布，即：Ｐ ｏｃ 卢。～。或者，对于任意给 定的一个度值ｋ，网络中度数大于 的顶点的数目服 ∑ ｋ 、， 从指数分布，即：Ｐ一 ￣ａ２ｌｆｚ～， 表示ｔ 时刻顶点度数等于ｋ 的顶点数目； （ｃ）高的聚类系数：当时间ｔ很大时，总存在一个正 常数８，使得Ｃ≥占成立； （ｄ）等级结构性 ：对于任意选取的度为ｋ顶点，其 聚类系数Ｃ满足Ｃ。ｃｋ～； （ｅ）小的直径：随着时间ｔ的延续，网络模型的直径 满足Ｄ 。ｃ ，ｌｎ（１Ｖ（ｔ）１）； （ｆ）低的平均距离：随着时间ｔ的延续，网络模型的 平均距离 满足 ｏｃｏＬ ｌ￣（Ｉｖ（ｔ）ｌ１。 命题１网络模型具有小世界效应，如果它拥有高 聚类系数（ｃ）、小的直径（ｅ）和低的平均距离（ｆ）。 命题２网络模型具有指数特性，如果其顶点的度 分布（累积度分布）服从指数分布（ｂ）。 （３）网络运算映射．厂：对于一个给定的简单图 Ｇ 目，顶点集合和边集合分别为 和Ｅ，简单记作 Ｇ。对任意的一组顶点集合（核心集合） ＠＝｛１３１） ：，…，＂ｏｉ｝，都可以得到图Ｇ的一个顶点导出子 图Ｇ（ （ ），Ｅ（ ）），若将图Ｇ拷贝上ｎ个，依次标号为 Ｇ （ ，Ｅ ），Ｇ （ ，Ｅ ），…，Ｇ Ｖ－，Ｅ“），映射ｆ作用在这一组 图集合上，便能得到一个诱导图。如下： （Ｇ ，Ｇ ，・一，Ｇ ）＝Ｇ，（ ，Ｅ。） （Ｉ） 心图日（１）中任意选出ｉ个顶点作为核心顶点集合，再拷 贝上ｎ个图Ｇ ，Ｅ ），按照生成图Ｇ。 ，Ｅ。）的过程，这ｎ 个图Ｇ。 ，Ｅ ）在映射， ’下便可得到一个新图 Ｇ： ，Ｅ：），这个过程可以重复多次，直至得到理想的模 型，这样便得到一组模型，构成了一个网络模型空间 （Ｇ ，Ｈ（ｔ）ｄｆｖ＇，ｔ）。 （４）网络运算０：一般而言，对于一个随时间不断 变化的复杂网络来说，获取它的直径Ｄ和平均距离 的数值是一件很困难的事．为此文中定义了一种新的 网络运算，简称为０运算，其运算法则被展示在等式 （２）中。 文中的网络模型ＪＪｖ∞的建立是依阶数为６的完全 三部图 为基本元素，结合了增长和优先连接两大 基本演化机制，并采用了循环迭代的算法程序（网络运 算映射厂）得到的．其顶点集合和边集合分别用 （ｆ）和 Ｅ 表示，相应地，顶点数目和边数目用Ｉ （ｆ）ｌ和ＩＥ（ｆ）Ｉ表 示，记号［ｍ，ｎ】表示ｍ，ｍ＋１，ｒｎ＋２，…，ｎ一２，ｎ—ｌ，ｎ的自 然数集合。 。。 ｚ１ （６ｌ＋ ）ｃ』］ｄ 口ｌ６ｌ ｃｌｄｌ 。 ａ：ｂ２ ｃ：ｄ２ ＝ｌ （６２＋ ）ｃＪＪ ］ ●●● 。 ＝ ａ。ｂ ●●● 吼 ＋ＬＪ １ ）ｃＪ］ ｉ １＝ 【 ＝ １鲫 ＪＪ （６ｍ十 ） － ．． （２） ３建立网络模型 （１）在￡＝１时刻，初始网络模型Ⅳ（１）是一个具有６ 个顶点的完全三部图 依次将其三部分标号为 Ｂ（１），Ｂ（２）， （３），图１中的左图。 ５ 信息技术 （２）在ｔ＝２时刻，网络模型／、，ｆ２）是由３个初始网络 模型Ｎ（１）组成的。从每一模型Ⅳ （１），ｉ∈【ｌ，３】中选出在同 一２０１７年（第４６卷）第６期 ４网络模型Ｎ（ｔ）的拓扑性质 下面将以定理的形式详细讨论文中模型Ｎ（ｔ）所具 部分中的两个顶点构成顶点集合Ｂ。∽√∈【１，３］，然后 用选定的这三部分中的６个顶点在网络运算映射厂【２】 有的拓扑性质。下，相互连接构成一个新的完全ｊ部图 ，称它为模 型Ｎ（２）的中 ｔＬ，图，也称核心图，简单记为ｄＰ（２），图ｌ中 的中间图。 （３）在ｔ≥３时刻，网络模型Ｎ（ｔ）是由３个网络模型 Ｎ（ｔ—１）组成的，依次记为 —ｌ ∈［１，３］。从每一个模 型Ｎｉ（ｔ一１ ∈［１，３］的核心图ｑｂｊ（ｔ一１）中选出在同一部分 中的两个顶点构成顶点集合Ｂ （ｊ），ｊＥｌ１，３Ｊ，然后让这６ 个顶点在网络运算映射 卜下连接组成模型Ｎ（ｔ）的中 心图 ∽，见图２。 这样的循环迭代运算（网络运算映射厂）过程可以 进行无限次，直至达到所需的网络规模．在ｔ时刻后，模 型Ｎ（ｔ）的顶点数（模型的阶）和边数（模型的尺寸）分别 如下 ｔｖ（ｔ）ｌ＝３１Ｖ（ｔ一１）１＝３ ｗ（１）ｌ：２×３ （３） ＩＥ（ ）Ｉ：３１Ｅ（￡一１）Ｉ＋鱼！ ：２×３ ．－一６ （４） 婚静 图１ Ｎ（１），Ｎ（２）和Ⅳ（３） ①Ｎ（ｔ一１） 图２模型Ｎ（ｔ１ ６ ４．１平均度＜ｋ＞ 作为一个网络模型的重要结构参数（拓扑参 数）——平均度＜ｋ＞，体现了所建构模型的稀疏性 （ｓｐａｒｓｅ），其拓扑定义为：网络模型所具有的边数目的２ 倍与网络顶点数目的比值，即 ＝ （５） ｔ时刻之后，网络模型Ｎ（ｔ）的平均度 ＜ ＞： ６，是一个很小的数值，满足性 ｘ ｊ 质（ａ），所以说模型Ⅳ（ 具有稀疏性。 ４．２聚类系数 作为另一个定量描述网络拓扑性质的参数——聚 类系数，它刻画了网络的集聚程度（整体和局部）。例 如：在研究者合作网络中，每一个小团队中的成员之间 的合作是相当紧密的，既而在他们之间会形成很强的 互动联系，然而每一个团队之问的联络就没有如此的 紧密了，并不是两个团队中的每一个人都参与互动，只 是每个团队中的个别人（领头人）与另一个团队中的个 别人（领头人）发生联系，通过这种互动关系依次逐渐 形成了更大的合作网络。在拓扑学中，顶点ｉ的聚类系 数Ｃ．被定义为与顶点ｉ相连的三角形的个数和顶点ｉ 相连的三元组的个数的比值，即 Ｅ（￡） （６） Ｆ 式中Ｅ （￡）表示模型Ｎ（ｔ）中顶点ｉ的邻居顶点之间 实际存在的边数， ．（ 。一１）／２表示模型Ⅳ（￡）中顶点ｉ的 邻居顶点之间最多可能存在的边数。对于整个网络而 言，聚类系数ｃ 丽Ｃｉ。据此可以得到模型，ｖ（ｚ）中 每个顶点的聚类系数，见表１如示。 表１ 则整个网络的聚类系数 ｃ＝ 南＝ ＪＰ ｃ（ ）＝善；× ＋ ×＿４ ２＞。＿５２４（７） ２０１７年（第４６卷）第６期 信，皇，技术 图３整个网络模型Ｊ７、ｒ∞的聚类系数 可以看出模型Ⅳ 具有很高的聚类性，满足性质 （ｃ）．当１＜ｔ≤１００时，模型Ⅳ∞的聚类系数变化曲线可 以参看图３。 从上述表格中易见：对于顶点度为ｋ＝４ｉ（ｉ足够的 大）的顶点而言，其聚类系数符合如下的方程 ｃ ２×ｋ （８） 满足性质（ｄ），所以说文中的模型Ⅳ∞具有等级结 构性。 ４．３度分布 网络模型的度分布是衡量模型是否具有某种特性 （例如：无标度特性——度分布服从幂率分布，指数分 布特性——度分布服从指数分布）的拓扑参数，文献 ［１ １］中Ｄｏｒｏｇｏｖｔｓｅｖ提出了对于确定型演化模型度分布 的计算公式，即： ∑ Ｐ一 （９） 上式中ｎａｔ）表示ｔ时刻顶点度数等于ｋ 的顶点数 目。为此，给出模型Ｊ７、ｒ∞的顶点的度谱表格，如表２所示。 表２模型Ⅳ（ｆ）的顶点的度谱表格 可以看出：顶点的度谱是一列离散的实数数值。 对于度值为ｋ＝４（ｔ—ｔ ＋１）的顶点而言，根据公式（９）有 ｌｊ一１ Ｐ－． ＝— ２＋４∑３ ＝３ ～＝３×３ 一＾ （１ｏ） Ｕ 模型ⅣＯ）的累积度分布服从指数分布，满足性质 （ｂ），说明该演化模型是指数分布型网络模型。 ４．４直径和平均距离 大量的实验数据表明生活中许多演化网络拥有小 世界效应，即：随时间的推移，演变模型具有小的直径 Ｄ和低的平均距离 。在获知模型Ⅳ 具有指数分布 特性后，这一部分将证明它的小世界效应。鉴于文中 模型Ｎ（ｔ）的特殊构造过程，直径Ｄ和平均距离 的表 达式将被呈现在下面的定理中。 定理１在ｔ时刻，模型Ｊ７、『 的直径Ｄ 为 １ｆＤ ＝２ｔ一１，ｔ≥２ ，１ １、 Ｄ（１）＝２，ｆ＝１ 证明：当ｔ＝１时，模型Ｎ（１）就是一个完全三部图 ，易知其直径Ｄ（１）＝２，符合定理１中陈述；当ｔ＝２ 时，模型Ⅳ（２）是由３个完全三部图 组成的，易知其 直径Ｄ（２）＝３＝２×２—１，也符合定理１中陈述；当ｔ≥３ 时，模型Ⅳ ） 由３个Ｎ（ｔ一１）构成的。从图２中可以得 出：直径ＤＯ）的长度是一条始点ｉ和终点．，属于不同组 成部分ⅣｌＯ一１）ｑｅ［１，３］）的路的长度，否则，假设始点ｉ 和终点 在同一个 一１）（１ｅ［１，３］）中，显然一定有 ｄ Ｏ一１）≤Ｄ 一１）成立，那么就会有如下的不等式链 ｌＤ ≤Ｄ 一）二１ ≤…≤Ｄ（２）＝３ 一 ． （１２） 但这是矛盾的，既而假设错误．由于模型Ⅳ 具有 很好的旋转对称性，不防设顶点ｉ属于Ｎ。 一１），顶点ｊ： 属于Ｎ２（ｔ一１），那么直径Ｄ 就是 Ｄ ＝ｄ讲㈣ ＋１＋ ㈤ （１３） 式中ｄ哪， 等于顶点ｉ到Ⅳｌ 一１）中核心顶点 Ｈ（ｔ，１）（数目是两个）的距离， ㈤ 等于顶点 到 Ｎ２（ｔ一１）中核心顶点Ｈ（ｔ，２）（数目是两个）的距离。由上 述方程（１３）可知 ｆｄ／／／０，１） ＝ －Ｔｊ…ｔｉ￣ｓ，ｚ） ｖｉ， （ｆ）＝ ． ４ 联立（１３）和（１４），在初始条件Ｄ（２）＝３下便可以得 到 』Ｄ（ ＝ ＋ｌ＋ －２（ｔ—１）＋１＝２ｔ－１，ｔ＞１ （１）＝２， １ （１５） 证毕。 可以看出，随着时间ｔ的推移，直径Ｄ ＝２ｔ一１与 ７ 信息技术 ２０１７年（第４６卷）第６期 顶点个数ＩＶ（ｔ）ｌ＝２Ｘ ３ 的自然对数值是同阶的，即： ２ｔ一１ ｏｃＩｎ３Ｘｔ＋Ｉｎ２， 一。。），满足性质（ｅ）。 接下来讨论模型ⅣＯ）的平均距离 。 定理２在 时刻，模型Ⅳ０）的平均距离 为 ＋ ： 赤 号争 ２ 证明：当ｔ＝１时，模型Ｎ（１）就是一个完全ｉ部图 ，则 ＝ ＿１．２。当ｆ＝４时， 的计算过程将在文章末尾的附录Ｉ中以例子呈现， 仅供参阅。当ｔ＞２时，模型Ⅳ（￡）中所有顶点对ｉ和 的 距离ｄｉｊ（ｔ）的和ｄ０）＝∑ｄ 满足如下递推公式 ｄ（ｔ）＝３ｄ（ｔ一１）＋△ —１）． （１７） 式中△Ｏ一１）表示属于ⅣＯ）中不同小块 一１） ∈【ｌ，６］）（见图４）的任意一对顶点Ｕ和 距离之 和，即：ａ（ｔ—１）＝∑ｄ （￡）。通过Ⅳ（￡）的构造过程，可 以重写Ａ（ｔ一１）为 ・２ ｏ（ｔ－１）＋［ … 依据对称性可知 ∞－１（￡ １））＝＝ ∑｛√ｉ ：０ ｌ（ｆ～１， ）ｌＪ∑Ｊ ０ ＝ （ｄ（￡一１， ）＋ｄ（） ｔ－ｌｊ））Ａ（ｔ－ｌ√）］ｌ Ｊ）｝ （１９） 式中ｄ０—１， 表示在同一个小块ｏｑ（ｔ一１） ∈【ｌ，６１） （见图４）中到核心顶点Ｈ（ｔ，Ｄ距离ｉ＝ｄ（ｔ—ｌ，０，Ａ（ｔ一１，０ 表示了在同一个小块 （ｆ一１）（／ｅｌｌ，６Ｊ）中到核心顶点 Ｈ（ｔ，Ｄ距离为ｉ＝ｄ（ｔ一１， 的顶点数目（可以参看附 录Ⅱ）．结合模型的构造过程和附录Ⅱ，有如下的一组 方程 Ａ（ｆ，０）＝１，Ａ（ｔ，１）＝２￡，Ａ（ｉ， ）＝０￡＞户 ．Ａ（ｉ， ）＝２ Ａ（￡，ｉ）＝Ａ（￡一１，ｉ）＋２Ａ（￡一１， 一１） Ａ（ｔ—ｌ，ｉ）＝Ａ（￡一２，ｉ）＋２Ａ（￡一２．ｉ－１） ８ ． 。 ‘ Ａ（ ＋ ， ） （ ， ）＋２Ａ（ｉ，ｉ－１） （２０） 易得Ａ（ｔ，ｉ）的递推公式 Ｉ ＝Ａ“，０＋２ＺＡＯ，ｉ一１） Ａ（ｔ， ｌ一 １ （２１＼ ，） ：２‘＋２￣ＡＯ＇，ｉ－１１ 』＝ｉ 进一步可得 ＝ ｉ）＋２ｙＡ（ｉ ，ｉ。一１） ｆ—Ｊ， ２—１ 、 ＝Ａ（ｔ，ｉ．） ２ ＋２∑｝Ａ（ｉ。一１， 。一１）＋∑Ａ（ｉ，， 。一２）｝ ２ ｌ＼ ｌ－１ ｆ ｒ一１ 一１ ｉ２—１ ｆ—Ｉ ｉ２—１ Ｉ１一 ＼ ＝２ Ｉ＼ １＋∑＋ｉ２ ｉ１‘∑∑＋…＋∑∑…∑Ａ！ ｉｌｉ３ ｉｌ一１ ｉ２＝ｉｌｉ ｉＪ ＿。 ｉ ＝２ （ｉ １）ＩＪ （２２） 联立方程（１７）一（２２）以及应用０运算可得 ３ ＋ 计算并化简可得方程（１６），证毕。 图４模型Ⅳｒ３）和Ⅳ 的剖分 ２０１７年（第４６卷）第６期 信，电技术 当￡ ｏ。时，网络模型Ⅳ 的平均距离 一百４ｔ。 网络模型Ⅳ 的顶点数目的对数为ｔＩｎ３＋ｌｎ２，则 子生成树的叶子数目为Ｌｕ∞等等。下面我们不加证明 地给出如下推论： ｝ 鲁＝Ｄ（１），满足性质∽。当１＜ ≤１００时，模型 子生成树 Ⅳ 的平均距离变化曲线见图５。 （ 推论１ ｔ时刻之后，模型Ｊ７、ｒ∞的任意的两个最多叶 和 的顶点集合满足 ） ｖ（ｔ一２） （２４） ）ｎ （ 可以看出模型Ⅳ 符合命题１，说明Ⅳ 是小世界 网络模型。 定理３ ｔ时刻之后，模型Ⅳ∞的最多叶子生成树的 叶子数目 ∞为 ∞＝４Ｘ３ ‘ （２５） 证明：通过分析及图２可知，在Ｊ７ｖ（ｃ）中，只有当每一 个Ｎ（ｔ—１）都是最多叶子生成树时，Ⅳ∞的生成树才具 有最多的叶子，因此有 』ｌ ：Ｌ ３ｆ１）＝４ × 一１） 计算知 （ｆ）＝４×３ ，证毕。 （、２。６ ） ５结束语 图５整个网络模型Ⅳ∞的平均距离 ４．５最多叶子生成树 本论述以完全三部图 为基本的构成元素，通 对于一个给定的模型，它的生成树的数目不仅是 一过循环迭代的运算映射．厂，构造了一类复杂网络模 个不变量，而且还刻画了它的安全可靠性、随机游 型。通过计算该模型的平均度和顶点的累积度分布， 获知该模型不仅是稀疏的，而且具有指数分布特性；理 论分析和数值仿真均表明，该模型具有小世界效应， 即：高的聚类系数、小的直径和低的平均距离；最后，利 用特殊的演化过程，获得了它的最多叶子生成树的叶 子数目．希望文中的研究方法能有助于今后复杂网络 的研究 ＿３２】，后续将开展进一步的探索，不仅通过丰富 基本元素之间的连接方式，而且结合概率，增加网络演 化的随机性，以期获得更加符合现实网络的演化模型。 走、优化同步性以及渗流效果．对于一个给定的有限图 而言，它的生成树的数目都能通过Ｋｉｒｃｈｈｏｆｆ＇ｓ矩阵树理 论得到，即该图的Ｌａｐｌａｃｉａｎ矩阵的所有非零特征根的 乘积，这仅仅只是一个理论分析，面对成千上万个顶点 的庞杂网络模型，一般的计算机在短时间内不可能获 取相应的数值，如何找到有效可行的好算法，已经成为 一个迫切、有待深入研究的问题。在近几年已发表的 文章中 圳，作者们针对每一类特殊的模型，提出了一 类计算生成树数目的循环算法．作为一类特殊的生成 树——最多叶子生成树，其指的就是网络模型中用最 少的顶点来控制最多的一度顶点（叶子）的一类树。在 附录Ｉ 的计算过程 按照对模型Ⅳ（４）的剖分过程，依次给每一个小块 标号为ｎ （３），ａ２（３），ａ３（３），ｃＬ４（３），ｏ５（３），ｃｌ６（３）。当顶点 实际网络中它有着广泛的用途，例如：在一个时序Ｉｎ． ｔｅｒｎｅｔ中，大量的用户都是一度顶点，并且随着时间的 延续，这类用户的活动是最频繁的，即很频繁地进人网 多叶子生成树是很有必要的。 Ｕ和ｖ都在同一个分支ｃｔ，（３）（ｉ∈［１，６］）时，它们之间的距 离记作ｄ ，则有∑ｄ ＝ 。当顶点ｕ和ｖ不在同一 。络、退出网络、重新与其他顶点连接等等，所以研究最 个分支￣ｔｉ（３）（ｉＥ［１，６］）时，由于旋转对称性，不妨设ＵＥＧ （３）、ＶＥＯ２（３），它们之间的距离记作ｄ ，则有 在文献乜 圳中，作者们已经对最多叶子生成树进行 了初步的研究，提出了控制顶点集合（Ｄｏｍｉｎａｔｅ—Ｖｅｒ－ ∑ｄ ＝ （３）．应运网络运算０，则有以下方程 ｖｅ ｅｒ，（３） ｔｅｘ－Ｓｅｔ），简记为Ｄ—Ｖ—Ｓ，平稳集（Ｂａｌａｎｃｅ—ｓｅｔ），最多叶 ０（３）的表达式： ９ × （Ｕ ）ｃＪ］ ｏｏ Ｊ ＝ ４９２ （３４） ｒ１ Ｘ０、 （３）＝ ６ｘ ｌｒ１ Ｘ０、 ８Ｘ３ ２“） ２ ８×３ （２．４） ｌ。ｌ ２ Ｉ＝ Ｕ（２＋ ） ＝０ Ｊ ＝ｏ ＝ｏ Ｊ ６× （Ｌ， ＋ ） 附录１Ｉ： （２７） ． １ ｌ × × × Ｊ 表１模型Ⅳ∽中的Ａ（ｊ，０和ｄ０＇，０ ８× （Ｕ３＋ｄＪ）ｃＪ］ ＝５４＋４８６＋１２９６＋１０８０＝２９１６ 既而，有Ａ（３）： ］ 叫卅叫一－１］ Ｊ］ Ｊ ｆ＝： △（３）＝１２（２１９６＋７２９）＝３５１００ （２８） 为了获得△（１）和Ａ（２），同理有以下的方程 ０（２）的表达式： ｒ１ＸＯ、 ｆ，１×Ｏ、 （２）＝ｌ ４×１４×２ ｌ／ｌ ２．３） ０Ｉ ４Ｘ ４Ｘ２１ ３ｌ ） ＝ （２９） （３Ｏ） ０）（２ ｘ０） 嚣 图５模型Ⅳ（４）的平均距离 的图示 △（１）的表达式： △（１）＝１２（１２＋９）＝２５２ （３２） 联立方程（２７）一（３２），再根据公式（２３），便有ｄ（４） 的表达式 ｄ（４）＝３３ｄ（１）＋３ △（１）＋３△（２）＋△（３）＝４８５４６ （３３） 根据公式（１６），可得到模型Ⅳ（４）的平均距离 １０ ： ２ ＋ ０ ＝ ＠ 参考文献： ［１］Ｅｒｄｏｓ Ｐ，Ｒｅｎｙｉ Ａ．Ｏｎ ｒａｎｄｏｍ ｇｒａｐｈｓ［Ｊ］．Ｐｕｂ１．Ｍａｔｈ．１９５９ （６）：２９０—２９７． １２ Ｊ Ａ．一Ｌ．Ｂａｒａｂｒｓｉ，Ｒ．Ａｌｂｅａ，Ｈ．Ｊｅｏｎｇ Ｍｅａｎ—ｆｉｅｌｄ ｔｈｅｏｒｙ ｆｏｒ ＳＣａｌｅ＇ｆｒｅｅ ｒａｎｄｏｍ ｎｅｔｗｏｒｋｓ Ｐｈｙｓｉｅａ Ａ．１９９９（２７２）：１７３—１８７． 【３ Ｊ Ｄ．Ｊ．Ｗａｔｔｓ，Ｓｍａｌｌ Ｗ０ｒ１ｄｓ： Ｉ＇Ｉｌｅ Ｄｙｎａｍｉｃｓ ｏｆ Ｎｅｔｗｏｒｋｓ ｂｅ． ｔｗｅｅｎ Ｏｒｄｅｒ ａｎｄ Ｒａｎｄｏｍｎｅｓｓ（Ｐｒｉｎｃｅｔｏｎ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ， Ｐｒｉｎｃｅｔｏｎ，ＮＪ，１９９９）． １４ Ｊ Ｄ．Ｊ．Ｗａｔｔｓ ａｎｄ Ｓ．Ｈ．Ｓｔｒｏｇａｔｚ，Ｃｏｌｌｅｃｔｉｖｅ ｄｙｎａｍｉｃｓ ｏｆ ｓｍａｌｌ— ｗｏｒｌｄ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ．１９９８（３９３）：４４０—４４２． ［５］Ｍ．Ｅ．Ｊ．Ｎｅｗｍａｎ，Ｄ．Ｊ．Ｗａｔｔｓ．Ｐｈｙｓ．Ｌｅｔｔ．Ａ ２６３（１９９９）３４１． ［６］Ｍ．Ｅ．Ｊ．Ｎｅｗｍａｎ，Ｄ．Ｊ．Ｗａｔｔｓ．Ｐｈｙｓ．Ｒｅｖ．Ｅ ６０（１９９９）７３３２． ［７］Ｒ．Ｋａｓｔｕｒｉｒａｎｇａｎ．ｃｏｎｄ－ｍａｆｆ９９１Ｍ０５５（１９９９）． ［８］Ｊ．Ｋｌｅｉｎｂｅｒｇ．Ｎａｔｕｒｅ．４０６（２０００）８４５． １９ Ｊ Ｚ．Ｚ．Ｚｈａｎｇ，Ｂ．Ｗｕ，Ｙ．Ｌｉｎ．Ｃｏｕｎｔｉｎｇ ｓｐａｎｎｉｎ。ｇ ｔｒｅｅｓ ｉｎ ａ ｓｍＭ１一ｗｏｄｄ Ｆａｒｅｙ ｇｒａｐｈ，Ｊ．Ｐｈｙｓｉｃａ Ａ，３９１（２０１２）３３４２— ３３４９． ［１０］Ｚ．Ｚ．Ｚｈａｎｇ，Ｌ．Ｌ．Ｒｏｎｇ，Ｃ．Ｈ．Ｇｕｏ．Ａ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｓｍａｌｌ— ｗｏｄｄ ｎｅｔｗｏｒｋ ｃｒｅａｔｅｄ ｂｙ ｅｄｇｅ ｉｔｅｒａｔｉｏｎｓ［Ｊ］．Ｐｈｙｓｉｃａ Ａ．３６３ （２ｏｏ６）５６７—５７２． ［１１］ Ｓ．Ｎ．Ｄｏｒｏｇｏｖｔｓｅｖ，Ａ．Ｖ．Ｇｏｈｓｅｖ，Ｊ．Ｆ．Ｆ．Ｍｅｎｄｅｓ．Ｐｈｙｓ． Ｒｅｖ．Ｅ ６５（２０ｏ２）００６６１２２． 【１２ Ｊ Ｂ．Ｙａｏ，Ｍ．Ｙａｏ，Ｘ，Ｅ，Ｃｈｅｎ，Ｘ．Ｌｉｕ，Ｗ．Ｊ．Ｚｈａｎｇ，Ｒｅ— ｓｅａｒｃｈ ｏｎ Ｅｄｇｅ—Ｇｒｏｗｉｎｇ ｍｏｄｅｌｓ ｒｅｌａｔｅｄ ｗｉｔｈ ｓｃａｌｅ－ｆｒｅｅ ｓｍａｌｌ—ｗｏｒｌｄ ｎｅｔｗｏｒｋｓ［Ｊ］，Ａｐｐｌｉｅｄ Ｍｅｃｈａｎｉｃｓ ａｎｄ Ｍａｔｅｒｉ－ ａｌｓ，Ｖｏｌｕｍｅｓ ５１３－５１７，２０１４． 【１３ Ｊ Ｃ．Ｍ．Ｓｏｎｇ，Ｔ．Ｋｏｒｅｎ，Ｐ．Ｗａｎｇ，Ａ．一Ｌ．Ｂａｒａｂａｓｉ，Ｍｏｄｅｌ— ｌｉｎｇ ｔｈｅ ｓｃａｌｉｎｇ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｈｕｍａｎ ｍｏｂｉｌｉｔｙ［Ｊ］．Ｎａｔｕｒｅ Ｐｈｙｓｉｃｓ．２０１０（１７６０）：１－６． ２０１７年（第４６卷）第６期 信息技术 （上接第８５页） 好的服务于广大基层患者。 参考文献： 于传统刷片，主要是因为传统刷片涂片面积较大，涂片 过厚，细胞受外力破坏，涂片时有些细胞重叠，结构不 ［１］武春燕，王彦丽，陈岗，等．液基细胞学在肺癌支气管刷片 检查中的应用价值［Ｊ］．同济大学学报（医学版），２００９，３０ （３）：６５—６９． 清，标本固定不及时导致细胞风干变形。与传统涂片 方法相比，离心法利用细胞黏附原理，使用特殊的细胞 基液将脱落细胞混匀，去除粘液及红细胞，然后进行离 心甩片，细胞丰富，背景清晰。 国产离心法液基细胞制片系统是一种改良的细胞 ［２］陶玉，何松，吉志固．４种液基细胞制片的比较ＥＪ］．临床与 实验病理学杂志，２００９，２５（５）：５５９—５６１． ［３］ 国宏莉，唐幕湘，田林，等．宫颈液基细胞学检查国内外方 法的对比研究［Ｊ］．西部医学，２００９，２１（９）：１５２４－１５２６． ［４］王娅．１Ｉ．Ｔ与ＴＣＬ两种液基细胞学技术应用对比分析［Ｊ］． 河北医学，２０１３，１９（４）：５５８—５６１． 学制片技术，由于其本身的优点，是支气管镜刷检诊断 肺癌是一种可靠方法。且由于其操作简便，省时省力， 成本低廉，质量稳定，更适合基层单位广泛开展，能更
