文摘

最流行的一种方法,评估网络的复杂性是衡量网络熵的不变量,如邻接矩阵或度序列。不幸的是,熵和所有entropy-based信息理论措施有几个漏洞。这些措施都是独立的一个特定的表示网络也不能捕捉生成过程的性质,生产网络。相反,我们提倡使用熵算法的复杂性定义网络的基础。熵算法(也称为Kolmogorov复杂度复杂性)评估的复杂性描述无损的娱乐所需的网络。这种方法不受特定选择的网络特性的影响,它不依赖于网络的方法表示。我们在香农熵和执行实验复杂性逐渐演进的网络。这些实验的结果复杂性的更健壮和可靠的测量网络的复杂性。论文的创新性的贡献包括引进一些新的entropy-deceiving网络和熵和实证比较复杂性作为网络构造复杂性的基本量的措施。

1。介绍

网络越来越重要在当代信息科学是因为他们提供了一个全面的模型代表了许多现实世界的现象。大量的数据交互在复杂系统允许网络科学描述,模型,模拟和预测行为和州这样的复杂系统。因此重要的是描述网络的复杂性,为了调整特定的网络分析方法。网络复杂性的度量对众多应用程序至关重要。例如,网络复杂性的程度可以确定网络内的各种过程发生的过程中,比如信息扩散、传播失败,操作与控制,或弹性保护。网络复杂性的结构已经成功地用于调查软件库(1),计算化学结构的属性(2),以评估质量的业务流程(3- - - - - -5),并提供网络的一般特征(6,7]。

复杂网络在许多领域的科学无处不在,如数学、生物学、化学、系统工程、物理学、社会学、和计算机科学,等等。然而,网络复杂性的概念缺乏一个严格的和公认的定义。一般来说,网络被认为是“复杂的”如果展品很多特性,比如小直径,高聚类系数,anticorrelation节点的度,存在网络主题和模块化结构(8]。这些特性是常见的在实际网络中,但是他们很少出现在人工随机网络。找到一个好的指标,可以估计的复杂性网络并不是一件容易的事情。好的复杂性衡量不应该仅仅依靠顶点和边的数量,但它必须考虑网络的拓扑特征。此外,复杂性并不等同于随机性或出乎意外。正如已经指出的(8的范围内),可能的网络,从最命令(派系、路径和明星)最无序(随机网络),复杂网络占据这个频谱的中心。最后,一个好的复杂性度量不应该依赖于一个特定的网络表示,应该产生一致的结果为各种表示相同的网络(邻接矩阵、拉普拉斯算子矩阵和学位序列)。不幸的是,目前的研究表明,找到一个好的复杂性测量适用于各种各样的网络是非常具有挑战性的9- - - - - -11]。

在许多可能的措施,可用于定义网络的复杂性,各种网络不变量的熵一直到目前为止最受欢迎的选择。网络不变量考虑定义entropy-based复杂性措施包括顶点的数量,数量的邻居,数量的邻居在一个给定的距离(12,顶点之间的距离13)、能源网络矩阵如Randić矩阵(14]或拉普拉斯算子矩阵(15),和程度的序列。通常有多个熵的定义,大致分为三个家庭:热力学熵统计熵,信息理论,熵。领域的计算机科学,信息理论的措施是最普遍的,它们包括香农熵(16),Kolmogorov-Sinai熵(17),和Renyi熵(18]。这些熵的概念是基于一个系统的信息内容,他们测量所需的信息传输对象的描述。利用信息理论的基本假设熵的定义是,不确定性(以熵)是一种不减少的可用信息的数量的函数。换句话说,系统的信息几乎没有的特点是低熵,因此被认为是“简单。“第一个想法用熵量化网络的复杂性来自Mowshowitz [19]。

尽管通用的熵定义的普遍性,但许多研究人员已经开发出专门的熵定义旨在描述网络的结构(10]。引人注目的例子,这样的定义包括该提议由吉等人的突然一个特定网络通过比较它的数量可能网络配置用于给定的一组参数(20.]。这个概念显然是受熵算法的启发,它定义了一个系统的复杂性的信息内容,但从其生成过程。一种不同的方法来衡量网络的熵引入了由德信息功能的形式21]。信息功能也可以用来量化网络熵的角度社区的顶点12,13)或独立的顶点集(22]。另一种方法提出了网络熵Korner,主张稳定的顶点集的使用为基础来计算网络熵(23]。几个综合的调查网络熵应用程序也可以(9,11]。

