英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

一个新的网络类的结构性质和复杂性：Collatz步数图表

Frank Emmert-Streib*

英国贝尔法斯特女王大学医学院健康与生命科学学院医学和生物医学学院癌症研究和细胞生物学中心计算生物学和机器学习实验室

摘要

在本文中，我们介绍一个生物启发模型来生成复杂的网络。 与迄今为止引入的其他许多网络建设程序相比，我们的方法根据一维符号序列生成网络，这些符号序列与数量理论中所谓的Collatz问题有关。本文的主要目的是首先从Collatz问题中导出一个符号序列，我们称之为步序列，并研究它的结构特性。其次，我们介绍基于这些步骤序列的增长网络的构建过程。第三，我们研究这个新的网络类的结构特性，包括它们的有限尺度和它们的复杂性，平均最短路径长度和聚类系数的渐近行为。有趣的是，与包括Watts＆Strogatz的小世界网络在内的许多其他网络模型相比，我们发现CS图随着尺寸的增大而变得更小。

引言

网络分析是一个繁荣的领域，涵盖了从生物学，数学和统计学到社会科学等许多学科[1-6]。从研究随机网络开始[7]，社区的兴趣近年来转移到所谓的复杂网络[8,9]。与节点度数呈泊松分布的随机网络相比，许多复杂的网络表现出幂律分布[8,10]。复杂网络中的关注可能至少部分归因于它们似乎无所不在的事实。这使得这种网络不仅从理论上而且从实践角度都很有趣[11-13]。

本文的主要目的有三个。首先，我们从Collatz问题导出一个符号序列，我们称之为一个步序列。Collatz问题[14,15]来自数论，它指的是从任意自然数开始的数学表述，某个数学函数的迭代应用总是可能通过中间自然数导致数1。因此，Collatz问题导致自然数的一维符号序列的生成都以1结束。其次，我们介绍一种基于Collatz问题的步长序列的新的生长网络构建过程。出于这个原因，我们称之为结果网络CS（Collatz步骤）图。这将同时导致定义一类新的复杂网络。第三，我们研究步骤序列和CS图的结构复杂性和缩放行为，包括对CS图的渐近复杂度的估计。

与迄今引入的许多其他生成网络的生成过程[2,16-18]相反，我们的方法从与Collatz问题相关的一维符号序列构建网络[14,15]。我们想强调，我们不是第一个将一维对象映射到网络的。例如，对于时间序列数据，已经在[19-24]和[25,26]中完成了素数相关网络的构建。一个更古老的构造原理例子可以在[15]中找到所谓的Collatz图。在本文中，我们结合[15]中的工作，然而，从可以从Collatz问题导出的不同类型的序列构建网络。有趣的是，我们会证明Collatz图和CS图完全不同，我们会认为这与底层序列的不同有关，分别是它们复杂性的差异。

在这种情况下，值得注意的是Collatz问题的猜想迄今在数学上未经证实。然而，它已经被数值验证，直到自然数高达[27]。 由于这个原因，可以假设这个复杂的问题能够产生真正复杂的符号序列。

我们的网络模型的动机是基于生物细胞的工作机制。在一个细胞中，DNA的线性符号序列被转录成mRNAs，然后被翻译成蛋白质，形成蛋白质相互作用，信号或其他类型的基因网络[28-30]。这意味着我们的建设程序，如果与众所周知的产生不断增长的网络的数学机制相比，起初可能显得非常规，实际上这些程序本质上是在使用。除此之外，我们想要注意的是，蛋白质相互作用网络和信号网络可以被认为是复杂的，不仅因为它们在其程度上展现幂律分布，而且因为这些网络构成活细胞功能的组成部分。此外，研究表明，DNA序列本身也可以被认为是一个复杂的符号序列[31,32]。这表明DNA序列的复杂性延伸到基因网络的复杂性。在这种情况下，似乎可以假设没有任何任意的DNA序列导致复杂的（基因）网络，但DNA序列本身需要是复杂的。从抽象的角度来看，我们通过利用生物对应物的机制将我们的网络模型建立在这些观察中。具体而言，我们使用与Collatz问题相关的符号序列[14,15]作为我们模型的起点。

本文组织如下。在下一节中，我们将介绍我们分析所需的所有数学定义和初步知识。此外，我们定义步骤序列，CS图和我们的程序来生成增长网络。在结果部分，我们展示了我们对步骤序列和CS图的分析，研究了它们的复杂性和缩放行为。此外，我们提供了CS图的渐近复杂度，平均最短路径长度和聚类系数的估计。本文结束后进行讨论和结论。

