研究背景
现实中存在大量的复杂系统，其个体或元素之间的交互往往是非线性的，结构通常存在很强的耦合性和异质性，如人类社会、互联网和人类大脑等[1]。对复杂系统的建模和研究吸引了来自不同领域学者的关注，其中，复杂网络被认为是一个用于对复杂系统的结构进行建模并研究其动力学特征的合适工具[2]，相关的研究在控制理论、疾病传播等多个领域中有广泛的应用。一般网络通常用节点和连边来代表复杂系统中的元素和元素之间的关系，然而，从人类社交到化学反应，在人类和自然复杂系统中普遍存在涉及多体的高阶交互，这种以群体形式存在的高阶交互难以用一对一的连边来描述[3-5]。同时，有大量的研究表明，将高阶结构纳入考量能够帮助我们更好地建模和理解复杂系统中的动力学行为[6]。在这些研究中，超图可以用来直观和自然地表征上述高阶结构[7]，超图相关的研究也成为网络科学的一个热门研究领域。
复杂网络的结构通常存在很强的异质性，网络中的小部分节点具有不成比例的影响力和重要性，能够对整个网络带来重要的影响[8]。节点的这种性质可以由节点的中心性来量化，而通过对复杂网络中的节点按照重要性程度进行排名，进而实现复杂网络中关键节点识别的问题，被称为中心性问题，用于节点排名的算法被称为中心性算法。中心性问题是复杂网络研究中的一项重要研究内容，其研究能够有效挖掘复杂系统中的重要信息、揭示寻找关键节点的规律，对谣言制止、传染病控制和广告营销等现实问题而言具有重要的应用意义。
本文基于真实数据对复杂系统中的高阶结构进行研究，着眼于解决超图上的中心性问题。从真实数据出发，分析高阶结构在中心性问题中的地位和作用，对于帮助我们理解复杂网络中高阶结构的特征，更好地挖掘关键节点而言具有重大意义。同时，尽管已有一些学者将一般网络上的中心性算法推广到超图上，但是大多数研究并没有从高阶的角度对算法识别关键节点的效果进行验证，目前也缺乏一套适合于高阶网络的验证方法对算法效果进行检验和分析。因此，从高阶作用的角度提出一套超图上中心性算法的验证方法，这是本文的另一个目标。最后，本文从真实数据中的高阶结构出发，提出了两种超图上的中心性算法，HGC和LHGC；从传播动力学和网络连通性两个角度定义了两种适用于超图的中心性算法的验证指标；在多个真实网络上对比了HGC、LHGC和其他对比算法的效果。实验结果表明，所提出的方法考虑了高阶信息，能够更好地识别关键节点，尤其是在高阶距离较大网络，基于局部拓扑的指标（如度）会失去准确性，加入对高阶距离的考量可以更好地识别关键节点。
方法
1. 复杂系统中的高阶结构
本文从真实数据中构建了8个真实超图，分析了高阶距离在超图中的分布情况（图1）。在图1中，横坐标为s-距离，纵坐标为s-距离在超图中所占的比例，散点的颜色代表s的取值。这里的s代表超边之间的交集，s的取值越大，说明超边之间的共同节点越多，耦合关系更深，超边之间的高阶交互更加明显，而s取值为1，则等价于一般网络中的距离。我们发现，在不同的数据集中，超边交集的最大值从9 (iAF1260b) 到58 (Geometry) 不等，这说明高阶距离在超图中广泛存在；在不同的数据集中，s-距离的分布形状相似，接近幂律分布，说明在超图中，耦合很深的路径占少数，但是由于交集很大，它们可能是传播中的关键路径。以上分析表明，在识别关键节点时，有必要将超图中的高阶信息纳入考量，并且对更高阶的信息基于更大的权重。
图1 高阶距离（s-distance）在不同超图上的分布。横坐标为s-距离，纵坐标为s-距离在超图中所占的比例，散点的颜色代表s的取值。
2. 中心性算法
根据上述对超图中高阶结构的分析，本文基于引力模型提出了两种中心性算法来挖掘超图中的关键节点。著名的万有引力模型旨在描述物体之间的引力正相关于它们之间的质量，负相关于它们之间的距离的规律。受这一物理规律的启发，大量的研究将引力模型引入中心性问题中，用其来刻画节点之间的吸引力。其基本思想是，节点之间的吸引力受他们质量（例如度，k-shell值）的影响，并且这种吸引力随着节点之间的距离增大而削弱。吸引力大的节点往往意味着更高的影响力。过去已有许多研究验证了引力模型在一般网络上识别关键节点的效果[9-11]，在本文中，我们利用节点的局部特征（度）和超图的全局特征（高阶距离），基于引力模型提出了两种中心性算法，HGC和LHGC。为了考虑超图中的高阶结构，我们引入了一个惩罚项，对耦合更深，s值较大的节点间距离给予更大的权重，以此来筛选关键节点。
3. 基于高阶交互的验证方法
(1) 超图上的简单传播与复杂传播
在现实中，通过二元连边发生的传播较为常见，例如疾病传播、信息扩散，这类传播通常被称为简单传播。但是，二元关系并不能完整地描述传播过程，因为在同侪压力或舆论氛围的影响下，存在许多来自集体对传播的影响，我们将这类传播称为复杂传播。实际上，理解群体是研究个体行为的一个重要方面，每个人都是社会的人，都受到其所属的各种集体的影响，而大多数的决定或成果又都是团队合作的成果。为了刻画超图上的复杂传播，我们在经典的SIR传播中引入了一个传播阈值 ，它代表了群体对个体的影响程度，只有当群体中受到感染的个体的比例超过阈值 ，群体中的个体才会在群体之外进行传播。当 取值为0，此时的SIR传播等价于原本的经典模型。我们以单个节点为初始感染节点，并在真实超图上进行传播模拟，最终实现的传播规模大的节点的影响力被认为是高的。
图2 考虑传播阈值的SIR传播示意图。红色、蓝色和绿色节点分别为感染节点、移除节点和易感节点。在每一个时间步，感染节点以 的概率感染其易感邻居，同时以 的概率恢复为移除节点。当超边内感染过的节点的比例超过 时，感染节点会向超边外传播。
(2) 超图上的高阶效率
传播模型可以从动力学的角度验证节点的重要性，而网络效率可以从网络的结构和功能室上反映节点的重要程度。具体来说，网络效率是刻画网络信息流通效率的指标，网络中节点之间的距离越小，沟通效率越高。本文中，我们将超图上的高阶距离纳入考量，重新定义了一种高阶效率，通过攻击节点，并计算被攻击前后高阶效率的变化，得以验证中心性算法在超图上识别重要节点的效果。
4. 算法效果
(1) 节点传播能力验证
为了量化节点的传播影响力，我们在超图上进行传播模拟。在图3中，我们展示了排名前10%的节点在传播早期的传播曲线。从中，我们发现HGC和LHGC在大多数超图上的传播效果为最优或接近最优。对于ECC和HCC，我们取其s的取值为1，这使得它们等价于一般网络上的方法，而ECC在HCC在传播中的表现并没有优于其他算法，这说明考虑超图中的高阶结构是有必要的。同时，对于一些基于超边中心性的算法（如HEDC，ECC，HCC和VC），我们将超边的中心性分数均分到其包含的节点上，从而得到节点的中心性分数。而这些方法的表现同样不稳定，这说明在超边内部，节点的贡献可能不是均质的。这也符合我们的常识，也即团队成果的贡献大多数来自少数的重要节点。
图3 排名前10%节点在不同超图上的传播曲线。横坐标为传播时间步，纵坐标为被感染过的节点的比例。
对于DC，我们发现，它和我们提出的方法之间存在较高的相关性，它们之间的传播曲线也都较为接近，这是由数据集的高阶距离较小所导致的（如超图email-Enron），而在高阶距离较大的超图上，我们提出的方法则由于DC（如超图NDC-classes）。这说明，在高阶距离较大的超图上，考虑高阶距离有助于识别关键节点，本文所提出的方法也会有更好的效果。为了验证这一点，我们利用HpyperCL这一超图生成模型，生成了一系列规模不同、超边数 (M) 和节点数 (N) 比值不同的超图，并在这些超图上进行了传播模拟。从图4中，我们发现，随着M/N比值的增大，所提出的算法和传播影响力最大的节点之间的差距越来越大。这说明在M/N比值小的网络上，所提出的方法有更好的效果,而更少的超边则意味着网络高阶距离较大。
图4 所提出算法在合成网络上算法效果的变化。横坐标为超边数和节点数的比值， 为HGC和传播影响力最高的10%节点之间的AUC差距。
(2) 网络高阶效率验证
在这一部分实验中，本文首先删除p比例的重要节点，然后计算网络效率的变化。在图5中，我们发现，所提出的方法在大多数超图中都有较好的表现，说明HGC和LHGC能够较好地识别对保持网络沟通效率和网络功能而言重要的节点，也从另一个方面说明了在中心性问题中考虑高阶结构的重要性。同时，我们还发现，在攻击重要节点时，DC的效果并不如本文所提出的方法，这意味着在高阶网络上，仅仅攻击超级传播者可能不能达到拆解网络的目的，从而不能很好地解决网络拆解和传染病抑制等问题。
图5 超图高阶效率在攻击重要节点后的而变化。横坐标为攻击的重要节点的比例，纵坐标为高阶效率的变化值。
总结
在这项工作中，我们基于引力模型提出了两个超图上的中心性方法，这两个方法同时利用了超图上的局部信息和全局信息，并且考虑了超图上的高阶结构。为了验证中心性算法在超图上识别关键节点的能力，我们基于超图中的高阶相互作用和高阶结构提出了两个验证方法，分别从网络传播动力学和网络静态结构两个角度去进行实验。实验结果表明，所提出的方法识别出的关键节点具有较高的传播影响力，并且对提高网络的沟通效率而言具有重要作用。特别地，我们还发现，所提出的方法在高阶距离较大的超图上可以有更好的效果。
论文网址：
https://aip.scitation.org/doi/10.1063/5.0127434.
- THE END -
图文来自复杂系统与社会计算公众号
转自：“再建巴别塔”微信公众号
如有侵权，请联系本站删除！