在信息科学领域,系统的复杂性通常是相关的,元素之间可能的相互作用的系统。复杂系统的发展随着时间的推移,他们甚至是敏感的小扰动的初始步骤开发和通常涉及重要的组成元素之间的关系。系统表现出高度的互联性结构和/或行为通常被认为是难以描述和预测,因此,这样的系统被认为是“复杂。“另一种可能的解释术语“复杂”的大小与系统。在网络的情况下,可以考虑使用顶点和边的数量来估计网络的复杂性。然而,网络的大小不是一个好的指示器的复杂性,因为网络有定义良好的结构和行为,一般来说,计算简单。

在这项工作中,我们没有引入新的复杂性度量或提出新的信息功能和网络不变量,entropy-based复杂性度量可以定义。相反,我们遵循观察制定(24]和我们提出的批评熵复杂度衡量建设的指导原则。因此,我们不使用任何特定的正式定义的复杂性,但是我们提供额外的参数为什么熵可能很容易欺骗当试图评估网络的复杂性。我们的主要假设是熵算法,也称为Kolmogorov复杂度,优于传统的香农熵算法由于事实熵更健壮,更少的依赖于网络表示,和更好的与直观人类理解的复杂性。

本文的组织如下。节2介绍相关的基本定义熵和我们制定反对使用熵作为衡量网络的复杂性。部分2.3entropy-deceiving网络提供了几个例子,提供动力和轶事证据对我们的假设。节3,我们引入Kolmogorov复杂度和展示这种方法可以应用于网络,尽管其高计算成本。实验的结果提出了熵和Kolmogorov复杂度的比较4。本文的结论部分5简要总结和未来工作议程。

2。熵作为衡量网络的复杂性

2.1。基本的定义

让我们介绍一下基本的定义和本文的其余部分中使用的符号。一个网络是一个有序对 ,在那里 是一组顶点和 是一组边缘。的学位 的顶点是,相邻的顶点数 。一个给定的网络可以用在许多方面,例如,使用一个邻接矩阵定义为

另一个邻接矩阵是网络的拉普拉斯算子矩阵定义为

其他受欢迎的表示网络包括学位名单定义为 和度分布定义为

虽然有许多不同的熵的定义,在这个工作我们专注于信息科学中最常用的定义,香农熵(16]。这一措施表示所需的信息提供网络的统计描述。鉴于任何离散随机变量与可能的结果,香农熵的变量被定义为函数的概率所有的结果 :

根据所选的对数的底,熵是表示在比特( ),nats ( ),或说( )(也称为香农,和说也称为哈特利)。上面的定义适用于离散随机变量;对连续随机变量概率分布的微分熵,通常随着限制离散点的密度。给定一个变量与可能的离散结果,这样的限制 的密度方法的不变测度 ,连续熵给出了

在这项工作中,我们感兴趣的是测量各种网络不变量的熵。这些不变量可以被视为离散随机变量的数量可能的结果受可用字母的大小,或者二进制(邻接矩阵的情况下)或十进制(在其他不变量)。考虑第三图呈现在图1。这张图可以描述使用邻接矩阵如下:

反过来,这个矩阵可以被一个向量(一点也行操作或列),和这个向量可以被视为一个随机变量有两个可能的结果,0和1。这些结果数出现的次数,我们到达随机变量 和它的熵 。另外,这个图可以描述使用程度列表 可视为随机变量的熵 。另一个可能的随机变量,可以从这个图是程度分布 的熵 。总之,任何网络不变可以用来提取一个随机变量,计算其熵。

因此,在本文的其余部分,每当提及熵,我们将参考离散随机变量的熵。一般来说,随机性越高,熵就越大。熵的值是均匀分布的随机变量的最大和最小值随机变量的熵是获得一个常数。这种熵将在本文进一步探讨,以揭示其弱点。

