复杂超图
摘要
提供自然和人类复杂结构的抽象表示是一个具有挑战性的问题。 在考虑系统异构组件的同时考虑到分析的易处理性是一个困难的平衡。 在这里,我介绍复杂超图(chygraph),汇集了超图、多层网络、单纯复形和超结构的概念。 为了说明这种组合结构的适用性,我计算了组件大小统计数据并确定了向巨型组件的过渡。 为此,我介绍了一种矢量化技术,可以解决 chygraph 的多层次性质。 我的结论是,chygraph 是复杂系统的统一表示,可以进行分析洞察。
我简介
图是多粒子系统的结构抽象,顶点代表粒子,边代表粒子之间的成对相互作用Albert and Barabási (2002)。 超图是允许两个或多个顶点之间交互的扩展Ghoshal 等人 (2009);巴斯克斯(2009);库蒂尼奥等人 (2020); Civilini 等人 (2021);孙和比安科尼(2021)。 多重网络引入了不同交互类型的层Gómez 等人 (2013)。 单纯复形将连通性扩展到包含层次结构Petri 和 Barrat (2018);考特尼和比安科尼 (2018); Iacopini 等人 (2019)。
也有自指结构。 Joslyn 和 Nowak 引入了 ubergraphs Joslyn and Nowak (2017),这是一种边可以包含其他边的组合结构。 ubergraphs 已用于组织知识数据库中的关系Yadati 等人 (2021)。 在更高的抽象层次上,Baas 使用范畴论 Baas (2019) 中的概念引入了高阶结构,也称为超结构。
在实践中,什么是合适的表示是一个平衡问题。 我们希望超图的灵活性能够超越成对相互作用、多层的可能性以及单纯复形和超结构的分层包含结构。 反过来,我们希望图表能够简单地计算聚合属性,例如巨型组件的大小。
II 关键定义
II.1 动机
复杂的系统被简化以方便分析。 逐渐地,我们删除了一些简化并更接近真实的系统。 例如,科学出版物系统根据所提出的问题由不同的网络结构表示Newman (2001); Barabási 等人 (2002)。 引文网络表明知识沿着出版物的流动Redner (1998); Lehmann等人(2003)。 在引文网络中,节点是出版物,引文由定向链接表示。 当专注于合作时,合着网络更适合。 作者-出版物网络可以进一步扩展以明确表示作者和出版物,从而产生二分图Newman (2001)。 相同的作者-出版物关系可以表示为作者超图,其中出版物是关联一位、两位或更多作者 Vasilyeva 等人 (2021) 的超边。 这些网络和超图是简化的,失去了原始系统的某些方面。 我们需要更完整的表示和更丰富的组合结构。 科学出版物包含作者和参考文献。 文档内部结构可以用具有两条边的超图表示,即作者和参考文献列表。 最重要的是,出版物是高阶结构中的一个顶点,其中的构建块是作者和出版物。 通俗地说,是超图的超图,复杂的超图。
II.2 复杂系统
在这里,我在结构意义上使用“复杂”这个术语:由不同的部分组成。 我区分了不可分解为其他部分的部分、原子以及由其他部分(包括原子)组成的复合体。 原子可以具有更精细的结构,但它们已被选为主要构建块。 这些基本知识导致了复杂系统的自洽定义。
定义。复杂系统是原子和络合物的集合,其中络合物是由原子和其他络合物组成的。
后者作为复杂系统的哲学定义。 对于实际应用,我们需要精确的数学结构。 选择取决于复合体的内部结构。
II.3 超图
超图是顶点集和超边集,其中超边是的子集。为了便于说明,我根据上面介绍的复杂系统的措辞重写了这个定义。 超图是一个原子集和一个复数集,其中复数是的子集(超边)。 显然,超图不具备复杂系统的自指属性。 它们的结构很简单。
II.4 超级图
为了使超图具有自指性,Joslyn 和 Nowak 引入了超级图 Joslyn and Nowak (2017),这是一种超边可以包含其他超边的组合结构。 这里我用上面介绍的复杂系统的措辞重新定义它们。
定义。 ubergraph 是一组原子 和一组复合体 ,其中复合体是 。
II.5 复杂超图
为了添加更多内部结构,我选择超图。 这就引出了复杂超图的定义。
定义。复杂超图(chygraph) 是一组原子和一组复合体,其中复合体是具有顶点集的超图在中。
让我们用一些例子来解释这个定义。 图 由 chygraph 表示,其中复合体是边。 具有分层图 、 的多重图 Gómez 等人 (2013) 由 chygraph 加上一些分区表示下面讨论的结构。 科学出版物系统由 chygraph 表示,其中原子是作者,复合体是出版物,出版物由具有两条边的超图表示( 代表作者, 用于参考),索引 贯穿所有出版物。 两条边没有重叠,因此代表科学出版物的复合体具有两个内部组件(图1)。
我们可以将 chygraph 视为具有两种边缘类型的超级图:与超图相关的复合体中的边和复合体。 该复合体充当一个特殊的边缘,我们将其指定为包含的基本单元。 反过来,超级图是 chygraph,其中所有复杂内超图都包含一条边。 显然,在这种情况下,复杂内超图只有一个其大小等于超边基数的分量。 因此,在用超边基数替换组件大小后,以下部分中得出的所有结果对于超级图均有效。
II.6 Cygraphs 属性
图/超图的许多属性都被延续到了 chygraph 中。 为了区别与复杂超图结构相关的度量,我将使用希腊字母来命名 chygraph 级别的数量。 给定一个复杂的 ,令 为其关联的超图。 令 为原子或复合物,其中 和 。 我将使用与 等效的符号 。 chy-邻接矩阵 是具有矩阵元素的 矩阵
(1) |
其中。 关联的顶点 chy 度
(2) |
需要额外的指标来表征潜在的多层结构。 Chygraph 可能包含多个级别的包含内容。 在较低的层次上,我们有原子,其精细结构为空或未指定。 在上面一层我们有复合体,它们的内部结构被指定为包含原子和/或其他复合体作为顶点的超图。 在某些系统中,定义更高级别的内含物是有意义的。 例如,当按地点描述人口时,我们会谈论社区、城市、国家、大陆和世界。 这种包含层次结构导致了 chygraph 长度的定义。
定义:chygraph长度。 令 为 chygraph。 令 为 的一个分区,它是非拦截的( 代表 )、分层(如果 然后 )并且同一分区内的复合体具有相似的统计特性。 chygraph 长度由 表示,是所有此类分区中的最大值 。
通过统计属性区分分区允许指定多类型结构。 多重图和超图就是这种情况。 在这种情况下,两个层可以具有相同的顶点集,但是根据层的不同,复合体可以具有不同的统计属性。
与高阶网络 De Domenico 等人 (2013) 的情况一样,我们可以将聚类系数和熵等其他指标扩展到 chygraph。 在这里,我将注意力限制在以下部分所需的指标上。
III渗流理论一:无层内夹杂物
尽管其复杂性,chygraph组合结构仍适合分析处理。 我专注于渗透,这是图论的一个核心问题。
生成函数技术已被用来解决图和超图中的渗流问题 Callaway 等人 (2000); Ghoshal 等人 (2009);库蒂尼奥等人 (2020);孙和比安科尼(2021)。 它遵循一个简单的方法:将组件尺寸分布的生成函数表示为自身的递归函数,并由其他相关分布的生成函数进行调制。 在糜烂图中,关键量是组件大小 和多余组件大小 ,当组件分别从层 随机取样或从另一层 取样时。 这里我们需要精确地了解我们如何从另一层到达。
我们可以通过两种不同的方式得出参考复合体。 来自它包含的复合体(来自下面)或来自它所包含的复合体(来自上面)。 如果没有层内连接,则符号 不需要任何进一步的规范。 当时,很明显我们是从下面到达的。 相反,当时,我们是从上面到达的。 在本节中,我假设没有层内连接。 层内连接的情况将是下一节的主题。
组件大小取决于 chy 度 的联合分布、复杂超图组件大小 及其多余等价 和 从层 到达时。符号)表示层的复合体内的组件由来自的顶点组成。 反过来,表示层的顶点的chy-度被分解为层的顶点的chy-度。 、、、、和的概率生成函数分别用、、、、和表示。 由于它们是概率分布的生成函数,因此在 处求值时它们都等于 1,并且它们的一阶导数等于相应的期望值。
III.1 平均组件尺寸
chygraph 的定义被转化为组件尺寸生成函数的一组自洽方程。 作为指导,我们到达一个参考复合体,然后从复合体中我们导航 chygraph。 遵循 chygraph 邻接矩阵,引导我们找到包含参考复合体的复合体,或者遍历参考复合体超图中包含的复合体。 更确切地说,
(3) | |||||
(4) | |||||
其中。 请注意,这些方程右侧的第一个 对应于参考复合体,包含 和 的项使用 chygraph 邻接矩阵进行导航(包括参考复合体的复合体)以及包含 和 的术语,用于在参考复合体超图中导航复合体。
III.2 平均组件尺寸
矩阵方程(5)可以通过矩阵方程Horn等人(1994)的矢量化方法求解。 向量化运算符 通过堆叠 的列,将 矩阵转换为 列向量。 例如,
(6) |
为了处理具有四个索引的张量,我概括了向量化运算符。 作用于 张量的矢量化运算符通过沿列堆叠上部索引和沿行堆叠下部索引来创建 矩阵。 例如,
(7) |
应用矢量化方程。 (5) 转换为
(8) |
在哪里
(9) |
(10) |
是整数 Heaviside 阶跃函数(如果 则为 ,否则为 0)。 线性方程组 (8) 将克拉默规则作为形式解
(11) |
其中 派生自 ,通过用 替换第 列。 如果 不是单数,则该解决方案有效。 当时,平均成分尺寸发散,系统实现渗透。 因此,chygraph临界渗透条件由下式给出
(12) |
III.3 巨型组件
平均组件尺寸 (8) 的公式在 条件下有效。 下面我将证明 对应于亚临界相。 令 为随机选择的层 中的顶点不属于巨型组件的概率,令 为层中的顶点不属于巨型组件的概率从层的复合体中选择的不属于巨型组件。 这些概率满足自洽方程
(13) |
(14) |
该方程组没有显式解析解。 可以通过逐次逼近找到解决方案,其中将迭代 插入右侧后,将左侧解释为 迭代。 特别是,在没有巨大组件的情况下,方程。 (13) 和 (14) 承认解。 让我们假设 ,其中 。 将等式中 中的项保持为一阶。 (14) 得出递归近似方程
(15) |
当且仅当 时,线性映射 (15) 收敛于 ,其中 是 。 因此是巨型组件存在的控制参数。 在亚临界(超临界)相 () 中,不存在(存在)巨型组件,且 () 。 渗流转变发生在临界条件,这相当于等式: (12)。
三.4
超图 映射到一层 chygraph,其中复合体是超图边缘:。 在这种情况下,多余的组件大小是多余的超边基数,多余的原子度是顶点的多余度 。 代入等式。 (17) 得到超图的临界条件:,与 Coutinho et al Coutinho 等人 (2020 )。 此外,图是基数超过 1 的超图,因此,临界条件降低为 ,如 Molloy 和 Reed Molloy 和 Reed (1998) 以及 Callaway et al Callaway 等人 (2000).
三.5
III.6分层包含
在许多系统中,包容性遵循层次结构。 地理缩放,例如 Okabe 和 Sadahiro (1996)。 在 chygraph 中构建分层包含很简单:原子包含在第 1 层复合体中,第 1 层复合体包含在第 2 层复合体中,……层 复合体包含在层 复合体中。 在这种情况下,如果 或 ,则 的张量元素为零。对于 的情况,此约束导致消除等式中的第二行和第五行以及第二行和第五列(19),导致
(20) |
展开后一个行列式并代入张量 的显式形式(方程 (9)),我们得到
(21) | |||||
在括号内,我们单独列出了每一层的临界条件。 最后一项表示包括两层在内的交互。 后者是层次包容的真正复杂性。 前两个括号内的项可以为正,这意味着没有标准的 1 层渗透,并且 可能由于最后一个交互项而变为 0。
III.7 多重超图
多重超图是另一种多层结构Sun and Bianconi (2021)。 多重超图是一组具有相同顶点集的超图。 请注意,当超图 的统计属性不同时,多重超图在统计上不等于 。 多重超图可以映射到 chygraph ,其中所有边都由复合体表示,并且复合体根据它们源自的超图进行分区。 对于情况,由于没有将复合体包含在复合体中,导致消除了(19)的第四行和第六行以及第四列和第六列,从而导致
(22) |
展开后一个行列式并代入张量 的显式形式(方程 (9)),我们得到
(23) | |||||
在前两个括号内,有每个超图层单独的贡献。 最后一项表示两个超图之间通过顶点的相互作用。 后者是多重超图的真正复杂性。 前两个括号内的项可以是正数,这意味着没有标准的超图渗透,并且 可能由于最后一个交互项而变为 0。
III.8数值示例
为了测试分析结果,我将使用具有多重结构的随机 chygraph 模型:一层 原子,两层具有 和 复合物的复合物将随机选择的原子包含到层、中随机选择的络合物中。 由于内含物是随机的,所以乳糜度和成分大小均具有平均值为 和 、 的泊松分布。 对于泊松分布,超额平均值与平均值一致,因此 和 、。 将这些值代入方程。 (23) 我们到达临界条件
(24) |
其中,。
为了测试这个表达式,我计算了巨大成分分数和不包括巨大成分的平均成分大小。 为此,我将 chygraph 投影到一个网络中,其中节点代表原子和复合物,而链接代表包含关系。 图2报告了巨型成分分数和平均成分尺寸的数值估计,作为的函数,使用方程1计算。 (24)。 在处存在相变,出现巨型组分以及排除巨型组分的平均组分尺寸的最大值。 该协议证明了多重 chygraph 分析结果的有效性。
事实证明,这个例子也是对层次包含的验证。 考虑另一个具有以下包含结构的随机 chygraph 模型:一层 原子、用 复合物标记为 1 的层以及随机选择的原子的 包含物进入第 1 层随机选择的复合体,以及标记为 2 的层,其中带有 复合体和 包含从第 1 层随机选择的复合体到第 2 层随机选择的复合体。 人们可以检查方程 1 中具有分层包含的 chygraph 的临界条件。 (21) 简化为等式: (24)。 此外,将 chygraph 投影到网络中,其中节点代表原子和复合物,而链接代表包含关系,我们获得与上述多重 chygraph 相同的网络。 请注意,此等式适用于 。 对于 来说,具有多重或分层包含结构的随机 chygraph 之间不存在等价性。 对于多路复用结构,网络投影有一层连接到 层。 对于分层包含,网络投影具有 有序层,仅在相邻层之间有链接。
IV渗流理论二:有层内包裹体
我们可以从它包含的复合体(从下面)或它包含的位置(从上面)得出参考复合体。 当没有层内连接时,索引对 足以区分我们如何到达参考复合体。 如果我们来自下面。 如果我们是从上面来的。 然而,当存在层内包含时,两个索引不足以指定我们如何得出案例 的复合体。 我们需要一个额外的索引。 在生成函数形式主义的背景下,这意味着当从原子或另一个复合体到达复合体时,我们需要两个分量大小的生成函数。 当从下面到达时,我将用 表示它们;当从上面到达时,我将用 表示它们。 有了这个区别,方程。 (3) 和 (4) 被重写为
(25) | |||||
(26) | |||||
其中 和
(27) |
(28) |
注意我隐含地假设乳糜度和复杂内超图分量是独立的。
我们可以应用矢量化技巧来变换方程: (29) 转化为标准线性方程组。 为此,我们需要应用矢量化技巧两次。 一次像之前一样对索引 进行,另一次对索引 进行。 在第一次矢量化之后(29) 可以重写为
(32) |
第二次向量化后为
(33) |
在哪里
(34) |
(35) |
最后,临界条件为
(36) |
IV.1
IV.2数值示例
测试方程。 (37) 我考虑一个随机 chygraph,其中包含一层 原子、一层 复合物、 内含物随机选择的原子进入随机选择的复合体,并且将随机选择的复合体包含到随机选择的复合体中。 该模型的可能实现如图1所示。
由于内含物是随机的,所以乳糜度和成分大小都具有平均值为 、、 和 的泊松分布。 对于泊松分布,超额平均值与平均值一致,因此 、、 和 。 将这些值代入方程。 (37) 我们得到
(38) |
其中 和 、。
V结论
总之,chygraph 是一种表示复杂系统的通用组合结构。 它们允许编码不同类型的结构异质性和层次结构。 关键成分是 chygraph 的分形性质:复合体由原子和其他复合体组成,并且它也可以是其他复合体的一部分。 我已经使用矢量化计算了 chygraphs 的组件大小统计数据。 未来的工作需要将这种形式主义扩展到其他问题。
参考
- Albert and Barabási (2002) R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
- Ghoshal et al. (2009) G. Ghoshal, V. Zlatić, G. Caldarelli, and M. E. J. Newman, Phys. Rev. E 79, 066118 (2009).
- Vazquez (2009) A. Vazquez, J. Stat. Mech.: Theory Exp. 2009, P07006 (2009).
- Coutinho et al. (2020) B. C. Coutinho, A.-K. Wu, H.-J. Zhou, and Y.-Y. Liu, Phys. Rev. Lett. 124, 248301 (2020).
- Civilini et al. (2021) A. Civilini, N. Anbarci, and V. Latora, Phys. Rev. Lett. 127, 268301 (2021).
- Sun and Bianconi (2021) H. Sun and G. Bianconi, Phys. Rev. E 104, 034306 (2021).
- Gómez et al. (2013) S. Gómez, A. Díaz-Guilera, J. Gómez-Gardeñes, C. J. Pérez-Vicente, Y. Moreno, and A. Arenas, Phys. Rev. Lett. 110, 028701 (2013).
- Petri and Barrat (2018) G. Petri and A. Barrat, Phys. Rev. Lett. 121, 228301 (2018).
- Courtney and Bianconi (2018) O. T. Courtney and G. Bianconi, Phys. Rev. E 97, 052303 (2018).
- Iacopini et al. (2019) I. Iacopini, G. Petri, A. Barrat, and V. Latora, Nature Comm. 10, 2485 (2019).
- Joslyn and Nowak (2017) C. Joslyn and K. Nowak, “Ubergraphs: A definition of a recursive hypergraph structure,” (2017), https://doi.org/10.48550/arXiv.1704.05547.
- Yadati et al. (2021) N. Yadati, D. R S, V. S, I. K M, and S. G, in Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume (Association for Computational Linguistics, Online, 2021) pp. 448–454.
- Baas (2019) N. A. Baas, Int. J. Gen. Syst. 48, 603 (2019).
- Newman (2001) M. E. J. Newman, Proc. Natl. Acad. Sci. USA 98, 404 (2001).
- Barabási et al. (2002) A. Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek, Physica A 311, 590 (2002).
- Redner (1998) S. Redner, Eur Phys J B 4, 131 (1998).
- Lehmann et al. (2003) S. Lehmann, B. Lautrup, and A. D. Jackson, Phys. Rev. E 68, 026113 (2003).
- Vasilyeva et al. (2021) E. Vasilyeva, A. Kozlov, K. Alfaro-Bittner, D. Musatov, A. M. Raigorodskii, M. Perc, and S. Boccaletti, Sci. Rep. 11, 5666 (2021).
- De Domenico et al. (2013) M. De Domenico, A. Solé-Ribalta, E. Cozzo, M. Kivelä, Y. Moreno, M. A. Porter, S. Gómez, and A. Arenas, Phys. Rev. X 3, 041022 (2013).
- Callaway et al. (2000) D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett. 85, 5468 (2000).
- Horn et al. (1994) R. Horn, R. Horn, and C. Johnson, Topics in Matrix Analysis (Cambridge University Press, New York, 1994).
- Molloy and Reed (1998) M. Molloy and B. Reed, Comb., Probab. Comp. 7, 295–305 (1998).
- Okabe and Sadahiro (1996) A. Okabe and Y. Sadahiro, Environment and Planning A: Economy and Space 28, 1533 (1996).