方法

在本节中，我们将介绍我们需要介绍我们的网络模型的基本定义和注释。这包括Collatz问题的简要描述，只要我们的分析是必要的。

基本定义：Collatz问题，序列和图形

根据以下映射的迭代应用为每个自然数n [N]定义Collatz序列。

(1)

例如，对于，我们得到序列。这个序列被称为的Collatz序列。前20个自然数的其他例子可以在图1中找到。这意味着公式的迭代应用1将步后的自然数映射为1，即。公式的进一步应用1不能导致其他结果，因为1是上述映射的一个固定点。如果将自然数视为转换的状态，则可以通过相邻状态之间的连续映射在状态空间中将上述序列可视化。图1显示了前20个Collatz序列的状态空间的可视化。由于状态空间是离散的，因此它的表示对应于一个网络。这个网络被称为Collatz图[15]。

我们想指出的是，状态空间中的元素的数量对应于从初始自然数n到1遍历的自然数的数量。然而，我们想强调这些元素不一定对应于连续的自然数1,2,3，... n。如果考虑一组序列的状态空间，例如，那么这个状态空间中元素的个数就是各个序列元素的并集，即。有趣的是，有两种状态可以自然地相互区分。第一类状态由自然数n组成，它们被用作初始值来生成Collatz序列，而第二类状态是具有值大于n的状态。为了可视化这一点，在图1中，我们以灰色显示第一种类型的状态，以橙色显示第二种类型的状态。

基于上述公式1中的映射，Lothar Collatz在1937年推测每个自然数，将通过迭代应用映射到1。这也被称为3n 1猜想或Syracuse问题[33,34]。迄今为止，这个猜想仍然在数学上未经证实，然而，数字上它已经被验证达到 [27]。在本文中，我们不会关注这个猜想的证明，而是关于步骤序列的配置，这可以从Collatz问题中得出，如下一节所讨论的。

步序列和CS图

除了应用产生的状态空间外，还有其他不同的符号序列可以基于得到。 在下面，我们将推导出这样一个符号序列。 为了正确定义我们的新符号序列，我们需要引入两个函数和。第一个函数，

(2)

定义从自然数n到T（n）映射到1所需的迭代步数t的映射。因此，我们称为阶梯函数。基于和，我们定义了第二个映射如下

(3)