香农熵作为替代,我们提倡使用Kolmogorov复杂度。我们推迟Kolmogorov复杂度的讨论部分3,我们提供它的定义和方法近似这数不清的措施。为了简便起见,在本文的其余部分中,我们将使用术语“熵”指的是香农熵和术语“复杂性”来指代Kolmogorov复杂度。

2.2。为什么熵是一个坏的网络复杂性

Zenil et al。24认为熵是不适当的测量真实网络的复杂性和他们的几个例子网络不应该成为复杂(使用术语的通俗理解),未达到最大熵的各种网络不变量。我们遵循的行论证Zenil et al .,我们现在更多的例子entropy-deceiving网络。我们的主要目的是显示它相对容易构造一个网络来实现各种网络熵值高的不变量。例子在这一节中概述的主要问题提出使用熵作为衡量复杂性的基础建设:即熵是不符合直觉的人类理解的复杂性。统计随机性,以熵来衡量,并不意味着复杂性有用,操作方式。

熵的主要原因和其他entropy-related信息理论措施无法正确描述网络的复杂性是这些措施并不独立于网络的表示。事实上,这句话同样适用于网络复杂性的所有可计算的措施。很容易呈现两个等效无损的例子描述相同的网络有非常不同的熵值,我们将展示部分2.3。在这篇文章中,我们实验的四种不同的表示网络:邻接矩阵,拉普拉斯算子矩阵,学位列表和度分布。我们展示的经验,选择一个特定的表示网络强烈影响产生的熵估计。

另一个属性使得熵衡量网络复杂性的问题是熵不能应用于一些网络特性同时,但它只作用于一个单一特征,例如,学位,中间性。在理论上,可以设计一个函数将一个个体组成特性,但高成分的复杂性并不意味着高复杂性的组件,反之亦然。这个需求选择一个特定的特性并计算其概率分布就排除了熵作为普遍的和独立的措施的复杂性。

此外,一个经常被遗忘的熵是衡量熵要求任意选择有关的聚合级别变量,计算熵。考虑到网络呈现在图2。乍一看,这似乎相当随机网络。网络的密度在邻接矩阵及其熵计算位。然而,这个网络已经使用一个非常简单的生成过程。我们首先初始矩阵:

接下来,我们创建这个矩阵的副本,这些副本是随机转置。最后,我们结合所有这些矩阵在一起形成一个方阵我们使用它创建网络的邻接矩阵。所以,如果我们要合并的邻接矩阵 邻接矩阵的块,熵是0,因为所有组成块都是一样的。这将意味着网络实际上是确定的,其复杂性是最小的。另一方面,应该注意的是,这个缺点的熵可以规避使用熵率(蟋蟀熵)相反,因为熵率计算所有可能的级别的粒度熵的一个变量。给定一个随机变量 ,让 表示的联合概率连续的值 。熵率一个序列的连续的值被定义为

熵的变量只是上面的估计的极限 。

2.3。Entropy-Deceiving网络

在本节中,我们提出四种不同的例子entropy-deceiving网络,类似于[创造的想法24]。这些网络有一个简单的生成过程和不应该(直觉)被视为复杂。然而,如果熵被用来构造一个复杂性度量,这些网络都是合格的复杂。在这一节中给出的示例无视任何特定的复杂性的定义;他们的目的是概述的主要缺点熵作为任何复杂性度量的基础建设。

2.3.1。度序列网络

度序列网络是一个网络的例子,一个有趣的属性:有两个顶点的度数为每个值 ; 。

程序生成序列网络是非常简单的。首先,我们创建一个链表顶点, 和 , , 。它是一个圆没有优势 。接下来,从顶点开始 ,我们遵循一个简单的规则:为 来 做为 来( )做 结束了结束了

由此产生的网络呈现在图3。很普通,顶点度的均匀分布,由于其简单的生成过程。然而,如果一个研究程度的熵序列,这将最大熵对于一个给定的数字的顶点,暗示更大的随机性的网络。这个例子表明,熵序列程度(和度分布的熵)是非常误导试图评估时的真实网络的复杂性。

