多层网络、时间网络与超图

“一对节点、一条边、一张图”的表示在三种情形下不够用：同一组节点之间有多种关系，关系随时间变化，或相互作用发生在多于两个节点之间。

多层网络

设共有 $N$ 个节点、$T$ 层，第 $\alpha$ 层的邻接矩阵为 $A^{(\alpha)}$，层间耦合强度为 $\omega$。多重网络可以写成一个 $NT\times NT$ 的超邻接矩阵（supra-adjacency matrix）：

$$\mathcal A=\begin{pmatrix} A^{(1)} & \omega I & \cdots & \omega I\\ \omega I & A^{(2)} & \cdots & \omega I\\ \vdots & & \ddots & \vdots\\ \omega I & \omega I & \cdots & A^{(T)} \end{pmatrix},$$

对角块是层内连接，非对角块是层间连接。若层有自然顺序（如时间窗），通常只连接相邻层，非对角块只出现在紧邻对角线的位置。超邻接矩阵让很多单层方法（随机游走、谱分析、模块度）可以直接推广到多层网络。

生物医学中的多层结构：

• 线虫神经系统：化学突触层（有向）与电突触层（无向）共享同一组 302 个神经元；
• 多模态脑网络：结构连接层与功能连接层；
• 时间窗功能网络：每个时间窗一层，多层模块度与“灵活性”见动态功能连接与多层脑网络；
• 多组学网络：同一组基因的 PPI 层、共表达层、调控层。

把多层网络简单地把各层相加成一张加权图（聚合，aggregation），会丢掉“哪种关系”这一信息，有时还会造成错误结论：两个节点在每层都只有一条弱边，聚合后可能看起来连接很强。

时间网络

时间网络（temporal network）中每条边带有时间戳或持续时间，例如医院病房中两人的接触记录 $(i,j,t)$。表示方式有两种：接触序列（事件列表 $(i,j,t,\Delta t)$）和快照序列（按时间窗聚合成一串邻接矩阵 $A(t)$）。时间网络中的路径必须按时间先后前进：$a$ 在 9 点接触 $b$、$b$ 在 8 点接触 $c$，病原体不能经 $b$ 从 $a$ 传到 $c$，尽管在聚合图上存在路径 $a$–$b$–$c$。因此聚合图会高估可达性和传播速度（Holme 与 Saramäki，2012）。

超图

多体相互作用在生物学中很常见：蛋白质复合物由多个亚基共同组成，一个生化反应有多个底物和产物，一次处方同时包含多种药物，多个脑区在同一时刻共同激活。超图有三种常见的降维表示，各有代价：

关联矩阵与二分图的双邻接矩阵是同一个对象：$H$ 就是“节点–超边”二分图的 $B$。所以超图在计算上总可以先存成二分图（超邻接矩阵与团展开信息丢失的演示见代码示例）。Klamt 等（2009）系统讨论了用超图表示代谢反应和信号网络的必要性：例如反应 $A+B\to C$ 只有在 $A$ 和 $B$ 同时存在时才发生，普通有向图 $A\to C$、$B\to C$ 无法表达这种“与”关系。高阶相互作用的结构与动力学见 Battiston 等（2020）的综述。