这意味着是矢量值函数，其分量由 ）进行索引。 函数允许产生长度为n {1的元素序列，其元素在N中取值。例如，产生序列（1,7,2,5）。 进一步的例子可以在图2中找到。我们将由生成的符号序列称为步序列，因为该序列的每个分量i的值对应于映射T需要应用的迭代步骤的数量 将iz1映射为1.在下面，我们简写为.

对于步骤序列，存在以网络形式的自然表示。更准确地说，让步骤序列的不同元素对应于网络的顶点V，并且边缘E由步长序列的长度为2的连续子序列定义。

定义：CS图

我们定义一个Collatz步骤图，简单地称为CS图，并用表示一个步序列，方法如下。 顶点集:

(4)

边缘设置：

(5)

图1. Collatz序列和Collatz步骤图。左：Collatz序列的例子，为前20个自然数。 右图：这些序列的网络结构被称为Collatz步骤图。

加权边集：

（6）以这种方式定义的网络是有向和加权的，并且边权重采用的值，而对应于状态k在阶序列上遵循状态m的次数。在数学笔记中，我们要说的是，由于Collatz步骤图是基于步序列构造的，因此生成的网络被索引为n。 这意味着对于每个ngt;1，都能获得一个CS图。

在图2中，我们将显示的步骤序列。

（7）

如图2的底部所示。由于这个网络中的顶点对应于将某个自然数映射到1的步骤数，而不是自然数n本身也不是Collatz序列的中间数，与图1中的Collatz图比较后，我们在CS图中用不同的节点颜色来强调这些元素的含义。在图9中，我们显示了更复杂的CS图，左边是和右边是。在这种情况下，网络由141 - 287个节点和356 -3201个边缘组成。

描述性地，CS图的定义可视作通过遍历从第一个元素到最后一个元素的步骤序列（对应于网络中的顶点）以及通过用边连接连续的元素。如果步骤序列中的某个元素已经出现在更早的步骤中，则不包含新的顶点，只包含该顶点的边。

图2. Collatz步骤图。 左：作为n函数的阶梯函数结果。 底部：基于阶跃函数结果的步序列。 右：由可以构造CS图。

增长网络模型

使用上一节中的定义，可以为CS图制定一个增长网络模型，称为GMCS。这意味着这个模型生成了一个CS图，作为自然数的函数。算法1正式描述了这个模型。我们用阶序列来表述GMCS，但是，我们想指出，一个等效的公式可以通过使用阶函数来实现，因为根据公式3可以写成：

（8）

有趣的是，与其他许多增长型网络相比，例如随机网络或无标度网络，CS图的构造原理是不同的。这些模型的不同之处在于，由给出的一维符号序列被用于确定网络的增长。在结果部分中，我们研究了步骤序列的不同结构方面与生成的CS图的关系。我们的模型和其他网络的另一个区别是，对于固定的n，总是得到完全相同的图。这是由于下面的步骤是确定的。但是，我们将说明生成的网络展现出了惊人的复杂性。

结果

在下文中，我们首先研究步序列的特征及其缩放行为，接着我们调查CS图的缩放行为和这些网络的复杂性。

算法1 GMCS：CS图的增长网络模型。

2. 初始化：
3. 计算：
4. ，则
6. 结束
7. 如果，则
9. 结束
10. 如果，则
13. 否则
15. 结束

19.i=i 1

20.终止循环

阶序列的性质和标度

为了量化阶序列H的行为，我们首先计算了长度为的阶序列的自相关函数R。图3中 A显示了在双对数图中R的可视化。在那里可以看到，在滞后lag=10000时，在移位序列之间仍存在相对较高的相关性（高于预期的随机序列），表明存在长期记忆。通常，一个符号序列中存在的长期记忆被认为是一个指示符序列的复杂性。我们通过对自相关函数的对数和滞后进行线性回归来量化这一观察结果，

(9)

(10)

自相关函数R的无标度特性为阶序列的复杂性质提供了量化证据。

的复杂性的另一个指标可以借助于对于步骤的偶数和奇数元素获得的两个直方图序列。更确切地说，我们定义了以下两个序列关于偶数n，

(11)

(12)

和的直方图如图3中B图所示。可以看出，两个直方图可以清晰地区分开来，表明的奇数和偶数元素之间的细微差别。对于这种效应的可能解释可以在基于的Collatz序列的不对称构造，在公式（1）中给出。因为这个映射不同地处理偶数和奇数。然而，这种行为并不是微不足道的，因为如果序列？和？用于其计算（结果未示出），偶序列和奇序列元素的不对称性不存在于自相关函数R中。

我们研究的最后一个属性是平均步数的缩放行为，，需要映射收敛，这对应于到达其定点的时间。更确切地说，我们定义，

(13)

并执行线性回归？步长序列长度的对数。这给出了一个比例因子并且p值为。从我们的结果可以看出， t与n的对数增长十分相似，这意味着即使对于大到的自然数，映射T也仅执行大约次的迭代步骤。

CS图的复杂性和缩放

现在我们转向研究CS图的结构性质。我们首先研究边权重的缩放。对于（绿色，红色，蓝色）获得的三个不同CS图的缩放结果显示在图4的双对数曲线中。确切地说，该图显示了边缘权重的频率分布的CS图。在这里，边缘权重对应于这些边缘在从第一个元素到最后一个元素遍历步骤序列时被访问的次数，如公式6.我们可以看到，所有三个网络渐近地遵循一个几乎相同的的指数的幂律。此外，向更大的n值变化只影响幂律行为的范围，但不影响其指数。

接下来，我们研究CS图的有限和渐近结构复杂度。在过去的几十年中已经提出了很多措施来量化网络的复杂性[37-43]。但是，目前一般没有接受的可用金标准与符号序列的Kolmogorov复杂度相当[44-46]。

图3步骤序列的属性 A：Collatz步序列的自相关函数R。 B：的偶数和奇数序列元素的直方图。

图4 CS图中边权重的幂律缩放。颜色对应于（绿色，红色，蓝色）的不同尺寸

针对我们的具体情况和基于符号序列的CS图的构造，最近引入的称为边缘减少[47]的度量似乎是最合适的。边缘减少基于所谓的功率图，其通过对彼此相似的节点和边缘进行分组而从底层网络G获得。例如，如果一个顶点连接到一组其他顶点，那么这组节点在功率图中表现为一个节点，参见图5A。另一个例子是两组节点的双向连接，如

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[23755]，资料为PDF文档或Word文档，PDF文档可免费转换为Word