2.3.2。Copeland-Erdos网络

Copeland-Erdos网络是一个网络似乎是完全随机的,尽管其生成的过程是确定的。Copeland-Erdos常数是一个常数,是由连接“0”的序列连续质数(25]。以10为底的质数表达时,Copeland-Erdos常数是一个正常的数量;数字的无穷序列,均匀分布(Copeland-Erdos常数的常态在基地以外的10不是证明)。这个事实让我们设计以下简单网络的生成过程。考虑到数量的顶点 ,在第一个数字Copeland-Erdos常数和代表他们的矩阵大小 。接下来,binarize使用函数矩阵中的每个值 (整数除法)并使用它创建一个网络的邻接矩阵。由于矩阵中的每个数字是大约同样有可能的是,由此产生的二进制矩阵将有大约相同数量的0和1。Copeland-Erdos网络的一个例子是显示在图4。邻接矩阵的熵是给定的最大顶点;此外,网络似乎是随机的和复杂的,但它的生成过程中,我们可以看到,非常简单。

2.3.3。2-Clique网络

2-Clique网络是一个人造的例子网络的邻接矩阵的熵最大。生成这个网络的过程如下。我们开始有两个连接顶点标记红色的和蓝色的。我们添加红色的和蓝色的顶点交替,每次连接新添加的顶点与所有其他顶点相同的颜色。因此,两个派系出现(见图5)。因为有那么多红色的顶点的有蓝色的顶点的邻接矩阵包含相同数量的0和1的(不考虑1代表派系之间的桥边缘)。所以,邻接矩阵接近最大熵,虽然网络的结构很简单。

2.3.4。大毒蛇网络

大毒蛇(大毒蛇是一种古老的蛇吃自己的尾巴的标志,第一个出现在埃及肖像然后获得恶名后来神奇的传统)网络的另一个例子是一个entropy-deceiving网络。程序生成这个网络很简单:对于一个给定的数字顶点,我们创建两个封闭环,每个组成的 顶点,我们连接对应顶点的两个戒指。最后,我们打破一个边缘在一个戒指,我们把一个顶点的破碎的边缘。这个过程的结果图中可以看到6。有趣的是,尽管几乎所有的顶点都在这个网络有同等程度的3中,每个顶点都有不同的中间状态。因此,中间状态序列的熵最大,表明一个非常复杂的模式通过网络沟通的途径。显然,这个网络是非常简单的从沟通的角度来看,不应认为是复杂的。

3所示。复杂性的度量网络的复杂性

我们坚信,Kolmogorov复杂度(复杂性)是一个更加可靠和健壮的基础构建复合对象的复杂性度量,如网络。虽然本质上数不清的,复杂性可以很容易地近似程度,允许的实际使用复杂性在真实的应用程序中,例如,在机器学习(26,27)、计算机网络管理(28),和一般计算理论(证明各种图灵机的下界,组合,正式的语言,和归纳推理)(29日]。

现在让我们介绍了正式的框架复杂性及其近似。注意,熵定义为任何随机变量,而复杂性仅为字符串的定义。复杂性一个字符串的正式定义为 在哪里程序产生的字符串吗当运行在通用图灵机和项目的长度吗 ,也就是说,所需的比特数来表示 。不幸的是,复杂性是不可数的30.),或者更准确地说,它是上层semicomputable(只有价值的上界复杂性可以计算给定字符串)。一个近似的真正价值是使用算法概率的概念引入Solomonoff和莱文31日,32]。算法的概率一个字符串的被定义为预期的概率随机程序运行在一个通用图灵机与二进制字母产生的字符串在停止:

当然有可能程序的长度 ,和求和在所有可能的执行计划不限制他们的长度,使得算法的概率一个semimeasure本身是不可数的。然而,算法可以用来计算概率复杂性使用编码定理[31日)即算法概率近似复杂到一个常数 :

编码定理的后果是它associates的频率出现的字符串以其复杂性。换句话说,如果一个特定的字符串可以由许多不同的程序,它被认为是“简单。“另一方面,如果一个非常具体的程序是需要产生给定字符串 ,这个字符串可以被视为“复杂。“编码定理也暗示复杂的字符串可以从其使用频率近似公式:

