Reticula: A temporal network and hypergraph analysis software package
Reticula：时空网络和超图分析软件包
https://www.sciencedirect.com/science/article/pii/S2352711022002199
摘要
1. 动机
许多有趣的物理系统由大量具有不同内部复杂性的相互作用实体组成。例如，社交网络由个体组成，他们通过物理或电子方式相互交换信息[2]。同样，像人脑这样的生物系统可以被视为其细胞及其连接的集合[3,4]。这些复杂系统的许多新兴行为可以通过将系统建模为图形来复制和分析。这催生了复杂网络领域，其中这种方法被应用于增加我们对大量互联系统现象的理解。例如，人们注意到许多系统显示出顶点之间的同步模式[5,6]，并且在完全不同的背景下的传播过程，如信息或疾病在人群中的传播[7,8]或公共交通系统的可访问性[9]，可以显示出在统计物理中已经广泛研究的相变。
将现实世界系统作为具有顶点之间二元关系的静态网络（图）的兴趣不断增加，推动了一系列软件库的发展，旨在填补计算空白，如NetworkX[10]、igraph[11]和斯坦福网络分析项目(SNAP)[12]。这些库在API易用性、性能和通用性之间取得了不同的折衷。
然而，许多现实世界的系统由连接和实体组成，它们在比观察期短或可比的时间段内发展变化。社交圈随着新的人际连接的形成而随时间演变。生物系统中的细胞死亡或改变它们与其他细胞连接的性质和强度。此外，时间决定了连接性的固有方向：与图形不同，实体之间的互动只有在时间上合理的情况下才是可传递的。时间网络[13,14]旨在提供一种复杂系统的表示，其中包括实体之间的互动时间，与静态网络边缘通常代表的相反，即实体之间互动的可能性或合理性。这组时间标记的互动（也称为时间边缘或事件）自然捕捉了系统随时间的演变以及可能在静态设置中被忽视的所有可能的时间异质性和相关性，这些因素影响动态过程[8]。
时间网络作为模型的普及和概念简单性带来了另一组软件库，如Raphtory，一个分布式时间网络分析库[15]，PathPy更专注于时间路径和路径统计[16]，以及Phasik，专注于推断网络中的时间阶段[17]。
另一方面，许多系统最好使用不受两个实体限制的互动或事件来描述。例如，在人群中面对面或在线互动通常发生在大于两个的群体中，科学文献的互动以引用的形式实际上是被引用论文的作者群体和引用论文的作者群体之间的互动。已经出现了专门处理超图的库，例如，Julia的SimpleHypergraphs.jl[18]和HyperGraphs.jl[19]，以及Python包HyperNetX[20]和Complex Group Interactions (XGI)[21]，旨在分析高阶互动。
Reticula是一个C++库及其配套的Python绑定，它本地支持广泛的复杂网络类型，包括静态和时间网络的有向和无向变体、超图和超图时间网络。此外，它还支持时间网络和超图时间网络的延迟事件，允许用户建模例如涉及延迟的交通网络或其他时间网络。该库还支持不同类型网络的合成生成和随机化方法、读写网络文件、计算网络的各种属性，以及与NetworkX进行静态二元网络类型的互操作。
2.影响
Reticula Python接口与纯Python库相比，在速度上有显著提升。例如，使用random_degree_sequence_graph函数生成一个大小为1000、度序列为(4, ..., 4)的单个随机图，在Reticula中的速度大约是NetworkX的18倍。同时允许使用24个CPU核心并行生成1000个这样的图，这个比例提高到了250倍。同样地，生成一个大小为16000、期望顶点度序列为(6, ..., 6)和期望边度序列为(3, ..., 3)的单个随机期望度超图，在Reticula中的速度大约是XGI的3.8倍。
这个软件的早期版本已经支持了各种研究工作。参考文献[22]使用它来估计大型现实世界时间网络的受限可达性，而参考文献[23]将相同的方法应用于各种随机时间网络模型，以展示有限等待时间邻接在许多时间网络中具有有向渗透可达性相变。此外，参考文献[24]在实现网络上的隔室模型动态时使用了该库，以预测度异质性、同质性和接触追踪应用程序适应性程度对它们作为预防措施的效果的影响。
3. 设计目标和软件描述
软件包接口旨在优化以下目标：(1)提供一个易于使用、人类可读的函数接口，通常类似于NetworkX，可以统一用于所有支持的网络类型，(2)通过安全的多线程，特别是在Python中，使其在高性能计算环境中易于有效使用，(3)尽可能优化实现算法中的CPU缓存命中率。
虽然从理论复杂性的角度来看，常用的哈希表嵌套哈希表表示图在检查两个顶点之间边的存在性时提供了恒定时间复杂度，但这种方法在许多需要循环遍历某个顶点的所有相邻边的图算法中导致了次优的内存访问模式。这种表示方式也不能直接扩展到时间网络和超图。
相反，Reticula将每个网络顶点的相邻边集合存储在内存的连续区域内，作为一个排序的向量。相邻边的连续存储允许处理器最优地利用其多层缓存系统，避免访问主系统内存的慢速和高成本。这种结构可以不加修改地扩展到超图。此外，它可以通过为每个顶点存储单独的入边和出边向量来支持有向网络。通过按时间排序的相邻边的时序向量，可以包含对时间网络和超图时间网络的支持。
为了让这个库在大量多线程环境中更容易使用，而不必使用显式的同步原语，该库主要呈现不可变边和网络类型，并提供了一系列用于操作网络的函数，这些函数返回修改后的副本，而不是直接修改对象本身。这消除了风险，例如，无意中修改了另一个线程同时正在读取的网络，这可能会返回错误的结果，没有明显的错误，甚至可能导致未定义的行为。这一点，加上C++库在大多数部分不直接操作任何Python对象的事实，允许我们在Python接口的入口点安全地释放全局解释器锁(GIL)，允许直接从Python代码进行多线程计算。
该库目前支持表示各种类型的静态和时间网络，具有有向或无向连接，无论是仅限于二元连接还是涉及任意数量顶点的超边。此外，该库允许用户构建高阶网络，其中顶点本身是较简单网络的边，对于C++库可以任意阶，对于Python库可以到第二阶。Python绑定还支持整数、字符串和2元组顶点，而在C++中，模板类型允许任何定义了强排序和某些实用函数的顶点类型，默认包括所有数值类型、字符串和所有有序容器。新的网络类型可以通过在C++中定义自定义边类型及其相应的类型特征轻松实现。
C++库可以直接编译并安装在目标系统上，或者更可取地使用FetchContent CMake模块直接包含在项目中。使用PyBind11 [1]实现的Python绑定可以从Python包索引中使用控制台命令`python -m pip install -U reticula`安装在任何具有GNU C库(glibc)版本2.17或更新的64位Linux操作系统上（即，与平台标签manylinux2014兼容）和Python版本3.8或更新。两个库提供类似的接口和类型集。尽管C++库提供了需求和概念，使研究人员能够轻松实现自定义功能，例如新的边类型或可以从已实现算法中受益的网络类型，但Python原生扩展接口的预编译要求使得这种即时可扩展性不可行。
核心库经过广泛且自动化的测试。测试用例实现在C++库源代码树的`src/tests/reticula/`目录中。代码库大量使用许多现代C++特性，如概念和范围，这些与其他最佳实践（如严格的const正确性）一起，通过库作者或最终用户提供一定程度的保证，防止一些容易出错的常见模式，但需要一个具有对C++ 20标准(ISO/IEC 14882:2020 [25])子集的体面支持的最近的编译器套件（不包括协程、模块和标准中的字符串格式化部分）。对于当前版本，该库已在GNU编译器集合版本10.2及更新版本上进行了测试并确认可以编译。软件的安装和使用有广泛的文档支持，可在线访问 https://docs.reticula.network/ 和在Python绑定源代码树的`docs/`目录中找到。
4. 实现的功能
该库允许从边列表文件或事件列表文件输入和输出网络。也可以将静态二元网络导入和导出到NetworkX。例如，这可以用来通过网络尚未实现的方法创建静态网络，或者读取和写入其他文件格式。
Reticula还可用于生成各种合成和随机的静态和时间网络，如规则环晶格、d维正方形晶格、G(n, p)[26]、Barabási-Albert[27]、k-规则、（有向或无向）度序列[28]和（有向或无向）期望度序列随机图[29,30]，以及具有任何静态“基础”和指数、几何、自激励和幂律事件时间分布的完全混合和激活模型时间网络[23]。也可以从一个（可能是现实世界的）时间网络开始，使用库中实现的各种微观正则化参考模型来随机化某些特征[31]。
虽然该库主要侧重于网络的传播、连通性和可达性分析，但它实现了其他一些可能作为其他算法或网络测量构建块的众所周知的网络算法。例如，该库允许用户检查度（对）序列是否是（二）图[32,33]，并检查有向（超）图是否是无环的，并找到有向无环图的拓扑排序。用户可以计算有向或无向二元静态网络的密度。对于时间网络，用户可以构建网络的静态投影：如果时间网络中至少有一个事件，则连接两个顶点的有向或无向静态网络。他们还可以计算与每个静态投影链接相对应的所有时间事件的时间线。
在可达性和连通性方面，该库提供了广泛的功能。对于静态网络，用户可以计算（弱）连通性和（弱）连通分量，查询一个顶点是否可从另一个顶点到达，并计算所有入和出分量以及到任何顶点的最短路径长度。还可以使用概率计数方法估计有向网络的入或出分量大小，在单次传递中以O(|E| log |E|)时间完成，对于无环图的常见情况[34]。
同样，对于时间网络，可以计算事件图表示[35]，并在O(|E|)时间内从指定时间的单个顶点开始计算时间可达性簇，或者在O(|E| log |E|)时间内单次传递估计所有顶点在所有可能的开始时间的时间可达性簇[34]。生成的时间簇包括可达性信息，以及特征量，如簇质量、体积和寿命[22,23]。
时间网络可达性簇计算可以使用许多最常用的时间邻接定义进行。简单邻接描述了可达性的上限，大致类似于易感者 → 感染者（SI）过程，其中对效应可能在顶点中保持多长时间没有限制。指数和离散时间变体几何时间邻接，大致让人联想到易感者 → 感染者 → 易感者（SIS）过程，允许顶点保持受影响的持续时间，通过给定速率的指数分布确定。有限等待时间使用确定性最大时间截止而不是概率分布。此外，C++库允许定义新型时间网络邻接类型，然后可以由C++库函数使用。
该库的未来路线图重点是集成最初为参考文献[24]实现的静态和时间网络的通用隔室模型框架，为x64和ARMv8 macOS和Windows设备提供预编译的Python包，并实现额外的网络统计和算法。
说明性示例
5.1. 静态网络中的各向同性渗透 在这个第一个示例中，我们将专注于静态网络的分析。这使我们能够比较和对比该库与其他网络库的接口和性能。这个示例生成了一系列G(n, p)随机网络，并绘制了最大连通分量大小作为p的函数，突出了巨成分的出现。
正如之前所讨论的，该库的公共函数接口非常简单，正如上面示例中所见，例如，在调用函数 ret.largest_connected_component 时，该函数接收一个无向网络作为输入，并按顶点数量返回其最大的连通分量。另一方面，G(n, p) 随机图模型的实现 ret.random_gnp_graph[ret.int64]() 需要提供顶点的数据类型信息，这在方括号中给出。这与 numpy 数组的 dtype 参数有类似的作用：
python
a = np.array([1, 2, 3], dtype=np.int64)
该示例使用Chung-Lu算法的推广到二分网络[37]来生成一个静态超图，对于大值的n，期望的顶点度为p(n−1)，边度为4。这创建了一个图表，在处显示临界阈值，如图1(b)所示。
5.2. 时间网络事件时间非均匀性和可达性
在这个例子中，我们从一个随机的G(n, p)静态网络和自激励过程激活时间生成一个时间网络，使用实现的微观正则化参考模型之一来洗牌事件时间之间的相关性，并比较可达性的变化。
这个示例生成了来自随机G(n, p)静态网络和Hawkes单变量指数自激励激活时间的ens = 100个随机时间网络。对于每个随机网络，它计算了平均时间外簇质量。然后，使用时间线洗牌方法[31]对时间网络进行随机化，以消除连续事件时间之间的相关性（即自激励），并重新计算平均时间外簇质量。在这个示例中，我们使用了时间邻接的指数模型，这意味着组件质量概念上类似于在SIS模型中感染的总人工小时，其中从感染状态恢复到易感状态的过程由具有速率参数的指数时间控制，在本例中设置为1.0。
通过在t = 0时计算每个顶点的出簇（在函数out_cluster_mass_at_t0中）并平均组件质量来计算平均时间外簇质量。如果使用概率计数方法来估计所有可能的出簇，可以更快地进行并拥有更大的样本大小，但必须注意在这个示例中事件时间不是均匀分布的。
运行示例产生了以下结果：
具有自激励事件时间的平均质量：2164.3724129038064
时间线洗牌随机化后的平均质量：5539.766618496214
可以这样解释：使用所提供的参数生成的随机时间网络的自激励属性被洗牌后，显著增加了时间网络的平均可达性。尽管需要更强的分析方法来适当地研究这样的假设，例如确立平均质量差异的显著性，或在经验网络和更广泛的合成网络上确认这一点，所有这些都超出了这个示例的范围。
请注意，时间网络不会复制到每个线程，而是在任何给定时间点在内存中只有一个时间网络实例。在Reticula中，使用跨线程的共享内存中的网络类型是安全的，因为不可能在一个线程中修改网络，而在另一个线程中读取网络。在这个示例中，用户可以确定，无需查看文档或实现，函数ret.out_cluster或任何其他以网络为输入的函数不会修改参数。这减少了意外数据竞争的风险，并且是由于Reticula中的网络类型是不可变的。这一点在表1中展示的其他库中并不保证，这使得对于igraph和SNAP网络类型，这两个作为原生扩展实现并支持多线程处理的网络库，很难推理可能的数据竞争。
这将得到以下函数ret.random_link_activation_temporal_network，它生成一个超图时间网络而不是二元时间网络。这展示了相同的API - 在这些说明性示例中，生成边激活网络或计算静态网络的时间簇或最大连通分量 - 可以在不同的网络类型上操作，只要这些操作对于给定的网络类型是明确定义的。
结论
Reticula是一个原生处理有向和无向静态网络、时间网络、超图和时间超图的软件库，提供统一的编程接口，支持Python或C++。该库优化了CPU缓存的使用，并提供线程安全类型和操作，使其适用于高性能计算环境中的多线程设置以及现代高核心数CPU。Reticula使科学家能够研究非常大的网络数据集的属性，构建和比较参考模型和随机网络，以及将网络读写到磁盘。
