多层网络的结构和动力学

S. Boccaletti stefano.boccaletti@gmail.com CNR- Institute of Complex Systems, Via Madonna del Piano, 10, 50019 Sesto Fiorentino, Florence, Italy The Italian Embassy in Israel, 25 Hamered st., 68125 Tel Aviv, Israel G. Bianconi School of Mathematical Sciences, Queen Mary University of London, London, United Kingdom R. Criado Departamento de Matemática Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid, Spain C.I. del Genio Warwick Mathematics Institute, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom Centre for Complexity Science, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom Warwick Infectious Disease Epidemiology Research (WIDER) Centre,
University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom
J. Gómez-Gardeñes Institute for Biocomputation and Physics of Complex Systems, University of Zaragoza, Zaragoza, Spain M. Romance I. Sendiña-Nadal Complex Systems Group, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain Z. Wang Department of Physics, Hong Kong Baptist University, Kowloon Tong, Hong Kong SRA, China Center for Nonlinear Studies, Beijing-Hong Kong-Singapore Joint Center for Nonlinear and
Complex Systems (Hong Kong) and Institute of Computational and Theoretical Studies,
Hong Kong Baptist University, Kowloon Tong, Hong Kong SRA, China
M. Zanin Innaxis Foundation & Research Institute, José Ortega y Gasset 20, 28006 Madrid, Spain Faculdade de Ciências e Tecnologia, Departamento de Engenharia Electrotécnica,
Universidade Nova de Lisboa, 2829-516 Caparica, Portugal
摘要

在过去的几年中,网络理论成功地描述了从生物系统到技术系统和社会系统的各种复杂系统的组成部分之间的相互作用。 然而,直到最近,人们的注意力几乎完全集中在所有组件都被同等对待的网络上,而忽略了有关所研究的相互作用的时间或上下文相关属性的所有额外信息。 直到最近几年,网络科学家利用真实数据集分辨率的提高,才将他们的兴趣转向现实世界系统的多重特征,并明确考虑网络的时变和多层性质。 我们在这里对由其组成部分之间的不同关系(层)组成的图的结构和动态组织进行了全面的回顾,并涵盖了几个相关问题,从基本结构措施的全面重新定义,到理解网络的多层性质如何影响过程和动态。

关键词:
MSC:
[2010] 00-01, 99-00
journal: Physics Reports

1简介

1.1 多层网络接近自然

如果我们把目光转向我们周围发生的绝大多数现象(从影响我们社会关系的现象,到改变我们生活的整体环境的现象,甚至影响我们自身生物功能的现象),我们立即意识到它们是只不过是系统出现的动态组织的结果,而这些系统又涉及大量基本成分(或实体)通过某种复杂的模式相互作用。

现代物理学的主要工作之一是提供这些系统的正确且合适的表示,其中组成部分被视为网络的节点(或单元),并且通过同一网络的链接对交互进行建模。 事实上,一方面拥有这样的表示,另一方面拥有用于提取信息的数学工具库(由应用数学和统计力学几个世纪的思想、概念和活动继承而来)是我们能够获得信息的唯一合适的方式。甚至敢于理解观察到的现象,识别其背后的规则和机制,并可能方便地控制和操纵它们。

过去十五年见证了一场科学运动的诞生,如今它以复杂网络理论的名义广为人知。 它涉及我们一些最优秀科学家的跨学科努力,目的是利用当前可用的大数据,以提取基本复杂系统和机制的最终和最佳表征。 主要目标是i)提取统一原则,这些原则可以包含和描述(在一些通用和通用规则下)普遍检测到的结构适应,以及ii)对由此产生的涌现动态进行建模,以解释我们通过观察此类系统实际看到和体验到的内容。

在这里报告在所研究的特定背景下进行的每一项原创作品看起来甚至是冗长的(事实上,读者会发现,沿着这篇评论,到目前为止就这个主题产生的所有相关文献,在报告的不同部分中进行了适当的处理和组织)。 在这个初始阶段,而是结合关于复杂的开创性文章[1,2,3,4]和经典书籍[5,6,7,8]网络,我们向感兴趣的读者推荐最近在同一本杂志上发表的其他一些报告[9,10,11,12,13],我们相信这些报告可能构成非常好的指南,以帮助他们找到方向关于这个主题的大量文献 特别是,参考文献。 [9] 是复杂网络的结构和动态特性所涉及的思想和概念的完整概要,而参考文献。 [12, 13] 具有通过讨论模块化网络 [12] 和空间嵌入式网络 [13] 的相关文献来陪伴和引导读者的优点 最后,参考文献。 [10,11]是研究网络系统同步组织[11]和网络演化博弈等过程[10]的重要文献。

传统的自然复杂网络方法主要集中于这样的情况,其中每个系统的组成部分(或基本单元)都被绘制成一个网络节点,并且每个单元与单元之间的相互作用被表示为一个(通常是实数)量化的数字。相应图的连接(或链接)的权重。 然而,我们很容易意识到,将所有网络的链路都放在这样一个等价的基础上,是一个太大的约束,有时可能会导致无法完全捕捉到一些现实问题中存在的细节,甚至导致对某些现象的错误描述。这些都发生在现实世界的网络上。

我们认为,以下三个例子代表了该方法的主要局限性。

第一个例子是从社会学借来的。 社交网络分析是行为科学以及经济学、市场营销和工业工程中最常用的范式之一[14],但与社交网络真实结构相关的一些问题尚未得到解决正确理解。 社交网络可以描述为一组人(或一群人),他们之间具有某种联系或交互模式[14, 15] 乍一看,似乎很自然地认为网络成员之间的所有联系或社会关系都发生在同一级别。 但实际情况却大不相同。 社交网络成员之间的实际关系(大部分)发生在不同群体(级别或)内,因此如果仅使用自然局部尺度的观点,则无法正确建模在经典的复杂网络模型中被考虑在内。 让我们思考一下在 Facebook 这样的社交网络上传播信息或谣言的问题。 在那里,所有用户都可以被视为图的节点,并且用户创建的所有友谊都可以被视为网络的链接。 然而,Facebook 中的友谊可能源自不同来源的关系:两个Facebook 的用户可能会分享友谊,因为他们是日常工作中的同事,或者因为他们是同一支足球队的球迷,或者因为他们在某个度假胜地度假期间偶尔见面,或者出于任何其他可能的社交原因。 现在,假设某个给定用户了解给定信息,并希望将其传播给其 Facebook 的好友社区。 显然,用户会首先选择他/她认为可能对信息的特定内容潜在感兴趣的朋友子群,然后才继续将其传播到该子群。 因此,将Facebook表示为独特的熟人网络(并在那里模拟经典扩散模型)将导致得出错误的结论和对系统真实动态的预测。 相反,正确的方法是将每个社会群体划分为不同的交互层,并在每个层上单独操作传播过程。 正如我们将在第 5 节中看到的,这种多层方法实际上会导致一系列戏剧性的重要后果。

本质上多关系(或多路复用)系统的第二个典型示例是在尝试描述交通网络时必须解决的情况,例如航空运输网络 (ATN) [16] 或地铁网络[17, 18] 特别是,ATN的传统研究是将其表示为单层网络,其中节点代表机场,而链路代表两个机场之间的直飞航班。 另一方面,很明显,更准确的映射考虑到每个商业航空公司对应于不同的层,包含同一家公司运营的所有连接。 事实上,让我们假设一下,我们想要通过系统来预测航班调度延误的传播情况,或者这种动态对乘客流动的影响[19] 特别是,参考文献。 [16]考虑了当一部分 ATN 链路(即航班)被随机删除时乘客重新安排的问题。 众所周知,每家商业航空公司在需要为乘客重新安排另一家公司的航班时都会产生相当高的成本,因此它首先尝试利用自己网络的其余部分来为乘客重新安排航班。 正如我们将在第 7 节中详细看到的那样,可以对此类动态过程进行适当预测的正确框架实际上是将 ATN 视为完全多层结构。

转向生物学,第三个例子是科学家试图对生物系统中特定成分的重要性进行排名的努力。 例如,秀丽隐杆线虫C.线虫是一种小型线虫,它实际上是第一个对整个基因组进行测序的生物体。 最近,生物学家甚至能够获得C 的完整图谱。线虫的神经网络,实际上由 281 个神经元和大约两千个连接组成。 反过来,神经元可以通过化学连接或离子通道连接,这两种类型的连接具有完全不同的动力学。 因此,描述此类网络的唯一正确方法是具有 281 个节点和两层的多重图,一层用于化学突触链接,另一层用于间隙连接的相互作用。 最重要的结果是,每个神经元可以在两层中发挥非常不同的作用,并且适当的排序应该能够区分那些在一层中具有高中心性的节点在另一层中仅处于边缘中心的情况。

这三个例子,以及读者将在本报告的其余部分看到的许多其他例子,很好地解释了为什么最近几年的网络科学研究的特点是越来越多地尝试通过发展来推广传统网络理论。 (并验证)用于研究多层网络的新颖框架,即以系统组成部分为节点的图表,并且必须考虑几个不同的连接层以准确描述网络的单元-单元交互,和/或整个系统的并行运作。