这个公式启发算法自然实验室集团(https://www.algorithmicnaturelab.org)发展中医(编码定理方法),一种近似方法小图灵机的复杂性通过计算输出频率。显然,算法概率的字符串无法准确计算,因为算法概率的公式需要找到所有可能产生的字符串的程序 。尽管如此,在有限的子集的图灵机可以计算机器生产的数量给定的字符串 ,这是中医背后的技巧。从广义上讲,中医的一个字符串由以下功能:计算 在哪里 所有通用图灵机的空间吗州和符号。函数 计算所有停止机器的比例州和符号产生的字符串及其价值的帮助下确定已知值著名的忙碌海狸函数(33]。算法自然实验室组织收集统计近500万短字符串(最大长度是12个字符)由图灵机与字母从2到9的象征,和根据这些统计数据中医可以近似算法的概率给定的字符串。中医的详细描述可以在找到34]。因为这个函数 是真正的近似算法的概率 ,它也可以用来近似复杂的字符串 。

中医可以仅适用于短12个字符组成的字符串或更少。对于较大的字符串和矩阵,应该使用BDM(块分解方法)。BDM需要字符串的分解(可能是重叠的)块 。给定一个长字符串 ,BDM计算其概率算法 在哪里是物体的算法复杂度和表示的次数出现在 。详细描述(BDM可以找到的35]。

显然,任何表示的一个非凡的网络需要远远超过12个字符。再次考虑第三图呈现在图1。这张图的拉普拉斯算子的矩阵表示如下:

如果我们把拉普拉斯算子矩阵的每一行作为一个单独的块,拉普拉斯算子矩阵的字符串表示 (为了简单起见,我们已经取代了象征“−1”象征“1”)。这个输入可以送入BDM,生产的最终估计算法(,因此,估计概率复杂性)字符串表示的拉普拉斯算子矩阵。在我们的实验中,当报告的值复杂的字符串 ,我们报告的价值的近似真实的复杂性。

4所示。实验

4.1。逐渐变化的网络

之前说,这项研究的目的不是为网络提出一种新的复杂性度量,但比较熵与的有效性和鲁棒性复杂性为复杂性作为底层基础措施。让我们回忆起什么属性预计从好和可靠的网络复杂性度量。首先,这项措施不应依赖于特定的网络表示但应该为所有可能产生或多或少地一致的结果无损表征的一个网络。其次,这项措施不应等同的复杂性和随机性。第三,这项措施应该考虑网络的拓扑属性,而不是仅限于简单的顶点和边的数量计算。当然,给定网络的统计特性不同网络之间不变量都有很大不同,但在基本水平的网络表示数量用于定义的复杂性测量应满足上述需求。主要的问题,我们的目标是回答在这个研究是熵和之间是否存在质的差异复杂性对上述要求在测量各种类型的网络。

为了回答这个问题,我们必须衡量底层网络结构的变化如何影响熵和的观测值复杂性。为此,我们设计了两个场景。在第一个场景中,网络逐渐从完美有序的状态转换到完全随机的状态。第二次转型带来完美有序的网络状态,状态可以理解为半有序,尽管方式不同。下面几节详细呈现两个场景。

以下4.4.1。从Watts-Strogatz小世界模型Erdos-Renyi随机网络模型

小世界网络模型引入了瓦和“36)是基于过程的,变换一个完全有序的网络没有随机重组成一个随机网络边缘。根据小世界模型,网络的顶点是放在一个常规维网格和每个顶点连接最近的邻国,生产常规的格子顶点的度相等。然后,有一个小概率的 ,每条边是随机重连。如果 ,没有发生重新布线,网络是完全有序的。所有顶点都有相同的程度上,同样的中间性,邻接矩阵的熵只取决于密度的边缘。当 这个过程,重新应用于边缘和边缘扭曲了顶点的度分布。

在网络另一端的频谱是Erdos-Renyi随机网络模型(37),之间没有固有的模式连接顶点。随机网络中通过选择所有可能对顶点和创造,每一对的边缘概率 。另外,一个可以生成所有可能的网络组成的顶点,这些网络的边缘,然后随机选择一个。随机网络的建设意味着最高程度的随机性,并没有其他的方式描述一个特定实例的网络除了通过显式地提供其邻接矩阵或拉普拉斯算子矩阵。

