【High 翻天】Higer-order Networks with Battiston Federico （1）

前言

Ginestra Bianconi 的一篇综述¹和一本书²展开的故事。

书还没有开始看，先看看综述吧。综述提供了一个关于超越成对交互的网络新兴领域的概述。

• 讨论了高阶网络的表示，主要是其中相互作用的表示，并强调了现有概念和其联系。
• 回顾了用来描述高阶系统结构的测量方法，以及可用于生成合成结构的模型。
• 介绍了快速发展的高阶动力系统和动态拓扑的相关研究，讨论了高阶相互作用与集体行为之间的关系。
• 特别关注了具有动态过程特征的新涌现扩展到成对交互之外时的现象，如扩散、同步、传播、社会动态和游戏。

高阶网络的表示

首先，给出高阶的概念。通常来讲，将包含 $k$ 个节点的相互作用的阶（order）表示为 $k-1$。例如：一个节点处的环记为0-阶，两个节点的相互作用是1-阶，三个节点的是2-阶，等等。当 $k\ge 2$ 时就是所谓的高阶。由于此时的定义与维度类似（dimension），有些文献也会说是高维。显而易见，低阶系统是那些只发生自我或成对交互作用的系统，而高阶系统在两个以上元素的组中显示交互作用。

至于为什么需要讨论高阶系统呢？作者给出理由如下：

The distinction between low- and high-order interactions is needed for two reasons. First, it highlights the differences between the graph-theoretic descriptions, that shaped the study of complex systems in recent decades, and the more recently (re)proposed descriptions based on genuine group interactions. Secondly, it allows us to clearly frame the connections between such descriptions, their various overlaps and reciprocal mappings. Finally, our definition explicitly leaves out other types of higher-order dependencies between the components of a system, as for example those defined by multiple link types in multilayer networks, or by non-Markovian paths in time-stamped interaction data.

在我的认知中，本质就是由于多层网络的兴起带来的问题。

高阶相互作用的初等表示

定义一个交互系统 $(V,\mathcal{I})$ 定义为节点集 $V$ 及其节点之间的交互族 I = { I 0 , ⋯ , I n } \mathcal{I} = \{I_{0}, \cdots, I_{n}\} I={I0​,⋯,In​} 。如下图所示，给一个交互系统的例子，其中 V = { a , b , c , d , e } V = \{a, b, c, d, e\} V={a,b,c,d,e}， I = { [ a , b , c ] , [ a , d ] , [ d , c ] , [ c , e ] } \mathcal{I} = \{[a, b, c], [a, d], [d, c], [c, e]\} I={[a,b,c],[a,d],[d,c],[c,e]}。显然 $\mathcal{I}$ 包括三个1-order 交互和一个 2-order 交互。很自然地， $\mathcal{I}$ 可由1-order 交互组成的基来表示。换句话说，$\mathcal{I}$ 可以映射为 I G = { [ a , b ] , [ a , c ] , [ a , d ] , [ b , c ] , [ d , c ] , [ c , e ] } \mathcal{I}_{G} = \{[a, b], [a, c], [a, d], [b, c], [d, c], [c, e]\} IG​={[a,b],[a,c],[a,d],[b,c],[d,c],[c,e]}，这样的话，传统图表示工具仍可使用。

与此同时，高维映射到低维的逆问题，即低维求解后如何重构高维，是一个艰难的问题。

Hypergraphs provide the most general and unconstrained description of higher-order interactions.

超图（Hypergraphs）包含顶点集 $V$ 和指定在交互中哪些节点以何种方式参与的超边 $H$。如上图中的（L）部分所示，超图是高阶交互系统的最好展现方式。

表示之间的关系

当讨论同一个交互系统的不同表示形式时，会出现关于联系与转换的问题。接下来，以 simplicial complexes 的两种表示（the Hasse diagram 和 the facet representation）为例，如下图所示。

总结

虽然提出了很多新的概念，但是底层逻辑是清晰的。事实上，将高维用合适的形式表示并不是难点，难点往往在于模型的通用性和统一性。