多层网络明确地包含多个连接通道,并构成描述通过不同类别的连接互连的系统的自然环境:每个通道(关系、活动、类别)由一个层和相同的节点或实体表示可能有不同类型的交互(每层中有不同的邻居集)。 例如,在社交网络中,我们可以考虑几种不同参与者的关系:友谊、邻近、亲属关系、同一文化社会的成员关系、伙伴关系或同事关系等。

这种范式的变化以不同的方式(多重网络、网络的网络、相互依赖的网络、超图等)进行命名,已经导致了一系列非常相关和意想不到的结果,我们坚信:i)它实际上构成了许多科学领域的新前沿,并且ii)它将在未来几年迅速扩展并吸引越来越多的关注,激发一场新的运动跨学科研究。

因此,我们的目的是,本报告旨在对当前技术状况进行调查和总结,并对未来仍待解决的悬而未决的问题进行深思熟虑的展望。

1.2报告概要

与介绍性序言一起,本报告由其他 8 个部分组成。

在下一节中,我们首先提供将伴随我们其余讨论的整体数学定义。 第 2 节包含几个必须相当正式的部分,以便正确介绍表征多层网络结构的数量(及其数学属性和表示)。 读者会发现尝试定义一个包含不同情况和系统的整体数学框架,稍后将对其进行广泛处理。 不过,如果对多层网络的建模或物理应用更感兴趣,建议读者将第 2 节作为词汇,这将有助于和指导他/她阅读本文的其余部分。

第 3 节总结了迄今为止为生成具有特定结构特征的人工多层网络而引入的各种(增长和非增长)模型。 特别是,我们广泛回顾了迄今为止考虑的两类模型的现有文献:增长的多重网络(其中节点数量随时间增长,并施加基本规则来控制网络结构的动态),以及多重网络集成(最终是满足一组特定结构约束的网络集成)。

第四节讨论了与多层网络的鲁棒性和弹性相关的概念、想法和可用结果,以及多层网络上的渗透过程,这确实近年来引起了巨大的关注。 特别是,就这些过程而言,第 4 节将阐明单层网络的传统方法与网络结构具有多层性质的情况之间的重要差异。

在第 5 节中,我们总结了当前对发生在多层结构之上的传播过程的理解,并明确讨论了线性扩散、随机游走、路由和拥塞现象以及信息和疾病的传播。 本节还包括对多层网络上发生的进化博弈的完整描述。

第 6 节专门讨论同步,我们在那里描述了交替层和共存层的情况。 在前者中,不同的层对应于不同的连接配置,这些连接配置交替定义给定的一组动态单元之间的依赖于时间的耦合结构。 在后者中,不同的层同时负责网络单元的耦合,并考虑到显式的附加层间交互。

第七节是对应用的大量回顾,特别是那些在社会科学、技术、经济、气候学、生态学和生物医学领域研究的应用。

最后,第 8 节介绍了我们的结论性评论和观点。

2 多层网络的结构

复杂性科学是对具有许多相互依赖的组件的系统的研究,这些组件反过来可能通过许多不同的渠道相互作用。 这些系统——以及它们所体现的自组织和新兴现象——是全球知识社会未来面临的许多具有全球重要性的挑战的核心。 这门科学的发展为理解物理、社会、工程、信息和生物科学的许多不同机制和过程提供了全新的方法。 大多数复杂系统包括多个子系统和连接层,并且它们通常是开放的、有价值的、定向的、多层次的、多组件的、可重构的系统系统,并且放置在不稳定和变化的环境中。 它们通过影响局部和全球范围内的子系统和组件的内部和外部动态相互作用来发展、适应和转变。 它们是观察、理解、重建和预测其多尺度和多组分动力学的非常困难的科学挑战的根源。 自然和人工复杂系统的多尺度建模所提出的问题需要对“传统”网络理论进行推广,通过开发坚实的基础和随之而来的新的相关工具来以综合的方式研究多层和多组分系统。 在过去的几年里,为了理解此类系统的结构和动态,人们做了很多工作[20,21,22,23,24] 相关概念,例如网络的网络[25, 26]、多维网络[20]、多级网络、多路网络、交互网络、相互依赖的网络等等被引入,甚至基于张量表示 [21, 22][23, 24] 的不同数学方法也被提出。 本节的目的是调查和讨论多层网络的一般框架,并回顾将概念和模型从单层网络扩展到多层网络的一些尝试。 正如我们将看到的,该框架包括迄今为止文献中讨论的绝大多数不同方法。

2.1 定义和符号

2.1.1 正式的基本定义

多层网络是一对=(𝒢,𝒞),其中𝒢={Gα;α{1,,M}}是一系列(有向或无向、加权或未加权)图Gα=(Xα,Eα)(称为 层)和

𝒞={EαβXα×Xβ;α,β{1,,M},αβ} (1)

是不同层节点GαGβαβ之间互连的集合。 𝒞 中的元素称为 交叉层,每个 Eα 中的元素称为 内层连接,而每个 Eαβαβ)中的元素称为 层间连接。

在剩下的部分中,我们将使用希腊语下标和上标来表示图层索引。 Gα层的节点集将由Xα={x1α,,xNαα}表示,每层Gα的邻接矩阵将由A[α]=(aijα)Nα×Nα表示, 在哪里