在我们的第一个实验中,我们观察熵和的行为复杂性逐渐被应用到网络的变化。我们开始与一个普通小世界网络生成的 。接下来,我们反复增加的价值通过在每一步,直到 。我们保留网络之间的迭代,从概念上来看,这是一个网络进行过渡。同时,我们只考虑重新布线的边缘没有被重塑了在前面的迭代,所以每条边是重塑了最多一次。为 ,网络形式规整的顶点,和 与所有边缘中枢网络是完全随机的。虽然随机重连边,我们不强加任何偏好选择目标顶点的边缘目前重塑;也就是说,每个顶点都有一个统一的概率被选中作为目标顶点重新布线。

4.1.2。从Watts-Strogatz小世界模型Barabasi-Albert优惠附件模型

另一个流行的模型的人工网络一代已经引入了巴斯和艾伯特(38]。这个网络模型是基于优惠附件的现象,根据顶点连续出现在网络和倾向于加入现有的顶点与强烈偏好高度的顶点。选择顶点的概率作为一个新创建的目标边缘成正比的程度 。无标度网络有许多有趣的属性39,40),但从我们的观点来看,无标度网络的最有趣的方面是他们代表一种特殊的半有序。低度顶点是混沌和随机的行为,和个人顶点很难区分,但高度顶点(所谓的结构中心)强加一个定义良好的拓扑网络。高度顶点作为桥梁,促进偏远地区的网络之间的通信,以及他们的学位都是可以预见的。换句话说,尽管绝大多数顶点随机行为,订单一旦出现高度顶点出现在网络。

在第二个实验中,我们从一个小世界网络重连概率增加优势在每一个步骤。然而这一次,我们不选择新的目标顶点随机,但我们使用附件优惠原则。早期的步骤,这一过程仍是随机的顶点度的差异相对较小,但在某种程度上出现的无尺度结构和越来越多的重新布线(发生 ),网络开始组织高度中心的一个子集。网络复杂性的直觉是,一个好的测量应该能够区分增加网络的随机的初始阶段和第二阶段出现半有序。

4.2。结果与讨论

我们实验只在人工生成的网络,使用三种流行的网络模型:Erdos-Renyi随机网络模型,Watts-Strogatz小世界网络模型,Barabasi-Albert无标度网络模型。我们从考虑故意遗漏了经验网络,由于可能的偏见可能会被引入。经验网络,不幸的是,我们没有一个好的方法近似算法的概率的一个网络。我们能做的就是比较经验分布的网络属性(如度、介数、本地集群系数)与已知分布生成模型。在我们以前的工作(41),我们已经表明,这种方法可以导致严重的近似误差的分布网络性能强烈依赖于模型参数的值(如边重连概率在小世界模型中,或无标度模型中的幂律系数)。没有一个通用的方法估计的算法概率经验网络,熵和比较是没有意义的因为没有复杂的网络可以建立基线,结果不会产生自己的解释。

在我们的实验中我们使用了acssR包(42)实现了编码定理方法(34,43)和块分解方法(35]。

让我们现在第一个实验的结果。在这个实验中,边缘重连概率改变从来通过在每个迭代中。在每个迭代中,我们产生的实例网络组成的 顶点,并为每个生成的网络实例,计算以下措施:(我)熵和邻接矩阵的复杂性(2)熵和拉普拉斯算子矩阵的复杂性(3)熵和复杂性程度的列表(iv)熵和度分布的复杂性

我们重复实验中所描述的部分4.1为每个50网络,执行这些网络的逐渐变化,和每个值的边重连概率我们在所有50个网络平均结果。由于熵和复杂性表达在不同的单位,我们正常化措施允许并排比较。标准化过程如下。对于一个给定的字符串的字符的长度 ,我们生成两个字符串。第一个字符串由重复0,它代表了最复杂的字符串的长度 。第二个字符串是一个串联的一致选定的数字,它代表了最复杂的字符串长度 。每个值熵和复杂性是规范化对熵和最小和最大的价值复杂性可能相等长度的字符串。这不仅可以让我们比较熵和复杂网络的不同表示,但也比较熵直接的复杂性。我们的实验结果呈现在图7。

