复杂网络中信息高尺度的出现

摘要

一个网络的连接包含关于节点之间的关系，它可以表示相互作用，协会，或依赖关系的信息。我们表明，这种信息可以通过测量包含在沿着网络中的节点和链路路径的不确定性（和确定性）进行分析。具体来说，我们从一个度量称为第一原理得出有效信息并在常见网络模型中描述其行为。具有更高有效信息的网络在节点之间的关系中包含更多信息。我们展示了如何将节点的子图分组为宏节点，从而在增加有效信息的同时减小网络的大小（这种现象称为因果涌现）.我们发现，信息性更高的尺度在生物、社会、信息和技术领域的模拟和真实网络中很常见。这些结果表明，网络中更高尺度的出现是可以直接评估的，这些更高尺度提供了一种从不确定性中创造确定性的方法。

1.介绍

网络提供了一种强大的语法来表示广泛的系统，从简单的系统到高度复杂的系统[1-3.］.根据网络的度分布或聚类等结构属性来表征网络是一种很常见的现象，对这些结构属性的研究对网络科学的发展至关重要。然而，我们在处理网络中节点之间的关系所包含的信息方面仍然存在差距，特别是在既有加权连接又有反馈的网络中，这是复杂系统的特征[4.那5.].正如我们将要展示的，分析这些信息可以在最合适、信息量最大的范围内对网络进行建模。这对于描述节点间相互作用或依赖关系的网络尤其重要，例如流行病学中的接触网络[6.，大脑中的神经元和功能网络[7.或细胞，基因或药物之间的相互作用网络[8.，因为这些网络通常可以在多个不同的尺度上进行分析。

在这里，我们介绍了信息理论度量，捕捉包含在网络连通性中的信息，可以用来识别这些网络何时拥有信息的更高尺度。为此，我们关注权重外向量， 那每个节点, 那在一个网络。这个向量由权值组成之间的和它的邻居, 那和如果没有从边缘到 ．为每一个我们猜测 那意思是可以解释为概率那个随机的沃克将转变为在下一个时间步中，一个随机的步行者可能表示一个信号的传递、一个交互或一个状态转移[9.］.网络连通性所包含的信息可以通过其节点的外权值和内权值之间的不确定性来表征。节点之间关系的总信息是这种不确定性的函数，可以从两个属性中得到。

第一个是节点输出的不确定性，即香农熵[10]在它的重量之外， ．熵的平均值， 那只有在以下情况下，网络关系中存在的噪声量才会跨越所有节点是网络确定的．

第二个特性是权重是如何在整个网络中分配的， ．这个向量由元素组成，这些元素是权重的和对每个节点从每个来邻居，(然后按网络的总权值归一化)。它的熵, 那反映确定性是如何分布在网络上的。如果所有节点只连接到同一个节点，则 那网络完全是简并因为所有的节点导致同一节点。

这有效信息 就是这两个量的差:

网络中权值分布的熵构成了网络关系中唯一信息量的上界，该上界减去了由于这些关系的不确定性而丢失的信息量。网络高在网络中节点之间的关系中包含更确定的（因为链接代表不确定的依赖性，唯一关联或确定性转换），而具有低的网络包含不太确定性。注意可以简单地解释为网络上随机步行者的结构性及其行为，类似于其他常见的网络措施[9.］.

在这里，我们使用这一指标来制定网络的一般分类（关键术语可在补充材料SM V中找到） A） 此外，我们还展示了网络的连通性和不同的增长规则如何与该网络的 ．这也提供了一种有原则的方法来量化网络中微观、中观和宏观依赖关系之间的信息量。我们介绍了一种寻找和评估网络中信息量最大的尺度的形式主义:最小化节点之间关系的不确定性的尺度。对于某些网络，以这种方式对网络的宏观描述可以提供更多的信息，展示一种称为因果涌现[11那12]，这里我们概括了复杂的网络。这提供了一种严格的手段，即识别网络何时具有信息丰富的更高规模。

2.结果

2．1.有效信息量化网络的依赖关系

这项工作扩展了网络之前的研究，即使用有效信息来衡量系统机制或状态之间的因果关系中的信息量。最初,被引入捕获神经元两亚子集之间的因果影响，作为大脑中综合信息计算的步骤[13］.后来，一个系统范围的版本显示出捕获的逻辑门的布尔网络基本因果性质，特别是它们的确定性和简并[11］.

我们当前的推导来自对于网络来说相当于这个系统范围的定义(SM V B)，它最初是基于对系统状态的干预。例如，如果一个系统处于特定的状态，一种，始终过渡到州B.之间的因果关系一种和B.可以用节点-连接图表示，其中两个节点-一种和B.-通过定向箭头连接，表示B.取决于一种．这可能是“因果关系图”中的节点对(通常表示为有向无环图，或DAG)如用于[14那15]代表的干预和因果关系。在这样的情况下，在之间的因果关系的信息一种和B.可以通过干预进行随机评估吗一种 并测量其影响B.．这是相互的信息吗一种和B.在这种随机化: [16］.

为了将这个框架扩展到一般的网络，我们放宽了干预要求，假设其中的元素总和为1.在这种情况下，可以将“干预”解释为丢弃网络上的随机步行者。例如，如果网络代表DAG或Markov链，则在节点上丢弃随机助行器就等于 ．随机游走者的跃迁熵以及这些跃迁的分布方式定义了网络的一部分。在这个广义公式中，只有在节点和边实际表示动力学、相互作用或耦合的网络中，才会这样做表示有关因果关系的信息。在边缘表示相关性的情况下，或者在未定义的节点或边缘表示的情况下，仅仅是包含在假设随机步行者行为中的信息的结构属性(然而，这种情况与其他依赖随机步行者的分析方法没有什么不同)。

在这里，我们将描述这种广义结构属性在普通网络模型中的行为，询问关于网络之间关系的基本问题这些查询允许对真实网络连接中包含的信息进行详尽的分类和量化随着网络规模的增长，网络的可用性将增加。一般来说，增加更多的节点会增加熵，而熵又会增加信息量。但是，在随机性而非结构的情况下，应该反映出这种随机性。我们发现情况确实如此。

数字1（a）表示网络之间的关系及其在Erdős-Rényi (ER)随机图若干参数化下的大小[17那18］.随着ER网络的大小增加（同时保持持续的概率，任何两个节点都将连接， ），它的收敛于的值 ．也就是说，在随机网络中，这一关键发现表明，在某一点之后，随机网络结构并不会随着其规模的增大而包含更多的信息。这种转移大约发生在ER网络中 那这也是我们可以预期的所有节点在一个巨大的组件[1］.这一发现说明，网络连接必须是非随机的，以增加节点之间的关系中的信息量(参见SM V c1的推导)。请注意，如果一个网络是最密集的(即，一个完全连接的网络，带有自环)， ．但是，我们预计这种密集的低这种结构并不常见，因为在自然界和社会中发现的网络结构往往是稀疏的[19］.

我们报告了网络的连通性和它之间的另一个关键关系在图中1（b）．我们再次比较将网络到其大小，专注于在优先附加模型的不同参数下生长的网络[20.那21］.在优先attachment growth模型中，每个时间步长都会有一个新的节点加入到网络中网络的新边缘;这些边连接到网络中已经存在的节点， 那的概率正比于 ．在这里,是节点的度数和调谐优先连接的量。价值对应于具有接收新的节点的链路（即，没有优先连接）的机会相等的每个节点。经典Barabási阿尔伯特网络对应于线性优先连接，[21］.在字行上面的优惠附件, 那创建的网络具有越来越少的 那最终类似于星状结构(参见SM V c2的推导)。如图所示1（b），仅在次线性优先依恋的情况下， 那网络是吗？随着它的规模继续增长。当-创建一个随机树，使网络的随着其大小的增加而对数增加。

最大可能在一个网络中节点 ．这可以在每个节点具有一个传入链路和一个输出链路的定向环网的情况下看出，每个节点的重量为1.0，因此每个节点都有一个唯一连接到它的节点。在这样的网络中，每个节点都会有助于零不确定性 那和 那因此，它总是 ．一般来说,环晶格的大小和维数(即，为无向环，是金牛座等[22)，对于这样的格也是如此（见SM V） C 2表示推导）。

由此得出的结论是与网络的连接性和增长（甚至是网络图案，如SM V D所示）无密不可分地与网络科学的基础知识相关联。随机网络具有固定数量的 那和scale-freeness 表示的增长的临界边界 ．一般来说，密集网络和星形网络具有较少的可用性 ．下一节探讨如何做到这一点这些组件解释了这些关联。

2.2.决定论和简并

决定论和简并这两个基本组成部分是[11］.它们基于网络的连接（见图2(一个)对于视觉解释），特别是网络中重叠权重的程度。确定性和简并性分别来自输出的不确定性和这些输出如何分布的不确定性：

在所有节点只有一个输出的最大确定性网络中， 那决定论是因为 ．从概念上讲，这意味着随机行走者将从任何节点开始决定性地移动。简并度是指通过输入权重重叠而丢失的连接中的信息量（例如，如果多个节点输出到同一节点）.在一个完全非退化系统中，所有节点具有相等的输入权重，简并度为零，因为 ．同时，决定论和简并可以用来定义 ：

这两个量清楚地解释了为什么不同的网络具有他们是这样。例如，作为一个ERDOS-莱利随机网络的大小增加时，其简并趋近于零，这意味着随机网络仅被网络的确定性驱动，这反过来反过来的连接概率，P.．同样,在D.- 扭曲环形格子网络，退化项总是零，这意味着环形格子结构也降低了该结构的确定性。环网具有平均度将有更高的比具有相同平均程度的网络，因为环网将具有更高的确定性值。在明星网络的情况下，单独的退化术语管理衰减such that hub-and-spoke-like structures quickly become uninformative in terms of cause and effect (see SM V C for derivations concerning these cases). In general, this means that canonical networks can be characterized by their ratio of determinism to degeneracy (see Figure2 (b)）.

２.３.真实网络中的有效信息

到目前为止，我们对正在分析的网络的起源是不可知的对于一个网络，可以创建每个通过将每个节点的超权向量归一化，使其和为1.0。无论节点之间的关系代表什么，网络的确定性反映了节点的超权值有多有针对性(具有更多针对性链接的网络具有更高的权重 ），而简并度则捕捉节点目标的重叠。高反映了连通性的更大特异性，而表示缺乏特异性(如图所示)2(一个)）.这将我们的结果推广到多种类型的陈述，尽管在解释测量值的值时应牢记归一化网络的起源。

自网络将根据网络尺寸而变化，我们使用规范化形式作为。。而被知道有效性为了比较真正的网络。有效性范围从0.0到1.0，定义为

随着网络的确定性和退化性分别增加到其最小值和最大可能值，该网络的有效性将趋向于0.0。无论其大小，一个网络，其中每个节点具有确定性输出到唯一目标的有效性为1.0。

在图3.，我们检验了84个不同网络的有效性，对应的数据来自真实系统。这些网络主要是从Konect网络数据库中选择的[23]，这是使用，因为它的网络是公开的，尺寸范围从几十到数以万计的节点，往往有一个合理的解释为是基于节点之间的相互作用，以及他们是多种多样的，从社交网络，电力网络，代谢网络。我们定义了四个类别的兴趣：生物，社会，信息和技术。我们通过使用所有可用的网络选择我们的网络（40个000由于计算约束节点）对应于Konect数据库中每个类别域，它是适当的，该网络库以及[24］.见材料和方法部分和SM表二,查阅此选择过程的完整描述。

较低的有效性值对应于具有高简并度的结构(如图右柱所示)2(一个)）或低确定性（如在左侧列中，图2(一个))或两者的结合。在我们测量的网络中，生物网络的平均有效性值较低，而技术网络的平均有效性最高。这一发现与我们所知道的两者之间的关系直觉上一致它还支持关于冗余、简并和噪声在生物系统中的作用的长期假设[25那26］.另一方面，电网、自主系统或航空网络等技术网络的平均效率更高。对这种差异的一种解释是，在人工技术网络中，效率倾向于创建更稀疏的、非退化的网络，平均效率更高，其中的节点关系在目标上更具体。

也许发现进化的网络有这种效率可能是令人惊讶的。但是，正如我们将显示的那样，低效实际上可以表明系统中存在信息丰富的更高尺度（Macroscale）连接。也就是说，低有效性可以反映生物系统通常含有更高尺度结构的事实，我们在以下部分中显示。

２.４.复杂网络中的因果涌现

这个新的全球网络测量， 那提供了一个原则性的方法来回答一个重要的问题:什么规模能最好地捕捉一个复杂系统的连通性?这个问题的解决是重要的，因为科学在不同的时空尺度上分析不同系统的结构，往往倾向于在远高于微尺度的水平上干预和观察系统[12］.这可能是因为在微观尺度上的关系可能非常嘈杂，因此没有信息，而粗粒度可以将这种噪音最小化[11]事实上，这种噪声最小化实际上是基于克劳德·香农的噪声信道编码定理[10]，其中尺寸减少可以像使用更多频道容量的代码一样操作[16］.更高级别的因果关系通常对较低级别的关系进行纠错，从而在那些更高的尺度上产生额外的有效信息。测量这种差异提供了定义的方法，当更高的尺度更具信息性（出苗）或更高的尺度是外来的，癫痫症或损失（减少）时的较高尺度。

把这些问题给网络科学，我们现在可以问，什么表示将最大限度地减少网络中存在的不确定性？我们通过检查做到这一点因果涌现，即当一个维度减少的网络包含更多的信息连接，以更高的形式比原来的网络。需要注意的是，所讨论的，可以单独解释为网络的一般结构属性。因此，虽然我们仍然称这种现象为“因果涌现”，因为它具有与先前布尔网络和马尔可夫链相同的数学形式化[11那12那16]，在这里，我们专注于如何将它用于识别网络的信息更高的尺度，无论什么样的网络代表。

值得注意的是，这种现象可以通过在更高的尺度上重铸网络和观察变化，识别网络的高尺度是否在低尺度之上添加信息的过程。

2.5。网络宏观

首先，我们必须介绍如何重铸网络， 那以更高的规模。这由新网络表示， ．之内 那微节点是原始文件中存在的一个节点 那宏节点被定义为节点， 那这代表了一个子图， 那原著(替换网络内的子图)。由于原始网络通过将节点分组而降维，永远有比较少的节点 ．

乘客码头被定义为 那由它所表示的子图中各节点的边权值导出。可以将宏节点看作是底层子图行为的汇总统计，这种统计采用单个节点的形式。最终，有许多表示子图的方法，也就是构建宏节点，并且根据连接性，有些方法在捕获子图的行为方面比其他方法更一致。这里我们要强调的是，总体而言，网络的宏观尺度应该是持续的与它们的动力学的微观尺度有关。虽然这从来没有在网络或系统内进行评估，但以前的研究已经提出，结构方程模型的宏观尺度是否与所有可能的干预措施的效果相一致[27］.

在这里，为了决定宏节点是否是其底层子图的一致总结，我们将一致性形式化，作为随机步行者是否在上相同行为的度量和 ．我们这样做是因为随机散步通常用于表示网络上的动态[9.]，因此，许多重要的分析和算法，如用于确定节点中心性的PageRank [28或社区发现的Infomap [29]-是基于随机游动的。

具体来说，我们定义不一致在宏观尺度上的差异[30.]随机行走的上期望分布之间vs。 那给定每个一些相同的初始分布。超预期的分布在未来某个时间， 那是 那而分布在未来的时间是 ．为了比较两者，分布在Macroscale中的相同节点上求和 那导致了分布（给定宏观尺度的微观尺度）。然后我们可以定义一系列时间步长上的宏观尺度不一致性作为

这种一致性度量的地址，其在微观拓扑的随机动力过程将在尺寸上缩小的拓扑中重现的程度（对于如何在我们的分析应用，见材料和方法）。

构成一致的Macroscale取决于将子图的连接分组到Macronode中，如图所示4.．这可以在集体的基础上构建吗子图（如图所示）的4(一)）.例如，在某些情况下，可以通过使用平均值来粗粒度化子图随着一些新的Macronode（如图所示）4 (b)）.然而，可能子图具有这种粗粒度无法捕获的依赖性。事实上，这类似于最近的发现，当从数据构建网络时，通常需要使用高阶节点明确地建模高阶依赖，以便随机游走的动态保持对原始数据的真实[31］.因此，我们介绍高阶Macronodes（HOMS），其借鉴类似的技术，以一致地代表子图作为单个节点[31］.

不同的子图连接需要不同类型的HOMs来一致地表示它们。例如，HOMs可以基于宏节点的输入权值，它采用如下形式 ．在这些情况下,是每个节点的加权平均值吗，其中的权值基于子图中每个节点的输入权值(图4 (c)）.随着时间的推移，另一种HOM通常会导致一致的宏节点是什么时候基于从子图到网络其余部分的平稳输出，我们表示为（数字4 (d)）.考虑到一些初始状态，这些类型的HOM可能会有轻微的不一致性，但随着网络接近其静止动力学（概述4.）.

具有复杂内部动态的子图可能需要更复杂的HOM类型，以保持宏节点的一致性。例如，在子图的输入和输出之间有延迟的情况下，可以用组合表示和 那当合并时捕获了延迟(图4 (e))。在这些情况下，宏节点有两个组件，其中一个组件在时间步骤中充当缓冲区。这意味着即使在从微观记忆的网络构建的网络中构造的MACRONEODE也可以具有存储器，实际上，有时需要这种类型的HOM以一致地捕获微观动态。

我们介绍这些类型的MACRONODE不是作为所有可能的HOM的详尽列表，而是通过将子图表示为节点，并且有时使用更高阶依赖项来确保这些节点的概要如何构建网络中的更高尺度的示例。这种方法提供了以前的粗粒程的完全概括[11]以及黑盒子[16那32那33，同时利用高阶依赖关系解决之前未解决的宏观尺度一致性问题。由子图组成的宏节点类型还提供了关于网络的实质性信息，比如网络的宏规模是否拥有内存或路径依赖。

2.6。因果涌现揭示了网络的规模

当重铸网时，网络具有信息丰富的Macroscale，（宏观尺度），具有更比原来的网络,，一般来说，网络的有效性较低（低考虑到它们的规模)有更高的可能性出现这种情况，因为它们可以被重新塑造，以减少它们的不确定性。跨组搜索允许识别或近似的宏规模，最大限度地 ．

除了最小的网络外，检查所有可能的分组在计算上都是很困难的。因此，为了找到增加 那我们使用贪婪算法将节点组合在一起并检查是否存在增加。通过选择一个节点，然后迭代地将其与其周围的节点配对，我们可以增长宏节点，直到配对不再增加 那然后继续前进到新节点（有关此算法的详细信息，请参阅“材料和方法”部分）。

通过生成无向的优先附加网络并改变优先附件的程度， 那我们观察到优先依恋和因果出现之间的关键关系。网络科学的核心成果之一是确定了“无标度”网络[21］.我们的结果表明，网络不是“无尺度的”，可以进一步分为微观，中观和宏观尺度，这取决于它们的连通性。这个量表可以根据它们的因果出现程度来确定(图)5(一个)）.在次线性偏好连接的情况下 那网络缺乏更高的尺度。线性优惠附件 产生无标度的网络，即在网络发展到更高规模之前优先依附的区域。这种更高的尺度只存在于超线性优先依恋的情况下 ．和过去网络开始收敛到一个宏观尺度，几乎所有的节点都被分组到一个宏观节点中。最大数量的因果出现出现在中尺度网络中，即在1.5到3.0之间，此时网络拥有丰富的宏节点数组。请注意下面的宏规模分组如图所示5(一个)类似于更高我们在图中观察到1（b）．这是因为之后的减少微尺度技术的发展为其性能的提高留下了空间在宏观尺度上，跟随一组节点。

相应的大小为降低增加，网络发展为信息的更高尺度，这可以从宏观尺度网络规模的比例中看出， 那到原来的网络规模，（数字5 (b)）.如前所述，以更高的值生成的网络会变得越来越像恒星类星型网络具有较高的简并度，因此简并度较小 那正因为如此，我们期望有更多的机会来增加网络通过将节点分组为宏节点。事实上，恒星网络的理想分组是在和少量。该结果类似于在最新进展光谱粗粒化也观察到理想的粗粒化的星形网络的是将其折叠成一个双节点网络，分组的所有辐条成单个macronode [34，这就是明星网络被重塑为宏观规模的原因。

我们的结果通过询问用单个节点替换子图是否有信息增益，为此类社区检测提供了一种原则性和通用的方法因果社区当一簇节点或一些子图形成一个可行的宏节点时(注意，这假设网络中的连接实际上代表了可能的因果交互，但它也仅仅是一个拓扑属性)。从根本上说，因果共同体在微观尺度上代表噪音。子图离完全噪声越近，其增益就越大用宏电极代替它(见SM V G)。在给定的网络中，使噪声最小化也能识别出代表该网络的最佳尺度。然而，首先必须有一些结构可以通过噪声最小化来揭示出来。在随机网络的情况下，形成一个单一的大组成部分，缺乏任何这样的结构，因果出现不会发生(如SM V G所示)。

2.7。真实网络中的因果涌现

根据连接，宏观的存在和信息性应在真实网络上各不相同。在这里，我们调查对不同领域的真实网络的因果出现的性格。我们从图中分析的相同网络集中绘制3.，选择过程和细节在材料和方法部分有概述。网络的规模可达40000个节点，因此无法为每个节点找到最佳的宏观尺度。因此，我们特别关注两个类别，这两个类别之前显示出最大的分歧 ：生物技术。由于我们对生物或技术网络是否表现出更大的因果涌现倾向这一普遍问题感兴趣，我们通过计算不断增长的抽样子图的因果涌现来近似因果涌现。每个样本使用“滚雪球抽样”程序找到，其中随机选择一个节点，然后在其周围找到一个指定大小的弱连接子图[35］.然后使用先前描述的贪婪算法方法分析该子图来查找最大化的MACRONODE在每个网络中。每个可用网络针对从中获取的每个大小进行20次采样。如图所示6.，我们展示了这些真实网络的因果出现如何在每个样本的50,100,150序列中增加采样的子图尺寸，并且在50,100,150，最后200个节点中增加。这些大小的网络以前为模拟网络中的因果出现提供了充分的证据，如图所示5(一个)．比较两类真实网络，我们观察到生物网络中的因果局部出现明显更大的倾向，而这更为明显阐述样品越大。注意，构建这些网络的随机空模型（例如，配置模型）将倾向于创建具有最小或可忽略的因果突出网络的网络，而ER网络的情况（图13在sm v g）中。

生物系统的子集显示出对因果的高度倾向，甚至解释性，许多长期假设围绕生物系统中的噪声和退化性的存在[36］.它还解释了解生物系统功能的因果结构的难度，因为它们是在一个水平和另一个级别的不确定性的神秘之中。

3.讨论

我们已经表明，网络中节点之间关系中的信息是其连接性固有的不确定性的函数，以及这种不确定性是如何分布的。为了获取这些信息，我们采用了一种衡量方法，即有效信息 那用于网络，并分析了网络科学家研究了几十年的常见网络结构一个随机网络倾向于 那和是否由于添加新节点是其优先附件的程度，因此优惠附件网络的增长或收缩 那大于或小于1.0。在机制或转换未知但结构已知的网络中，捕获网络中独特目标的程度。在真实的网络中，我们证明生物网络往往远低于技术网络。

我们还说明了所谓的“因果出现”可以发生在网络中，这就是当一个网络， 那被重新打造成一个新的网络， ．找到这种信息丰富的高尺度意味着平衡不确定性的最小化，同时最大限度地增加网络中的节点数量。这些方法可能有助于改进科学实验设计、大数据的压缩和搜索、模型选择，甚至机器学习。重要的是，不是每个重播网络， 那将有更高的比它代表，也就是说，这些相同的技术可以识别减少的情况为比较同一复杂系统的任意两种网络表示的有效性提供了依据。这些技术允许正式确定网络的规模。无标度网络可被认为具有分形的连通性[37),我们的结果表明,网络的规模的断裂分形在一个方向或另一个注意,未来的研究领域是如何有效地识别这些信息更高的尺度,以及如何网络属性以外的EI跨尺度变化(38］.

网络中高阶结构的研究是一个日益丰富的研究领域[29那39-42]，通常专注于构建能够更好地捕获它们所代表的数据的网络。在这里，我们介绍了一种形式化和广义的方法，在保持随机游动动力学的同时，在更高的尺度上重铸网络。在许多情况下，网络的宏观尺度在随机游动动力学方面可以是一致的，并且具有更大的稳定性 ．宏尺度中的某些宏节点可能是具有不同高阶属性的不同类型。换句话说，我们展示了如何将低阶网络转化为高阶网络。我们工作中一个值得注意和相关的方面是演示一个在微观尺度上无记忆的系统如何在宏观尺度上实际拥有内存，这表明一个系统是否拥有内存是尺度的函数。

虽然有些[43]以前我们曾将子图作为单独的节点进行过重铸，但它们并没有以基于噪声最小化和一致性最大化的方式进行重铸，而是通过压缩来提高算法速度。显式地创建宏节点以最小化噪声，从而突出了网络的依赖性。这意味着网络中的因果出现与社区检测有直接关系，社区检测是一门庞大的分支学科，它将网络中的密集子图视为表示共享属性、成员或功能[44那45］.然而，因果出现和传统社区发现之间的关系并不像它看起来那样直接。首先，在具有高退化度的网络(即具有高度枢纽的网络，如图所示)中，因果出现率较高5(一个)）.社区检测算法通常不选择这样的结构属性，而是专注于密集的子图，这些子图内部的连接比外部的连接更紧密[44］.在SM图12，我们将展示随机块模型网络及其相关的因果出现值的一道风景线。事实上，在网络中，将有高度模块化[46)，我们确实观察到因果出现，但只有当这两个不相关的派系是不同尺寸．这种区别是关键的，并且情况在复杂网络研究中显示出有意义的地方的因果的网络。鉴于此，Macronodes提供了一种社区检测，其中构成Macronode的微孔码是社区，最终可以由乘法器替换，总结其行为，同时降低子图的噪声。在这种解释下，社区结构的特点是噪声而非共享成员资格。

4.材料和方法

4.1。选择真实网络

网络被选择来代表四类兴趣:社会、信息、生物和技术(见SM图)10，其中我们详细描述了与图中相同的信息3.，除了每个网络的有效性值外，还包括网络数据的来源)。我们使用了反映我们兴趣类别的Konect数据库中所有域的40000个节点(由于计算限制)下的所有可用网络。对于我们的社会类别，我们使用域人的联系人那人类社会那社会的,沟通．对于我们的信息类别，我们使用了域名引用那共同创作那超链接那词汇,软件．对于我们的生物类别，我们使用了域名营养和新陈代谢．由于Konect数据库和网络存储库之间的重叠[24在这些领域，以及在Konect数据库中其他生物数据的缺乏，我们也纳入了大脑域和生态来自网络存储库的域以增加我们的示例大小（再次，包括在40,000个节点下的这些域内的所有网络）。对于我们的技术类别，我们使用了域名计算机和基础设施由于Konect数据库和网络存储库之间的重叠，我们还包括技术和电力网络来自网络存储库的域。对于本研究中使用的网络的完整表以及他们的来源和分类，请参阅表二,．

4.2。创建一致的Macronodes.

以前我们概述了创建不同类型的一致Macronodes的方法。在这里，我们探讨了他们的实现，这需要决定宏观呈哪一致。在Microscale上的随机步行者的预期分布之间测量不一致的kullback-leibler差异宏观尺度 那给定初始分布，如方程中所示(5.）.

为了测量的不一致性，我们使用的初始最大熵分布之间的共享节点上和 那也就是说，只有未分组的节点集 ．同样，我们只分析相同的一组微光码上的预期分布。由于这种分布仅在网络的一部分上，因此将每个分发标准化为1.0，因此我们包括单个概率，该概率表示在其中的所有非线性节点和（代表随机助行器在Macronode上）。

我们关注的是两者之间的共享节点和对于不一致性度量，因为(a)在算法搜索过程中，很容易计算出哪些是必须的;(b)除了异常情况外，共享节点上的不一致性仍然反映了整个网络;(c)即使在最极端的宏观尺度(例如在图中5.），仍有节点之间共享和 ．

在这里，我们检查我们使用更高阶依赖性的方法，以便演示这将创建一致的MACRONODE。我们使用1000个模拟优先附着网络，作为参数之间的均匀随机样品选择和2.0,到35岁，而且或2。然后，通过下一节中描述的算法对这些网络进行分组。所有宏节点都是相同的类型，并在1000个时间步骤中检查它们的不一致性。这些宏节点通常具有一致的动态，要么因为它们以这种方式开始，要么因为它们随着时间的推移趋于这种方式，在1000个网络中，只有4个网络在1000个时间步后的发散大于0。在图11在SM V F中，我们展示了15个这样的模拟网络，以及它们的参数、宏节点数目和一致性。请注意，即使在早期非零不一致的情况下，这总是非常低的绝对位，而随机选择的15位，没有一个随着时间的推移不趋向于一致性。在我们的观察中，大多数宏节点收敛于500个时间步之前，所以在使用宏节点，我们检查所有宏节点的一致性，只拒绝那些在500步时间内不一致的宏节点。关于找出因果出现的算法方法的更多细节可以在下一节中找到。

4．3．因果涌现的贪婪算法

用于查找网络中因果出现的贪婪算法的结构如下：对于每个节点， 那在原始网络的洗牌节点列表中，收集相邻节点列表， 那在哪里是马尔科夫毯的（在图形模型，马尔可夫毯， 那一个节点, 那对应于的“父母”、“孩子”和“孩子的父母”[47]）。这意味着由结点组成，结点的出边通向 那传出边缘的节点引入，以及具有引出边的节点引入的外部邻居 ．中的每个节点 那该算法计算从宏观的网络后，和组合成一个宏节点， 那根据图中的千克富码类型之一4.．如果得到的网络具有更高的值，算法存储此结构的变化，如有必要，请补充节点的队列， 那任何新的邻居节点马可夫毛毯还没有装进去 ．如果一个节点， 那已经通过与前一个节点的分组组合成一个宏节点， 那那么它将不会被包含在新的队列中， 那以后的节点检查。该算法迭代地结合了这样的节点，直到每个节点， 那在每一个节点,测试了马尔可夫毯。

数据可用性

本研究使用的所有数据均来自Konect数据库[23]并且还网络存储库[24，这些都是公开的。软件计算在网络中，可通过请求或https://github.com/jkbren/einet．

信息披露

本出版物中所表达的观点是作者的观点，并不一定反映坦普顿世界慈善基金会的意见。

的利益冲突

作者声明没有利益冲突。

作者的贡献

B.K.和E.H.构思了这个项目。这篇文章是B.K.和E.H.写的。B.K.进行了分析。

致谢

作者感谢Conor Heins，Harrison Hartle，以及Alessandro Vespignani的见解，了解有效信息的符号和形式主义。通过Paul G. Allen Frientiers Group（12171），Allen Discovery Center计划支持该研究。本出版物通过支持Templeton World Charity Foundation，Inc。（TWCFG0273）的批准。该工作也部分由国防科学与工程研究生奖学金（NDSEG）计划提供支持。

补充材料

答：关键术语表。B：有效信息计算。C：导出常见网络结构的有效信息。D：网络主题作为因果关系。E：网络数据表。f：一致的Macronode的示例。G：紧急子图。（补充材料）

参考文献

1. A.-L.巴拉贝西，网络科学，剑桥大学出版社，英国剑桥，2016。
2. M.E.J.纽曼，网络：导论，牛津大学出版社，牛津大学，英国，2010。
3. L. A. N.阿马拉尔和J. M. Ottino，“复杂网络，”欧洲物理杂志b -凝聚态物质，卷。38，没有。2，第147-162，2004。浏览：出版商的网站|谷歌学术搜索
4. A.Koseska和P.I.Bastiaens，“作为认知过程的细胞信号传递，”盟军杂志第36卷第2期5, pp. 568-582, 2017。浏览：出版商的网站|谷歌学术搜索
5. F. A. Rodrigues, T. K. D. Peron, P. Ji, J. Kurths，《复杂网络中的Kuramoto模型》，物理报告，第610卷，第1-98页，2016。浏览：出版商的网站|谷歌学术搜索
6. N.Perra、B.Gonçalves、R.Pastor Satorras和A.Vespignani，“时变网络的活动驱动建模，”科学报告，卷。2，p。2012年1日。浏览：出版商的网站|谷歌学术搜索
7. D. S. Bassett和O. Sporns，“网络神经科学”，自然神经科学，第20卷，第2期。3, pp. 353-364, 2017。浏览：出版商的网站|谷歌学术搜索
8. A-L.Barabási，N.Gulbahce和J.Loscalzo，“网络医学：基于网络的人类疾病治疗方法，”自然遗传学评论，第12卷，第2期1, pp. 56-68, 2011。浏览：出版商的网站|谷歌学术搜索
9. N.增田，M. A.波特，R.兰比特，《网络上的随机漫步和扩散》，物理报告， vol. 716-717, pp. 1-58, 2017。浏览：出版商的网站|谷歌学术搜索
10. C.E.Shannon，“沟通的数学理论，”贝尔系统技术期刊第27卷第2期3，第379-423页，1948。浏览：出版商的网站|谷歌学术搜索
11. E.P.Hoel、L.Albantakis和G.Tononi，“量化因果出现表明宏观可以击败微观，”国家科学学院院刊号，第110卷。49页，19790-19795,2013。浏览：出版商的网站|谷歌学术搜索
12. E.P.Hoel，“上面的代理，下面的原子：代理如何从其基础微物理中因果性地出现”，在走向目标:无意识的数学法则如何产生目标和意图?A. Aguirre, B. Foster, Z. Merali, Eds。那P.P.。6.3.-7.6.那Springer International Publishing, Berlin, Germany, 2018.浏览：谷歌学术搜索
13. G.托诺尼和O. Sporns，“衡量信息一体化”BMC神经科学，卷。4，不。1，p。31，2003。浏览：出版商的网站|谷歌学术搜索
14. j .珍珠因果关系美国纽约，剑桥，2000年。浏览：出版商的网站
15. J. Pearl，“实证研究的因果图”，生物计量学，第82卷，第2期4，第669-688页，1995。浏览：出版商的网站|谷歌学术搜索
16. E. HOEL，“当地图比领土好，”熵，卷。19，没有。5，p。188,2017。浏览：出版商的网站|谷歌学术搜索
17. P.Erdős和A.Rényi，“随机图”，“出版Mathematicae1959年，第6卷，第290页。浏览：谷歌学术搜索
18. B. Bollobas，《随机图的进化》美国数学学会学报，卷。286，没有。1，p。257,1984。浏览：出版商的网站|谷歌学术搜索
19. C. I. Del Genio, T. Gross和K. E. Bassler，“所有无标度网络都是稀疏的，”物理评论信，第107卷，第1页，2011。浏览：出版商的网站|谷歌学术搜索
20. P. L. Krapivsky, S. Redner，和F. Leyvraz，《不断增长的随机网络的连通性》，物理评论信，卷。85，没有。21，pp。4629-4632,2000。浏览：出版商的网站|谷歌学术搜索
21. A.-L.Barabási，R.Albert和H.Jeong，“无标度随机网络的平均场理论，”Physica A：统计力学及其应用，卷。272，没有。1-2，pp.173-187,1999。浏览：出版商的网站|谷歌学术搜索
22. d·j·沃茨和s·h·斯特罗加茨，《小世界网络的集体动力学》，自然，卷。393，没有。6684，PP。440-442，1998。浏览：出版商的网站|谷歌学术搜索
23. J. Kunegis，“konect -科布伦茨网络收藏”，在第22届世界世界范围内伴侣国际会议的诉讼程序，p。1343，里约热内卢，巴西，2013年5月。浏览：谷歌学术搜索
24. R. A. Rossi和N.K.Ahmed，“NetworkRepository：具有多尺度视觉分析的交互式数据存储库”，第二十九届AAAI人工智能会议论文集，p。4292，奥斯汀，德克萨斯州，美国，2015年1月。浏览：谷歌学术搜索
25. G. M.埃德尔曼和J. A.加利，《生物系统的退化和复杂性》，国家科学学院院刊，卷。98，没有。24，第13763-13768，2001。浏览：出版商的网站|谷歌学术搜索
26. G. Tononi, O. Sporns，和G. M. Edelman，“生物网络中退化和冗余的度量”，国家科学学院院刊，第96卷，第2期6，页3257-3262,1999。浏览：出版商的网站|谷歌学术搜索
27. P.K.Rubenstein，S.Weichwald，S.Bongers等人，“结构方程模型的因果一致性”，2017年，https://arxiv.org/abs/1707.00819．浏览：谷歌学术搜索
28. L.页，S.布林，R. Motwani和T.威诺格拉德说：“PageRank的引文排名：把以网络，”技术。众议员，斯坦福Infolab，斯坦福大学，CA，USA，1998年，技术报告。浏览：谷歌学术搜索
29. M. Rosvall和C. T. Bergstrom，“复杂网络上的随机漫步地图揭示了社区结构”，国家科学学院院刊，卷。105，没有。4，pp。1118-1123，2008。浏览：出版商的网站|谷歌学术搜索
30. T.M.Cover和J.A.Thomas，信息论要素，约翰威利和儿子，霍博肯，NJ，美国，2012年。
31. J. Xu, T. L. Wickramarathne，和N. V. Chawla，“代表网络中的高阶依赖”，科学推进，第2卷，文章编号e1600028, 2016。浏览：出版商的网站|谷歌学术搜索
32. W. R.阿什比，控制网络介绍，Chapman＆Hall，伦敦，英国，1957年。
33. W.马歇尔，L.阿尔巴塔基斯，G.托诺尼，《拳击与因果力量》，计算生物学， 2018, vol. 14, p. 1。浏览：出版商的网站|谷歌学术搜索
34. E. Laurence，N. Doyon，L. J.Dubé和P. Desroisiers，“复杂动态网络的光谱尺寸减少”​​，物理回顾X文章编号011042,2019年。浏览：出版商的网站|谷歌学术搜索
35. D.D.Heckathorn和C.Cameron，“网络抽样：从滚雪球和多样性到受访者驱动抽样，”社会学年度回顾号，第43卷。1, pp. 101-119, 2017。浏览：出版商的网站|谷歌学术搜索
36. G. Tononi, G. M. Edelman，和O. Sporns，“复杂性和一致性:整合大脑中的信息”，认知科学的发展趋势，卷。2，不。12，第474-484，1998。浏览：出版商的网站|谷歌学术搜索
37. A.-L.Barabási，e.Ravasz和T.Vicsek，“无规模的无尺寸网络”，Physica A：统计力学及其应用，卷。299，没有。3-4，pp。559-564,2001。浏览：出版商的网站|谷歌学术搜索
38. R.Griebenow，B.Klein和E. Hoel，“找到网络的正确规模：通过光谱聚类的有效识别因果出现，”2019年，http://arxiv.org/abs/1908.07565．浏览：谷歌学术搜索
39. A. R. Benson, D. F. Gleich, J. Leskovec，“复杂网络的高阶组织”，科学第353期6295页，163-166,2016。浏览：出版商的网站|谷歌学术搜索
40. I.Scholets，“网络何时是网络？路径和时间网络中的多阶图形模型选择”，年第23届ACM SIGKDD国际知识发现和数据挖掘会议，p。1037，哈利法克斯，加拿大，2017年8月。浏览：谷歌学术搜索
41. A. R. Benson, J. Leskovec，“网络的高阶聚类”，物理回顾E， 2018年第97卷第1页。浏览：出版商的网站|谷歌学术搜索
42. R. Lambiotte，M. Rosvall和I. Scholtes，“从网络到最佳的复杂系统型号，”自然物理，第15卷，第5期。4，第313-320页，2019。浏览：出版商的网站|谷歌学术搜索
43. D. Gfeller和P. De Los Rios，“复杂网络的光谱粗粒化”。《物理评论快报》，99卷，第5期。3，页38701,2007。浏览：出版商的网站|谷歌学术搜索
44. S. Fortunato和D. Hric，“网络中的社区检测:用户指南”，物理报告，卷。659，第1-44，2016。浏览：出版商的网站|谷歌学术搜索
45. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto，和D. Parisi，《定义和识别网络中的社区》，国家科学学院院刊，第101卷，第1期。9、第2 - 3页，2004。浏览：出版商的网站|谷歌学术搜索
46. M. E. J. Newman和M. Girvan，《发现和评估网络中的社区结构》，物理回顾E，卷。69页。1，2004年。浏览：出版商的网站|谷歌学术搜索
47. K.Friston，“我们所知道的生活”英国皇家学会界面杂志，第10卷，文章编号20130475,2013。浏览：出版商的网站|谷歌学术搜索

版权

版权所有©2020 Brennan Klein和Erik Hoel。这是一篇发布在知识共享署名许可协议，允许在任何媒介中不受限制地使用、分发和复制，前提是原作被正确引用。