aijα={1if (xiα,xjα)Eα,0otherwise, (2)

对于 1i,jNα1αM Eαβ对应的层间邻接矩阵是矩阵A[α,β]=(aijαβ)Nα×Nβ,由下式给出:

aijαβ={1if (xiα,xjβ)Eαβ,0otherwise. (3)

的投影网络是图 proj()=(X,E),其中

X=α=1MXα,E=(α=1MEα)(α,β=1αβMEαβ). (4)

我们用A¯表示proj()=(X,E)的邻接矩阵。

这个数学模型非常适合描述社会系统以及许多其他复杂系统中的现象。 一个例子是阿克塞尔罗德模型[27]中社交网络中的文化传播,因为每个社会群体都可以被理解为多层网络<中的一个 /t2>. 通过使用这种表示,我们同时考虑:

  • (一)

    不同组内的链接,

  • (二)

    (可能)属于不同层的元素之间的链接的性质和关系,

  • (三)

    属于所涉及的每一层的特定节点。

多路复用网络 [28]是一种特殊类型的多层网络,其中X1=X2==XM=X和唯一可能的层间连接类型是那些给定的层间连接节点仅连接到其余层中的对应节点,即每个 α,β{1,,M},αβ 都有 Eαβ={(x,x);xX} 换句话说,多路复用网络由通过不同类型的链路连接的一组固定节点组成。 多重网络的范式是社交系统,因为这些系统可以被视为多个复杂社交网络的叠加,其中节点代表个体,链接捕获各种不同的社会关系。

给定的多路复用网络可以与多个(单层)网络相关联,提供有关它的有价值的信息。 一个具体的例子是投影网络proj()=(X,E) 它的邻接矩阵A¯有元素

aij¯={1if aijα=1 for some 1αM0otherwise. (5)

多重网络概念的第一种方法可能表明这些新物体实际上是在介观尺度上具有某种(模块化)结构的(单层)网络。 很明显,如果我们采用多路复用,我们可以将其与(单层)网络~=(X~,E~)关联起来,其中X~不相交 G1,,GM所有节点的并集,即

X~=1αMXα={xα;xXα} (6)

E~ 由下式给出

(α=1M{(xiα,xjα);(xiα,xjα)Eα})(α,β=1αβM{(xiα,xiβ);xiX}). (7)

请注意,~ 是一个具有 N×M 个节点的(单层)图,其邻接矩阵(称为 supra-adjacency 矩阵)可以写成分块矩阵

A~=(A1INININA2INININAM)NM×NM, (8)

其中 INN 维单位矩阵。

将矩阵分配给多层网络的过程通常称为flatteningunfoldingmatricization 需要注意的是 ~ 的行为相关但又不同,因为 的单个节点对应于 ~ 因此,多路复用的属性和行为可以理解为相应(单层)网络~属性的非线性类型>。

值得注意的是,多层网络的概念扩展了其他数学对象的概念,例如:

  1. 1.

    多路复用网络 正如我们之前所说,具有 M 层的多路复用网络 [28] 是一组层 {Gα;α{1,,M}},其中每个层层是一个(有向或无向、加权或未加权)图Gα=(Xα,Eα),带有Xα={x1,,xN} 由于所有层都具有相同的节点,因此可以将每个 1αβMX1==XM=XEαβ={(x,x);xX} 视为多层网络。

  2. 2.

    时间网络 [29] 时间网络 (G(t))t=1T 可以表示为具有一组层 {G1,,GT} 的多层网络,其中 Gt=G(t)Eαβ= if βα+1,同时

    Eα,α+1={(x,x);xXαXα+1} (9)

    (见图1示意图)。 请注意,这里的 t 是一个整数,而不是一个连续参数,因为稍后将在第 2 节中使用它。 6.1.1

    Refer to caption
    图1: (在线彩色)。 将时间网络映射到多层网络的示意图。 (左侧)在每个时间t=1,2,3,都有一个不同的图来表征系统组成部分之间的交互结构。 (右侧)相应的多层网络表示,其中每个时刻都映射到不同的层。
  3. 3.

    交互互连网络[24] 如果我们考虑一系列相互作用的网络{G1,,GL},它们可以被建模为层{G1,,GL}的多层网络,其交叉层Eαβ对应于之间的相互作用网络GαGβ(见图2)。

  4. 4.

    多维网络 [20, 30, 31, 32, 33] 形式上,边标记多重图(多维网络)[30]是一个三元组G=(V,E,D),其中V是一组节点,D是一组表示维度的标签,E是一组带标签的边,即一组三元组E={(u,v,d);u,vV,dD}

    假设给定一对节点u,vV和一个标签dD,可能只存在一条边(u,v,d) 此外,如果所考虑的模型是有向图,则边 (u,v,d)(v,u,d) 是不同的。 因此,给定|D|=m,G中的每对节点最多可以通过m条可能的边连接。 当需要的时候,可以考虑权重,使得边不再是三元组,而是四元组(u,v,d,w),其中w是一个实数,代表节点之间关系的权重u,vV 并用 dD 标记。 通过将每个标签映射到一个层,可以将多维网络 G=(V,E,D) 建模为多重网络(因此,建模为多层网络)。 具体来说,G可以与层{G1,,G|D|}的多层网络相关联,其中对于每个αDGα=(Xα,Eα)Xα=V,

    Eα={(u,v)V×V;(u,v,d)Eandd=α} (10)

    和每个 1αβ|D|Eαβ={(x,x);xV}

  5. 5.

    相互依赖(或分层)网络 [34,25,35] 相互依赖(或分层)网络是不同网络(层)的集合,其节点彼此相互依赖。 实际上,网络一层的节点依赖于不同层的控制节点。 在这种表示中,依赖关系是连接不同层的附加边。 这种位于网络层之间的结构通常称为介观结构 参考文献中提出了有关相互依赖网络的初步知识研究。 [34](称为分层网络)。 与前面的多维网络情况类似,我们可以通过将每个网络标识为一个层,将相互依赖(或分层)网络视为多层网络。

    Refer to caption
    图2: (在线彩色)。 交互网络到多层网络的相当简单的映射的示意图。 左侧每个不同颜色的网络对应右侧不同的蓝色层。
  6. 6.

    多级网络 [36] 多级网络的正式定义如下。 G=(X,E) 是一个网络。 多级网络是一个三元组𝐌=(X,E,𝒮),其中𝒮={S1,,Sp}G的一系列子图Sj=(Xj,Ej),j=1,,p,例如那

    X=j=1pXj,E=j=1pEj. (11)

    网络G𝐌投影网络,每个子图Sj𝒮被称为切片多级网络𝐌 显然,每个多级网络𝐌=(X,E,𝒮)都可以理解为一个多层网络,每个1αβp都有层{S1,,Sp}和交叉层Eαβ={(x,x);xXαXβ} 可以直接检查每个多路复用网络是否是多级网络,并且多级网络 𝐌=(X,E,𝒮) 是多路复用网络当且仅当 Xα=Xβ 对于所有 1α,βp 而言。

  7. 7.

    超网络(或超图)[37, 38, 17, 39, 40, 41, 42, 43] 超图是一对=(X,H),其中X是非空节点集,H={H1,,Hp}X的非空子集族t3>,每个都称为超链接 现在,如果G=(X,E)是一个图,则超结构S=(X,E,H)是由顶点集X、边集E形成的三元组,和超边集H。如果=(X,H)是一个超网络(或超图),那么它可以被建模为多层网络,这样对于每个超链接h=(x1,,xk)H我们定义一个层Gh,是节点x1,,xk的完整图,交叉层为Eαβ={(x,x);xXαXβ}(见图3

Refer to caption
图3: (在线彩色)。 超图转换为多层网络的示意图。 左侧的红色节点集定义了三个超链接(H1H2H3),每个超链接都映射到由其节点的完整图。

2.1.2 一本小型(不太正式)手册

大量研究表明,表示复杂系统的元素及其与节点和链接的相互作用可以帮助我们深入了解系统的结构、动态和功能。 然而,除了一些复杂的系统外,将它们的组织简单抽象为单层节点和链路是不够的。 正如我们在上一节中讨论的,近年来已经开发了复杂网络对多结构多关系网络的几种扩展[20,21,22,24 、28、25、35、44、45、46、47、48、49、50、51、52、53、54、55、56、57、16、58、59、60] 下面我们简单介绍一下主要的特点。

考虑非局部结构的数学模型包括超图(或超网络)[37]和超结构[17] 然而,这些模型无法将局部尺度与系统的全局和介观结构结合起来。 例如,如果想要模拟谣言如何在社交网络中传播,则不仅需要记住不同的群体通过其某些成员联系在一起,而且认识同一个人的两个人不一定会相互联系。知道对方。 事实上,这两个人很可能属于完全不同的群体或层次。 如果试图用超网络来模拟这种情况,那么我们只考虑社会群体,而不考虑其成员之间的实际关系。 相反,如果使用超结构模型,则无法确定两个节点之间的每个接触属于哪个社会群体。 超网络和超结构不是具有介尺度结构的系统的最佳数学模型的关键在于它们都是基于节点的模型,而许多实际系统将基于节点的观点与基于链接的观点结合起来。

继续以社交网络为例,当人们考虑社交群体中两个成员之间的关系时,不仅要考虑持有该成员的社交群体,还要考虑持有该关系本身的社交群体。 换句话说,如果共享两个不同社会群体的两个人之间存在关系,例如工作和运动环境,则必须明确这种关系是在工作场所产生的,还是具有运动性质。 公共交通系统也存在类似的情况,其中属于多条交通线路的两个车站之间的链接可以作为不同线路的一部分出现。

然而,超图分析的使用还远远不够。 在参考文献中。 [61],作者研究了给定度分布的随机三方超图理论,为传统复杂网络的配置模型提供了扩展,并提供了一个理论框架,其中这些随机图的分析属性调查了。 特别是,分析了三方超图中出现巨型组件的条件,以及这些结构中的经典渗滤事件。 此外,在参考文献中。 [62] 提供了有关三方超图的有用指标集合,使该模型对于基本分析非常稳健。

另一种捕捉同时作用的多种不同关系的数学模型是多维网络[20,30,31,32,33,14,63,64,65,66,67] 多维网络中,一对实体可以通过不同类型的链接来链接。 例如,两个人可能因为是熟人、朋友、亲戚或者因为他们通过电话、电子邮件或其他方式相互通信而被链接。 两个实体之间每种可能的关系类型都被视为网络的特定维度。 在多维网络模型的情况下,网络是一个标记多重图,即节点和边都被标记并且两个节点之间可以存在两条或多条边的图。 显然,可以将仅边缘标记的多重图视为多维网络的特定模型。

当使用边标记多重图来建模多维网络时,节点集表示网络中的实体或参与者集,边表示它们之间的交互和关系,边标签描述关系的性质,即网络的维度。 鉴于标签和维度之间的强相关性,这两个术语通常可以互换使用。 在此模型中,如果 u 有至少一条标有 d 的边,则节点 u 属于(或出现在)给定维度 d 中。因此,给定节点 uVnuu 出现的维数,即

nu=|{dD;thereisvVs.t.(u,v,d)E}|. (12)

类似地,给定一对节点 u,vV,nuv 是标记 uv 之间边的维度数,即 nuv=|{dD;(u,v,d)E}| 通过使每个标签相当于一个层,多维网络可以被视为多层网络。

其他替代模型侧重于在尽可能广泛的意义上研究具有多种交互的网络。 例如,参考文献中使用相互依赖的网络来研究几个现实世界基础设施网络的相互依赖关系。 [25][35],作者还探讨了这些结构的几个属性,例如级联故障和渗透。 与这个概念相关,参见参考文献。 [35] 作者报告了渗透过程中存在临界阈值,在相互依赖的网络和理想气体之间建立了类比。 相互依赖网络的主要优点是它们能够将一种关系中的节点与另一种关系中的许多不同节点进行映射。 因此,介观结构可以将网络N1中的单个节点连接到网络N2中的多个不同节点。 这在没有明确定义的细观结构的其他模型中是不可能的,因此节点是单个不可分割的实体。

多级网络[36]位于多维网络和相互依赖网络之间,因为它们扩展了经典的复杂网络模型和超图模型[37] 通过将维度 d 与等效切片 Sd 结合考虑,多级网络与多维网络完全等效(同构)。 与维度 d 相对应的集合 D 是标有标签 d 的边的集合,即 D={(u,v,x);x=d},而 Sd 是关系 d 的节点和边的集合,即至少有一条边标有 d 的所有 uv 的集合。为了进行更高级的研究,如最短路径检测,在 Ref. [36] 作者还介绍了一种称为辅助图的细观结构。 多级网络𝐌的每个顶点都由辅助图中的一个顶点表示,并且如果𝐌中的顶点属于𝐌中的两个或多个切片图,那么它会被重复多次,其次数与它所属的切片图的数量相同。 E 的每条边都是辅助图中的一条边,并且对于复制顶点和原始顶点之间的每个顶点重复,还有一条(加权)边。 此操作打破了多维网络的同构性,并使这种表示非常接近分层网络[30] 然而,这两个模型并不完全等价,因为在多级网络中,不同切片中的节点一一对应是严格的,而这一条件对于分层网络不成立。 在参考文献中。 [36],作者还定义了多级网络经典网络度量的一些扩展,例如切片聚类系数和效率,以及多级结构的网络随机生成器的集合。

在参考文献中。 [68] 作者通过扩展用于社区检测的流行模块化函数,并通过调整其隐式空模型来适应分层网络,引入了多重网络的概念。 主要思想是用切片表示每一层。 每个切片都有一个邻接矩阵,描述属于先前考虑的切片的节点之间的连接。 这个概念还包括一个介观结构,称为片间耦合,它将特定片Sα的节点连接到另一个片Sβ中的副本。 最近通过许多工作[23, 28, 45, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 59, 60]. 例如,在参考文献中。 [23]提出了一种处理多路复用系统的综合形式体系,并提出了一些表征多路复用系统的指标,包括节点度、边重叠、节点参与不同层、聚类系数、可达性和提供了特征向量中心性。

其他最近的扩展包括多元网络 [69]、多网络 [70, 71]、多切片网络 [68, 72, 73, 74]、多类型网络[75,76,77],多层网络[21,22,78,79],交互网络[24,80,81] t5>,以及网络的网络[46],其中大多数可以被认为是第 2 节中给出的多层网络定义的特殊情况。 2.1.1 最后,值得注意的是,指代具有多种不同关系的网络的术语尚未达成共识。 事实上,来自不同领域的不同科学家仍然使用相似的术语来指代不同的模型,或者对同一模型使用不同的名称。 因此,很明显,引入适合这些新结构的清晰数学模型对于正确分析这些复杂系统中发生的动力学至关重要,即使在今天,这些复杂系统还远未被完全理解。

第 2 节中提出的符号。 2.1.1 只是处理多层网络的可能方法之一,实际上最近还有其他尝试来定义替代框架。 特别是,参考文献中提出的张量形式主义。 [21][22],我们将在第 2 节中对其进行广泛审查。 2.3 似乎很有前途,因为它允许多重度量的综合和紧凑表达。 尽管如此,我们相信我们在这里提出的符号在某种程度上更容易理解并且更容易用于现实世界系统的研究。

在下文中,我们描述了传统上用于表征单层图的结构特性的参数对多层网络环境的扩展。

2.2 表征多层网络的结构

2.2.1 节点的中心性和排名

识别起核心结构作用的节点问题是传统复杂网络分析的主要议题之一。 在单层网络中,有许多众所周知的参数来衡量每个节点的结构相关性,包括节点度、紧密度、介数、类特征向量中心性和 PageRank 中心性。 接下来,我们讨论将这些措施扩展到多层网络。

主要的中心性度量之一是每个节点的:节点拥有的链接越多,它的相关性就越高。 多路复用网络=(𝒢,𝒞)的节点iX的度是向量[20, 23]

𝐤i=(ki[1],,ki[M]), (13)

其中ki[α]是节点i在层α中的度数,即ki[α]=jaij[α] 这种向量型节点度是单层网络中节点度既定定义的自然延伸。

任何中心性度量的主要目标之一是根据节点在结构中的相关性对节点进行排序以生成节点的有序列表。 然而,由于多路复用网络中的节点度是一个向量,因此 M 中没有明确的顺序可以产生这样的排名。 事实上,我们可以在 M 中定义许多完整的顺序,因此我们应该澄清其中哪些是相关的。 一旦计算出节点的向量类型度数,就可以聚合该信息并定义节点iX重叠度[23] , 作为

oi=α=1Mki[α], (14)

oi=𝐤i1 事实上,许多其他聚合度量f(𝐤i)也可以用来计算度中心性,例如ki[1],,ki[M]的凸组合,或𝐤i的任何范数。

其他中心性度量,例如接近度和介数中心性,是基于网络的度量结构。 一旦定义了度量和测地线结构,这些措施就可以轻松扩展到多层网络。 在秒。 2.2.3,读者将找到对多层网络中度量结构的完整讨论,它允许直接扩展这种中心性度量。

测量中心性的另一种方法是利用邻接矩阵的谱特性。 特别是,特征向量中心性不仅考虑每个节点的链接数量,还考虑这些连接的质量[82] 有几种不同的方法可以将这个想法扩展到多层网络,如参考文献中所讨论的。 [28],或在参考文献中。 [83] 其中特征向量中心性用于优化交互竞争网络的结果。 在前一篇参考文献中,提出了多重网络的类特征向量中心性度量的几种定义,以及对其存在性和唯一性的研究。

在复用网络中计算类特征向量中心性的最简单方法是分别考虑每层1αM中的特征向量中心性𝐜α=(c1[α],,cN[α]) 通过这种方法,对于每个节点 iX ,特征向量中心性 𝐜i 是另一个向量

𝐜i=(ci[1],,ci[M])M, (15)

其中每个坐标是相应层中的中心性。 计算完所有特征向量中心性后,独立层类特征向量中心性[28]就是矩阵

C=(𝐜1T𝐜2T𝐜MT)N×M. (16)

请注意,C 是列随机的,因为 𝐜α 的所有分量都是半正定的,而且 𝐜α1=1 对于每个 1αM 都是半正定的,每个节点 iX 的中心度 𝐜iCith 行。至于度类型指标,可以通过使用聚合度量 f(𝐜i)(如和、最大值或 p 正态)来获得每个节点的数字中心度量。 该参数的主要局限性在于它没有充分考虑层与层之间的多级交互及其对每个节点中心性的影响。

如果现在记住,一个节点的中心性必须与其邻居(分布在所有层中)的中心性成正比,并且如果认为所有层具有相同的重要性,则有

xiα,xjαXα,c(xiα)c(xjα) if (xjαxiα)Gα,α{1,,M}, (17)

因此,均匀特征向量类中心性被定义为 [28] 矩阵 A~ 的正特征向量和归一化特征向量 c~(如果存在),其公式为

A~=α=1M(A[α])T, (18)

其中(A[α])T是层α邻接矩阵的转置。 例如,这种情况发生在社交网络中,不同的人可能与其他人有不同的关系,而人们通常有兴趣衡量熟人网络的中心性。

更复杂的方法是考虑网络不同层中不同程度的重要性(或影响力),并将此信息包含在定义各层之间相互影响的矩阵的定义中。 因此,为了计算特定层内节点的重要性,还必须考虑所有其他层,因为其中一些层可能与计算高度相关。 例如,考虑一下老板与他的一名雇员住在同一栋公寓的情况:所有邻居形成的公寓层内的两个人之间的关系与办公室层内发生的关系具有完全不同的性质,但在这种情况下,老板的角色(即他的中心地位)可能比他是住在该公寓楼的办公室里唯一的人更大。 换句话说,需要考虑各层之间的影响力是异构的情况。

为此,可以引入一个影响矩阵 W=(wαβ)M×M,定义为非负矩阵W0,使得wαβ测量对层Gβ给定的层Gα的影响。 𝒢W=(wαβ) 固定后,每层 Gα𝒢 局部异质特征向量样中心性被定义为 [28] 矩阵的正归一化特征向量 cαN(如果存在)。

Aα=β=1Mwαβ(A[β])T. (19)

因此,局部异构特征向量中心性矩阵可以定义为

C=(𝐜1𝐜2𝐜M)N×M. (20)

参考文献中介绍了类似的方法。 [23],但使用矩阵

Aα=β=1Mbβ(A[β])T, (21)

其中 bβ0βbβ=1

另一个重要问题是,一般来说,特定层 α 中节点 xiα 的中心性可能不仅取决于链接到 xiα 的邻居在该层内,而且在属于其他层的 xiα 的所有其他邻居上。 考虑不同知识领域的科学引用的情况。 例如,可能有两名科学家在不同的学科领域工作(一名化学家和一名物理学家),其中一名获得了诺贝尔奖:另一名科学家的重要性将会增加,即使诺贝尔奖获得者在该领域内被引用的次数很少。另一位研究员。 这个论证导致了另一个中心性概念的引入[28] 给定一个多重网络和一个影响矩阵W=(wαβ),类全局异构特征向量中心性被定义为正数和矩阵的归一化特征向量 cNM (如果存在)

A=(w11(A[1])Tw12(A[2])Tw1M(A[M])Tw21(A[1])Tw22(A[2])Tw2M(A[M])TwL1(A[1])TwL2(A[2])TwMM(A[M])T)(NM)×(NM). (22)

请注意,A 是矩阵的 Khatri-Rao 乘积

W=(w11w1MwM1wMM) and ((A[1])T(A[2])T(A[M])T). (23)

与之前所做的类似,我们可以引入符号

c=(𝐜1𝐜2𝐜M), (24)

其中𝐜1,,𝐜MN 然后,类全局异构特征向量中心性矩阵被定义为由下式给出的矩阵:

C=(𝐜1𝐜2𝐜M)N×M. (25)

请注意,一般来说,C既不是列随机也不是行随机,但C所有条目的总和为1。

其他谱中心性度量包括基于带有附加随机跳跃的随机游走者平稳分布的参数,例如 PageRank 中心性 [84] 这些措施的扩展以及多路网络中随机游走者的分析将在第 2 节中讨论。 5

2.2.2 聚类

Watts 和 Strogatz 在参考文献 1 中引入的图聚类系数。 [85] 可以通过多种方式扩展到多层网络。 该系数量化了节点形成三角形的趋势,遵循流行的说法“你朋友的朋友就是我的朋友”。

回想一下,给定网络 𝒢=(X,E) 给定节点 i 的聚类系数定义为

c𝒢(i)=# of links between the neighbors of ilargest possible # of links between the neighbors of i. (26)

如果我们考虑三个人ijk,并且ij之间也存在相互关系在ik之间,i的聚类系数表示jk也属于的可能性彼此相关。 𝒢全局聚类系数进一步定义为所有节点聚类系数的平均值。 显然,局部聚类系数是传递性的度量[86],它可以解释为局部节点邻域的密度。

请注意,全局聚类系数有时有不同的定义,其表达式直接与网络的全局特征相关。 这种替代定义并不等同于前一种定义,它通常用于社会科学[87] 它的表达式有时称为网络传递性[14],是

T=# of triangles in the network# of triads in the network. (27)

为了将聚类的概念扩展到多层网络的环境中,不仅需要考虑层内链路,还需要考虑层间链路。 在参考文献中。 [36],作者建立了多级网络的聚类系数、其层的聚类系数和其投影网络的聚类系数之间的一些关系。 通过将多级网络 的每个切片 Sq 与相应多路复用网络 =(𝒢,𝒞) 的层 Gα 进行识别,可以直接获得这种概括。 在给出多级网络中节点iX的聚类系数的定义之前,我们需要介绍一些符号。

对于每个节点iX,令𝒩(i)为投影网络proj()i的所有邻居的集合。 对于每个α{1,,M},让𝒩α(i)=𝒩(i)XαSα¯(i)是由𝒩α(i)诱导的层Gα的子图,即Sα¯(i)=(𝒩α(i),Eα¯(i)),其中

Eα¯(i)={(k,j)Eα;k,j𝒩α(i)}. (28)

类似地,我们将S¯(i)定义为由𝒩(i)诱导的投影网络proj()的子图。 此外,由𝒩α(i)生成的完整图表将由K𝒩α(i)表示,K𝒩α(i)中的链接数量由|Eα¯(i)|表示。 通过这种表示法,我们可以将 中的给定节点的聚类系数定义为 i

C(i)=2α=1M|Eα¯(i)|α=1M|𝒩α(i)|(|𝒩α(i)|1). (29)

那么,聚类系数可以定义为所有C(i)的平均值。

再次,聚类系数可以用几种不同的方式定义。 例如,我们可以考虑每层聚类系数的平均值Gα 然而,很自然地选择一个定义来考虑给定节点 i 有两个邻居 kj 以及 (i,k)Eα 的可能性>、(i,j)Eβαβ 以及 (j,k)Eγγα,β 这是社交网络中发生的一种情况:一个人i可能在有氧课上认识j,在读书俱乐部认识k,而jk是在超市认识的。 平均各层的聚类系数无助于描述这种情况,而基于投影网络的方法似乎更有意义,下面的例子就是证明:考虑具有层 {G1,G2,G3}X={x1,x2,x3,x4} 的多路复用网络 (图)。4);不难发现,cproj()(xi)=1适用于所有 xiX,但cGα(xi)=0适用于所有 xiα

Refer to caption
图4: (在线彩色)。 聚类系数之间差异的示例。 所有节点的局部聚类系数在每个单层中均为 0,但在投影网络中为 1。

为了建立多路复用网络中节点的聚类系数 C(i) 与投影网络中节点的聚类系数 cproj()(i) 之间的关系,我们可以使用参考文献中采用了相同的论点。 [36] 用于多级网络。 θ(i) 定义为 i 少于两个邻居的层数。 然后,

1Mθ(i)cproj()(i)C(i)cproj()(i). (30)

请注意等式。 (30) 表明C(i) 的范围随着θ(i) 的增加而增加。

虽然前面的示例(图 4)显示了根据各个层定义多路复用中节点的聚类系数的隐含限制,但提供替代的 “层”仍然有意义 定义。 与前面的情况类似,让 𝒩α(i)={jX;jis a neighbor ofiinGα}Sα(i)=(𝒩α(i),Eα(i)),其中 Eα(i)={(k,j)Eα;k,j𝒩α(i)} 请注意,Sα(i) 是由𝒩α(i) 引起的层Gα 的子图。 那么节点i层聚类系数定义为

Cly(i)=2α=1M|Eα(i)|α=1M|𝒩α(i)|(|𝒩α(i)|1). (31)

请注意,Sα(i)Sα¯(i) 的子图。 因此,𝒩α(i)𝒩α(i) 以及 α 层中 i 的邻居之间的最大可能链接数不能超过 i𝒩α(i) 中。 另外,我们还有关系

|𝒩(i)|(|𝒩(i)|1)212α=1M|𝒩α(i)|(|𝒩α(i)|1)+k<j|𝒩k(i)||𝒩j(i)|, (32)

其中最后一个总和有 (M2) 项。 我们可以进一步假设节点可以重新排列,以便 |𝒩α(i)||𝒩α+1(i)| 适合所有 1αM 因此,使用参考文献中描述的方法。 [36],我们可以得到投影网络中的聚类系数cproj()(i)与层聚类系数Cly(i)之间的关系:

Cly(i)Mcproj(𝒢)(i)[1+(M1)(4+θ(i)Mθ(i))]. (33)

节点 i 的层聚类系数的另一种可能定义是切片的聚类系数 cGα(i) 的平均值

Cproj()ly¯(i)=1Mα=1McGα. (34)

两个聚类系数之间存在以下关系[36]

Mmin1αM|𝒩α(i)|(|𝒩α(i)|1)2Cproj()ly¯(i)Cproj()ly(i)Mmax1αM|𝒩α(i)|(|𝒩α(i)|1)2Cproj()ly¯(i). (35)

参考文献中提出了将聚类系数的概念进一步推广到多层网络。 [23][47] 在参考文献中。 [23],作者指出有必要扩展三角形的概念,以考虑到多于一层的存在所增加的丰富性。 他们将 2-三角形定义为由属于一层的一条边和属于第二层的两条边形成的三角形。 类似地,3 三角形是由位于不同层的三​​个边组成的三角形。 为了量化多路复用结构在聚类方面提供的附加值,他们考虑了聚类相互依赖的两个参数,I1I2 I1 (I2) 是只能以 2-三角形(3-三角形)形式获得的多路复用中的三角形数量与聚合中的三角形数量之间的比率系统。 那么,I=I1+I2是聚合网络中不能完全在某一层中找到的三角形的总分数。 他们还定义了一个以节点i为中心的1三元组,例如jik,作为一个三元组,其中边(ji)和边(ik) 位于同一层。 类似地,2-三元组是其两个链接属于系统的两个不同层的三​​元组。 通过这种方式,他们为多路网络建立了两个进一步的聚类系数定义。 对于每个节点i,聚类系数Ci1是顶点在i中的2三角形的数量与数量之间的比率的1-三元组以i为中心。 第二个聚类系数 Ci2 被定义为以节点 i 为顶点的 3 三角形数量与以 i 为中心的 2 三边形数量之比。 正如作者指出的,虽然 Ci1 是与 M2 的多路复用的合适定义,但 Ci2 只能为由至少三层组成的系统定义,并且这两个系数的相关性很差,因此有必要使用这两个聚类系数来正确量化多层网络中三角形的丰度。 对系统的所有节点进行平均,获得网络聚类系数C1C2

在参考文献中。 [23]作者还概括了及物性的定义。 他们提出了两种传递性度量:T1作为2三角形数量与1三元组数量之间的比率,以及T23-三角形的数量与2-三元组的数量之间的比率。 正如作者所强调的,聚类相互依赖性 I1I2、平均多重聚类系数 C1C2 以及多重传递性 T1T2 都是全局网络变量,它们针对网络每一层计算的聚类系数和传递性给出了聚类和三元闭包的多层模式的不同视角。

在参考文献中。 [47],作者通过开发聚类系数的几种多重概括,得出了多重网络传递性的测量,并提供了多重聚类系数的一些不同公式之间的比较。 例如,作者指出,在社会网络和交通网络中,层内集群与层间集群之间的平衡是不同的,这反映了在这些情况下传递性是由不同机制产生的事实。 这种差异根源于层间连接产生的新自由度,并且对于通过聚合获得的单层网络上的聚类系数的计算是不可见的。 因此,推广多重网络的聚类系数使得探索此类现象并更深入地了解网络中不同类型的传递性成为可能。 进一步的多重聚类系数在参考文献中定义。 [64,88,89]

2.2.3 度量结构:最短路径和距离

复杂网络的度量结构与节点之间的拓扑距离有关,以图中的游走和路径来表示。 因此,为了将经典度量概念扩展到多层网络的背景下,有必要首先建立pathwalklengthpath的概念。 t2>。 为了介绍所有这些概念,我们将遵循与参考文献中使用的类似的方案。 [90] 给定一个多层网络=(𝒢,𝒞),我们考虑集合

E()={E1,,EM}𝒞. (36)

中的 walk(长度为 q1)是一个非空交替序列

{x1α1,1,x2α2,2,,q1,xqαq}, (37)

具有 α1,α2,,αq{1,,M} 的节点和边,这样对于所有 r<q 都存在一个 E()

r=(xrαr,xr+1αr+1). (38)

如果边1,2,q1被加权,则行走的长度可以被定义为相应权重的倒数之和。 如果x1α1=xqαq,则称步行​​已关闭

中两个节点 x1α1xqαq 之间的 path ω={x1α1,x2α2,,xqαq},是对 节点的行走,其中每个节点只被访问一次。 循环是一条在同一节点开始和结束的闭合路径。 如果可以找到任意一对节点之间的路径,则多层网络被称为已连接;否则称为断开连接。 然而,可以考虑不同类型的可达性[20, 23],这取决于例如我们是否仅考虑某些层中包含的边缘。

路径的长度是该路径的边数。 当然,在多层网络中至少有两种类型的边,即层内边和层间边。 因此,这个定义的变化取决于我们是否认为层间和层内边缘是等效的。 其他度量定义可以很容易地从单层网络推广到多层网络。 因此, 中两个节点 uv 之间的 大地线是连接 uv 的最短路径之一。uv 之间的 duv 距离是 uv 之间任意一条大地线的长度。 中任意两个顶点之间的最大距离 D() 称为 直径 通过nuv,我们将表示连接uv的不同测地线的数量。如果 x 是节点, 是链接,则 nuv(x)nuv() 将表示连接节点的测地线数量 uv分别经过x

多层网络 𝒩=(𝒢,𝒞)=(𝒢,𝒞) 的子网络,如果对于每个具有 γδγ,δ,都存在 α,β αβ,例如XγXαEγEαEγδEαβ 连通分量的最大连通子网。 如果多层网络中连接同一对顶点的两条路径除了起始点和结束点之外不共享其他顶点,则称它们是顶点无关的。 k-组件是顶点的最大子集,使得子集中的每个顶点都通过k独立路径彼此连接。 对于特殊情况k=2k=3k组件称为双组件三组件 多层网络。 对于任何给定的网络,k组件是嵌套的:每个三组件都是双组件的子集,依此类推。

特征路径长度定义为

L()=1N(N1)u,vXuvduv, (39)

其中|X|=N,也是衡量图性能的一种方法。

效率的概念,由Latora和Marchiori在参考文献中引入。 [91] 也可以以与参考文献 1 中使用的方式类似的方式扩展到多层网络。 [36] 使用相同的符号,多层网络的效率定义为

E()=1N(N1)u,vXuv1duv. (40)

尝试在多层网络的效率E()、其投影的效率E(proj())以及不同层的效率之间进行比较是很自然的E(Gα) 在参考文献中。 [36]有一些分析结果建立了这些参数之间的一些关系。

如果我们认为层间和层内边缘不等价,我们可以给出度量量的替代定义。 =(𝒢,𝒞) 为多层网络,并且

ω={x1α1,1,x2α2,2,,q,xq+1αq+1}, (41)

中的路径。 ωlength可以定义为非负值

(ω)=q+βj=2qΔ(j), (42)

在哪里

Δ(j)={1if j𝒞, (i.e. if j is a crossed layer) 0otherwise, (43)

β 是任意选择的非负参数。

在这种情况下, 中两个节点 ij 之间的 distanceij 所有可能路径中的最小长度。

请注意,对于 β=0,前面的定义简化为投影网络 proj() 中的自然度量,而 β 的正值对应于还考虑了的度量不同层之间的相互作用。

通过用 M×M 非负矩阵 Θ=(β(Gλ,Gμ)) 替换 跳跃权重 β,可以进一步概括路径长度的定义,考虑层之间的不同距离。 因此,路径ω的长度变为

~(ω)=q+j=2qΔ~(j), (44)

在哪里

Δ~(j)={β(Gσ(j1),Gσ(j))if Gσ(j)Gσ(j1),0otherwise. (45)

跳跃权重可以进一步扩展,不仅包含对层跳跃所涉及的两层的依赖,还包含对跳跃开始的节点的依赖。

对于多路复用网络,根据节点可达性[23]来量化单个节点对每层结构的参与也很重要。 可达性是网络系统的一个重要特征。 在单层网络中,它取决于连接节点对的最短路径的存在和长度。 在多级系统中,不同层之间以及每层与聚合拓扑网络之间的最短路径可能显着不同。 为了解决这个问题,参考文献中引入了所谓的节点相互依赖。 [57][92] 节点i的相互依赖λi定义为:

λi=jiψijσij, (46)

其中σij是多路复用网络上节点i和节点j之间的最短路径总数,ψij是节点 i 和节点 j 之间的最短路径,利用两层或多层中的链接。 因此,当所有最短路径都使用至少两层上的边时,节点相互依赖等于1,而当所有最短路径仅使用一层的边时,节点相互依赖等于0。系统。 对所有节点的 λi 进行平均,我们获得网络相互依赖关系。

相互依赖性是一种真正的多重测量,它提供了可达性方面的信息。 它与重叠度等程度度量略有反相关。 事实上,重叠度高的节点拥有更多的链接,可以成为通往其他节点的路径的第一步;因此,它的 λi 可能较低。 相反,重叠度较低的节点可能具有较高的 λi 值,因为作为第一步,其最短路径被限制为较小的边和层集。 该措施在参考文献中得到验证。 [23]关于印度尼西亚恐怖分子的数据集,记录了78个人之间的相互信任、共同行动、通信和商业关系等信息。

2.2.4 矩阵和谱属性

众所周知,网络的邻接矩阵和拉普拉斯矩阵的谱特性提供了对其结构和动态的深入了解[93,94,9] 如果引入适当的矩阵表示,多层网络也可能出现类似的情况。

给定一个多层网络,几个邻接矩阵可以给出有关其结构的信息:其中,最常用的是每层的邻接矩阵A[α]Gα、投影网络proj()的邻接矩阵A¯和超邻接矩阵A 超邻接矩阵的谱与多层网络上发生的几个动态过程直接相关。 使用矩阵 [93, 94, 95] 中矩阵商特征值交错的一些结果,参见参考文献 1。 [79]证明了如果λ1λN是无向多层网络的超邻接矩阵A的谱,并且μ1μnα 是层Gα的邻接矩阵A[α]的谱,那么对于每一个1knα

λkμkλk+Nnα. (47)

复用网络的拉普拉斯矩阵也会出现类似的情况。 复用 的拉普拉斯矩阵 =(也称为 超拉普拉斯矩阵)定义为以下形式的 MN×MN 矩阵:

=(D1𝐋𝟏000D2𝐋𝟐000DM𝐋𝐌)+(βD1β𝐈D12𝐈D1M𝐈D21𝐈βD2β𝐈D2M𝐈DM1𝐈DM2𝐈βDMβ𝐈). (48)

在上面的等式中,IN×N单位矩阵,𝐋α是网络层通常的N×N拉普拉斯矩阵α,其元素为Lijα=siαδijwijα,其中siα是层α中节点i的强度,siα=jwijα. 我们将在第二节看到。 5表明多重网络上的扩散动力学与的光谱特性密切相关。 在参考文献中。 [79],作者证明如果λ1λN是无向多层网络的拉普拉斯矩阵的谱,并且μ1μnαGα层的拉普拉斯矩阵𝐋α的频谱,那么对于每个1knα

μkλk+Nnα. (49)

使用微扰分析[59, 96]可以得到类似的结果。

除了邻接矩阵和拉普拉斯矩阵的谱外,复用网络还研究了其他类型的谱特性,例如不可约性[97] 网络理论中的几个问题不仅涉及矩阵[9]的特征值分析,还涉及特征向量分析。 这种分析通常包括研究正的归一化特征向量(Perron 向量)的存在性和唯一性,如果相应的矩阵不可约(通过使用经典的 Perron-Frobenius 定理),则保证其存在。 至于光谱特性,可以将这种矩阵的不可约性与每层和投影网络上的不可约性联系起来。 在参考文献中。 [28, 97] 证明如果wij>0与投影网络proj()的邻接矩阵A¯不可约,则定义全局异构特征向量中心性的矩阵 A 是不可约的。 当我们考虑多路网络中的随机游走时,类似的情况也会发生[98] 在这种情况下,马尔可夫过程稳态的唯一性由以下形式的矩阵的不可约性保证

𝔹=(P11P12P1MP21P22P2MPM1PM2PMM)(NM)×(NM), (50)

其中 Pαβ=WαβA[β]+vαβ𝐈WαβN×NvαβNWαβA[β] 是矩阵 WαβA[β](参见参考文献 [97])。 可以证明,在某些假设下,如果投影网络proj()的邻接矩阵A¯是不可约的,那么𝔹也是不可约的,因此随机游走在参考文献中提出。 [98] 具有独特的静止状态。

2.2.5 中尺度:基序和模块化结构

网络分析的一个基本方法是检测称为社区(或内聚群体)的介观结构。 这些社区是不相交的节点组(集),它们彼此之间的连接比与网络其他部分的连接更加紧密[12, 99, 100] 模块化是一个标量,可以将网络的任何分区计算为不相交的节点集。 实际上,模块化是一种质量函数,它计算社区内的边缘与随机预期的边缘相比。 因此,人们试图确定一种最大化模块化的分区,以识别网络内的社区。

在参考文献中。 [21],多层网络的模块化定义,其中作者引入了一个张量,该张量对定义零模型的随机连接进行编码。 参考号 [68]为在非常一般的环境中研究社区结构提供了一个框架,涵盖随时间演变、具有多种类型的链接(多重性)和多种规模的网络。 作者将通过质量函数确定社区结构推广到通过耦合多个邻接矩阵定义的多切片网络。

如上所述,群落是主要在全球层面定义的中尺度结构。 人们可能会问更多的局部介尺度,即那些定义略高于单节点水平的介尺度,是否也可以扩展到多层网络。 毫无疑问,其中最重要的是基序,即网络中重复出现的小子图,其频率高于随机图中预期的频率[101] 它们的重要性在于,它们可以被理解为基本构建块,每个块都与全局系统中的特定功能相关联[102]

迄今为止,很少有人关注理解多层网络中图案的含义。 参考文献中提出了一个重要的例外。 [63] 在 Pardus 社交网络的分析框架中,这是一个由 300.000 玩家在虚拟世界中互动的在线社区。 当链接被分组为两层时,对应于积极和消极的互动,一些结果结构(可以被视为多层主题)出现的频率要高得多(例如,共享积极关系的三元组用户)或更低(例如,两个敌人用户两者都与第三个存在正相关关系)比随机网络中预期的要多。

Refer to caption
图5: 第 2 节中讨论的单工网络的示意图。 2.3,其邻接矩阵如表1所示。

2.3 矩阵和张量表示:谱属性

文献中已经尝试过使用张量[21,22,47]的概念来正确建模多层网络。 在描述这些结果之前,我们回顾一些基本的张量分析概念。

考虑张量有两种主要方法:

  • (1)

    作为多线性映射的张量;

  • (2)

    张量作为两个或多个向量空间的张量积的元素。

前者应用较多。 后者更抽象,但更强大。 两个实向量空间 𝒱 的张量积,用 𝒱 表示,由 vw 的有限线性组合组成,其中 v𝒱w

实向量空间𝒱的对偶向量空间是线性函数f:𝒱的向量空间,用𝒱表示。 Hom(𝒱,)表示从𝒱的线性函数集,线性空间𝒱Hom(𝒱,) 此外,如果𝒱是有限维向量空间,则线性空间𝒱𝒱之间存在自然同构(取决于所考虑的基)。 事实上,如果𝒱是有限维的,𝒱𝒱之间的关系以抽象的方式反映了(1×N)之间的关系。 (N×N) 矩阵的行向量和 (N×1) 列向量。 然而,如果𝒱是有限维的,那么我们可以用Hom(𝒱,)来识别线性空间𝒱 因此,张量σ𝒱可以理解为线性函数σ:𝒱,因此,一旦确定了对应向量空间的两个基,就可以用特定的矩阵来标识张量。

现在,让我们考虑一个由 M{Gα;1αM}Gα=(Xα,Eα)X1==XM={x1,,xN}=X 组成的多路复用网络 ,为了将其描述为张量积

=X{1,,M}, (51)

其中 i 表示层 Gi

通过将向量族中的有限数乘以非零标量(通常是实数)并将结果相加,可以获得向量族的线性组合。 向量族的跨度是它们所有线性组合的集合。 下面,我们将向量族 {v1,,vm} 的跨度表示为

span({v1,,vm})={v1,,vm}. (52)

给定集合 {x1,,xN}{1,,M},我们考虑它们所有线性组合的 上的形式向量空间,如下所示:

𝒱={x1,,xN}, (53)
={1,,M}. (54)

很容易检查 {x1,,xN}{1,,M} 分别是 𝒱 的基础,因此

{xiα;1iN,1αM} (55)

𝒱的基础。 因此,我们可以赋予xiα直观的含义为“在节点i中并且在层α中”。

Refer to caption
图6: (在线彩色)。 通过复制图5的网络并将每个节点与另一层中的对应节点连接而获得的两层多路复用网络的示意图。
x1 x2 x3
x1 0 1 1
x2 0 0 1
x3 1 0 0
表格1: 5中单体的邻接矩阵

现在,如果我们考虑一个由 N 节点组成的单层网络 G=(X,E),其中有 V={x1,,xN},我们可以用线性变换 σ:VV 来识别 G,这样,与 σ 关联的矩阵相对于基 X={x1,,xN} 就是 G 的邻接矩阵。

因此,如果 G 的邻接矩阵是 A,我们只需将左侧的 A 乘以 ith 规范基础行矢量,就能一步找到从任意节点 i 访问的节点集。 例如图5中图的邻接矩阵为

(011001100). (56)

从节点 1,我们可以一步访问节点 2 和 3,因为

(100)(011001100)=(011). (57)

以同样的方式,N节点和层{1,,M}的多层网络可以通过线性变换σ:𝒱𝒱来识别,其中X={x1,,xN},

𝒱={x1,,xN}, (58)
={1,,M}. (59)
Refer to caption
图7: (在线彩色)。 具有层间连接的通用两层网络的示意图。

很容易检查 完全由与 σ 相关的矩阵相对于基确定

{xiα; 1iN,1αM}, (60)

例如,考虑带有 X={x1,x2,x3} 的单层网络 G=(X,E),其邻接矩阵 A 在表 1 中给出。

x1 x2 x3
x11 x12 x21 x22 x31 x32
x1 x11 0 1 1 0 1 0
x12 1 0 0 1 0 1
x2 x21 0 0 0 1 1 0
x22 0 0 1 0 0 1
x3 x31 1 0 0 0 0 1
x32 0 1 0 0 1 0
表2: 通过复制图5的网络并将每个节点与另一层中的对应节点连接而获得双工的邻接矩阵。

现在考虑具有层 {1,2} 和节点 X={x1,x2,x3} 的多路复用网络 ,通过在两层中复制先前的单工网络并将每个节点与其对应节点连接来获得在另一层(图6)。 的邻接矩阵如表2所示。

当然,表示张量的特定矩阵取决于我们对所选基的元素进行排序的方式。

{xiα;i{1,,N},α{1,,M}}, (61)

但是,如果 AB 是分配给同一张量的两个不同矩阵,则存在一个置换矩阵 P,使得 B=PAP1,因此两个矩阵具有相同的光谱特性(参见第 2.2.4 节)。

如果在前面的例子中我们交换层和节点的顺序,我们会得到一个不同的邻接矩阵,称为上邻接矩阵(表3),可以写成通常的形式

𝒜=(A1I3I3A2)6×6, (62)

其中Ai是层i的邻接矩阵。 注意,与复用网络的情况不同,一般多层网络的超邻接矩阵中的块不一定是方阵。 值得一提的是,通过比较表2和表3可以观察到层和节点之间的双重角色。

通用 2 层网络的示例如图 7 所示,我们可以一步从节点 x11 传递到节点 x22 ,并从节点 x31 到节点 x12 其邻接矩阵如表4所示。 需要强调的是,虽然具有 M 层和 N 节点的多层网络的邻接矩阵具有 N2M2 条目,但具有相同的层和节点完全由 N2M+M2 元素决定。 事实上,M层的复用网络完全由层对应的M邻接矩阵及其影响矩阵W=(wαβ)M×M决定,即非负矩阵W0,使得wαβ是层Gα对层Gβ的影响。

1 2
x11 x21 x31 x12 x22 x32
1 x11 0 1 1 1 0 0
x21 0 0 1 0 1 0
x31 1 0 0 0 0 1
2 x12 1 0 0 0 1 1
x22 0 1 0 0 0 1
x32 0 0 1 1 0 0
表3: 对应于图6中的双工网络的超邻接矩阵(定义见正文)。
x1 x2 x3
x11 x12 x21 x22 x31 x32
x1 x11 0 1 1 1 1 0
x12 1 0 0 1 0 1
x2 x21 0 0 0 1 1 0
x22 0 0 1 0 0 1
x3 x31 1 1 0 0 0 1
x32 0 1 0 0 1 0
表 4: 具有层间连接的两层网络的邻接矩阵如图7所示。

多层网络、多维网络、超图和其他一些对象可以用张量表示,这代表了实现不同模型的便捷形式[103] 具体来说,张量分解方法[103, 104]和多路数据分析[105]已被用于研究各种类型的网络。 此类方法基于将多层网络表示为邻接高阶张量,然后应用奇异值分解(SVD)[106]等方法的推广,以及CANDECOMP(规范分解)的组合Carroll 和 Chang [107] 提出的模型以及 Harshman [108] 提出的 PARAFAC(平行因子)得出 CANDECOMP/PARAFAC (CP)。 这些方法已用于提取社区[104]、对节点[109, 110]进行排名以及执行数据挖掘[103, 111, 112].

2.4 多路复用网络中的相关性

多重网络编码的信息比单独的单层要多得多,因为它们包含不同层中节点的角色之间以及单层统计属性之间的相关性。 发现多层网络中统计上显着的相关性可能是网络科学未来几年的主要目标之一。 在这里,我们概述了迄今为止探索的主要相关类型。 我们区分:

  • 1.

    层间度相关性
    一般来说,这些相关性能够指示一层中的集线器是否也是另一层中的集线器,或者它们通常是低度节点。

  • 2.

    重叠和多度
    节点连接模式可以在两层或多层中相关,并且这些相关性可以通过链路的重叠来捕获。 例如,我们通常有很大一部分朋友通过多种通信方式进行交流,例如电话、电子邮件和即时消息。 这意味着手机社交网络与电子邮件通信或即时消息通信有很大的重叠。 链接的重叠可以通过两层之间的全局或局部重叠来量化,或者通过确定特定重叠模式的节点的多度来量化。

  • 3.

    加权多重的多重强度和逆多重参与比
    不同层中链路的权重可以与复用的其他结构属性相关。 例如,我们倾向于以不同于其他科学家的方式引用合作者。 多重强度和逆多参与比捕获了多重结构属性和权重分布之间的这些类型的相关性。

  • 4.

    节点成对复用
    当节点并非在所有层中都处于活动状态时,两个节点可以具有相关的活动模式。 例如,它们可以在同一层或不同层上处于活动状态。 这些相关性由节点成对多重性捕获。

  • 5.

    层对多重性
    当节点并非在所有层中都处于活动状态时,两个层可以具有相关的活动模式。 例如,它们可以包含相同的活动节点或不同的活动节点。 这些相关性由层对多重性捕获。

2.4.1 多路复用网络中的度相关性

Multiplex 的每个节点 i=1,2,,N 在每个层 α=1,2,,M 中都有一个度 ki[α] 不同层中同一节点的度可以相关。 例如,作为科学协作网络中的中心的节点也可能是科学家之间的引用网络中的中心。 因此,协作网络的程度与引文网络的程度呈正相关。 当一层的中心不是另一层的中心时,也存在负相关性。 评估层α和层β之间的程度相关性的方法如下:

  • 1.

    矩阵P(kα,kβ)的完整表征。
    可以构造矩阵

    P(kα,kβ)=N(kα,kβ)N, (63)

    其中 N(kα,kβ) 是在 α 层中具有度数 kα 且在 β 层中具有度数 kβ 的节点数。 从这个矩阵中,可以确定相关性的完整模式。

  • 2.

    α 中的平均度以层 β 中节点的度为条件
    更粗粒度的相关性度量是 kα¯(kβ),即层 α 中节点的平均度以层 β 中同一节点的度为条件:

    k¯α(kβ)=kαkαP(kα|kβ)=kαkαP(kα,kβ)kαP(kα,kβ). (64)

    如果该函数不依赖于kβ,则两层中的度数不相关。 如果该函数在kβ内增加(减少),则两层中节点的度呈正(负)相关。

  • 3.

    Pearson、Spearman 和 Kendall 相关系数
    更粗粒度的相关性度量是 Pearson、Spearman 和 Kendall 相关系数。

    皮尔逊相关系数 rαβ 由下式给出

    rαβ=ki[α]ki[β]ki[α]ki[β],σασβ (65)

    其中σα=ki[α]ki[α]ki[α]2 如果度分布较宽,则皮尔逊相关系数可以由高度节点的相关性主导。

    αβ两层中度数序列{ki[α]}{ki[β]}之间的Spearman相关系数ραβ为给出的

    ραβ=xiαxiβxiαxiβσ(xα)σ(xiβ), (66)

    其中 xiα 是度数 ki[α] 在序列 {ki[α]} 中的秩,xiβ 是度数 ki[β] 在序列 {ki[β]} 中的秩。 此外,σ(xiα)=(xiα)2xiα2σ(xiβ)=(xiβ)2xiβ2 Spearman系数的问题是每个度序列中的度的等级不是唯一定义的,因为度序列总是具有一定的简并性。 因此,斯皮尔曼相关系数不是一个唯一定义的数字。

    度数序列 {ki[α]}{ki[β]} 之间的肯德尔 τ 相关系数是考虑排名序列 {xiα}{xiβ} 如果一对节点 ij 在两个序列中的排名相同,即 (xiαxjα)(xiβxjβ)>0,则它们是一致的,否则不一致。 Kendall 的 τ 根据一致对的数量 nc 和不一致对的数量 nd 来定义,并由下式给出

    τ=ncnd(n0n1)(n0n2). (67)

    在上面的等式中,n0=1/2N(N1) 以及项 n1n2 解释了秩的简并性,由下式给出

    n1=12nun(un1),
    n2=12nvn(vn1), (68)

    其中un是度序列{ki[α]}nth绑定组中的节点数,vn是度数序列 {ki[β]}nth 绑定组。

多路复用网络中的度相关性水平可以通过向多路复用[48]的节点重新分配新标签来调整。 为了简单起见,让我们考虑一个双工,其中我们有两个度序列 {ki[1]}{ki[2]},如参考文献中所建议的。 [48] 可以重新分配第 1 层和第 2 层中的节点标签,以便在两个度数序列之间生成所需的相关性。 假设我们已经对两层中的度数序列进行了排序。 如果两个序列中节点的标签都是按照每层度的递增秩给出的,则序列是最大正相关(MP),即两个序列中同等秩的节点是该序列的副本节点。多路复用。 反之,如果一层节点的标签按照同层度的升序给出,而另一层节点的标签按照同层度的降序给出,两个度数序列是最大负相关(MN)。 在图8中,给出了从多路复用网络的两层中的两个给定度数序列构造最大正相关(MP)和最大负相关(MN)的示例。

Refer to caption
图8: (在线彩色)。 三种相关多重网络的示意图:最大正 (MP)、不相关 (UC) 和最大负 (MN)。 网络的每一层都有不同类型的链路,分别用实线和虚线链路表示。 经参考文献许可重印图。 [48] © 2014 美国物理学会版权所有。

2.4.2 重叠和多重

多种数据集,包括综合机场网络、在线社交游戏、协作和引用网络[63,78,113],显示出明显的链接重叠。 这意味着两个不同层中同时存在的链路数量相对于两层中的链路总数不可忽略。

两层αβ[49, 63]之间的总重叠Oαβ定义为层 α 和层 β 之间共有的链接总数:

Oαβ=i<jaijαaijβ, (69)

其中αβ

有时定义两层 αβ [49] 之间的局部重叠 oiαβ也很有用t4>,定义为节点i的邻居总数,这些节点同时是层α和层β中的邻居:

oiαβ=j=1Naijαaijβ. (70)

多层网络中的总重叠和局部重叠可能非常显着。 以参考文献中研究的在线社交游戏为例。 [63] 在此数据集中,友谊层和通信层有显着的重叠,类似于通信层和贸易层。 即使是敌意和攻击这两个“负面”层面,其联系也存在显着的重叠。 作为具有显着重叠的多重网络的第二个示例,请考虑引用和协作网络的 APS 数据集[113] 该数据集中的两个层显示出显着的重叠,因为两位合著者通常也在他们的论文中互相引用。

表征链接重叠的一种方法是引入多重链接[49, 113]的概念。 多重链路完全确定多路复用中任何给定两个节点 ij 之间存在的所有链路。 例如,考虑具有 M=2 层的多路复用,即图 9 中所示的双工。 节点 1 和 2 通过第一层中的一条链路和第二层中的一条链路连接。 因此,我们说节点通过多重链路 (1,1) 连接。 同样,节点 2 和 3 在第一层中通过一条链路连接,在第 2 层中没有链路连接。 因此,它们通过多重链路(1,0)连接。 一般来说,对于M层的复用,我们可以按以下方式定义多链接多度 让我们考虑向量 m=(m1,m2,,mα,mM),其中每个元素