我们观察到传统的熵的邻接矩阵保持不变。这是显而易见的,边的重新布线不改变网络的密度(边的数量在原来的小世界网络和最后一个随机网络和无标度网络是完全相同的),所以熵的邻接矩阵的每个值都是一样的重连概率 。另一方面,邻接矩阵的复杂性逐渐增加。应该注意的是,的变化分析了绝对值时复杂度很小。尽管如此,复杂性不断增加,网络偏离的顺序对随机网络模型的混沌小世界模型。一个非常相似的结果可以观察到网络使用拉普拉斯算子的矩阵来表示。再次,熵未能信号任何网络复杂性的变化,因为网络的密度保持不变在整个过渡,和熵的非常细微的变化 是由于程度的变化列表形式拉普拉斯算子矩阵的主对角线。度的结果列表更令人惊讶。复杂性程度列表稍微增加的网络失去订单,但仍接近 。同时,重连概率熵增加速度优势方法 。熵增长非常相似的模式过渡到随机网络和过渡到无标度网络,后者相反特征的更大的熵。此外,熵的绝对值程度列表是几倍剩余网络表征(邻接矩阵和拉普拉斯算子矩阵)。最后,熵和复杂性表现同样的网络使用程度分布描述。我们注意到两个措施正确识别明显的减少复杂性作为方法的无标度网络模型(半有序出现时)和信号越来越复杂,网络变得越来越随机的。人们很容易从最后一个实验的结果得出分布程度当网络复杂性而言是最好的代表。然而,人们不应该忘记,程度分布和程度并不无损表征网络列表,所以只程度分布估计的算法复杂度是多么困难重新分配,而不是整个网络。

考虑到需求制定本节开始时和实验评估的结果,我们得出结论复杂性是一个更可行的措施构建直观的复杂性定义。复杂性捕捉发展网络拓扑变化小,熵无法检测这些变化是因为网络密度保持不变。同时,复杂性产生更少的绝对差异值在不同的网络表示,和熵的回报取决于特定的网络表示截然不同的估计。

5。结论

熵是常用的作为建模的基础网络的复杂性。在本文中,我们说明了为什么熵是一个错误的选择测量网络的复杂性。熵相当于随机性和复杂性要求预选感兴趣的网络特性。我们已经表明,它相对容易构造一个简单的网络,最大化熵的邻接矩阵,度序列,或中间性分布。另一方面,复杂性的长度相当于复杂性的计算描述网络。这种方法很难欺骗,它提供了一个更加健壮和可靠的描述网络。当网络逐步改变高度有序的高度无序状态,复杂性捕捉这种转变,至少对邻接矩阵和拉普拉斯算子矩阵。

在本文中,我们使用传统的方法来描述一个网络:邻接矩阵,拉普拉斯算子矩阵,程度列表和度分布。我们实验的范围有限三个最受欢迎的生成网络模型:随机网络、小世界网络和无标度网络。然而,它是可能的描述网络更简洁,使用通用网络发电机。在不久的将来,我们计划提供一个新方法的计算算法的复杂性网络无需估计复杂性,而是遵循最小描述长度原则。同时,扩展实验经验的领域网络可能被证明是有用的和有趣的。我们还打算调查网络表示基于各种能量(Randić能源、拉普拉斯算子的能量,和邻接矩阵能量)和网络能量和研究之间的关系复杂性。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者要感谢Adrian Szymczak帮助设计序列网络程度。这项工作是由美国国家科学中心、波兰,决定nos, DEC-2016/23 / B / ST6/03962 DEC-2016/21 / B / ST6/01463,和DEC-2016/21 / D / ST6/02948;欧盟的地平线2020研究和创新项目根据玛丽Skłodowska-Curie赠款协议。691152(雷诺);和波兰科学和高等教育基金支持国际共同投资项目在2016 - 2019年(协议号3628 / H2020/2016/2)。