结合图元与随机游走以捕捉复杂网络拓扑

为何连接的形态重要

从社交媒体的好友关系到航线网络，再到细胞内的蛋白相互作用，许多系统都可以描述为由节点与连接构成的网络。一种常见的研究方法是释放“随机游走者”，让其在节点间跳动并统计哪些节点会一起被访问。这类方法支撑了从网页检索到推荐系统的众多工具。但在许多实际情形中，节点的角色不仅取决于它与谁相连，还取决于其邻居群体所形成的小尺度模式。本研究提出了一个看似简单但影响深远的问题：当今的随机游走方法真的看清了这些模式的全貌，还是只看到了模糊的轮廓？

观察网络的两种视角

作者比较了两种描述节点在网络中位置的方式。第一种熟悉的视角使用随机游走。想象把一个标记放在某个节点上，反复随机选择一个邻居并移动；通过统计在这些游走中节点对共同出现的频率，可以绘出哪些节点在网络中彼此接近。第二种较新的视角则关注网络的小构件，称为图元。这些是由三到四个节点组成的小子网络，能形成链、三角形或方形等形状。通过记录两节点在这些形状中共享特定位置的频率，作者不仅捕捉到节点是否相连，还揭示了它们如何共同参与局部模式。

更精细的角色地图

为将图元思想转化为实用工具，研究引入了“轨道邻接”。与仅仅计数两节点是否同时出现在某种小模式中不同，轨道邻接记录它们在该模式中扮演的精确角色：例如，一个节点是否位于三角形的中心，而另一个位于链的端点。团队还开发了一个快速算法 GRADCO，能够在数分钟内计算出这些计数，即便面对含数万节点的网络。这使得可以将轨道邻接信息输入现代机器学习方法，把每个节点视为低维空间中的一点，该空间反映其在网络中的结构性角色。

随机游走忽略了什么

借助这种更细致的描述，作者对随机游走进行了理论层面的解剖。他们展示了对于给定长度的游走（如两步或三步），只有某些小的连线模式会影响节点对共现的频率。许多其他图元模式在随机游走统计中根本不会出现。即便是在会出现的模式中，随机游走也总是把若干模式混合成单一的综合信号，其权重由游走长度决定，而非由具体任务的需求来设定。这意味着潜在有用的结构性线索可能被淹没或与不相关的信号混合，从而限制了基于随机游走的方法区分不同节点角色的能力。

在真实网络上的测试

随后，作者在来自社会、技术和生物领域的40个网络上对两种方法进行了测试。每个网络中的节点带有标签，例如用户兴趣、机场活动类型、学科领域或生物功能。目标是仅从网络结构预测这些标签。在大多数数据集中，由轨道邻接构建的表示要么与基于随机游走的方法（包括 LINE 和 DeepWalk 等流行方法）相当，要么表现更好。值得注意的是，即使轨道邻接仅考虑最多四个节点的非常小的模式，它也能表现良好，而随机游走需要在网络中走得更远才能获取信息。这表明谨慎捕捉并区分局部连线模式，往往比单纯扩展观察范围更有价值。

对未来网络工具的意义

通俗地说，这项工作表明当前的随机游走工具以宏观笔触观察网络：它们能识别哪些节点倾向于彼此靠近，但无法精确地看清它们如何共享局部结构。轨道邻接则像一只更高分辨率的透镜，揭示哪些节点对在三角形、链以及其他基本形状中扮演类似角色。由于许多实际系统将结构与功能相联系，这种更清晰的结构视角能更好地预测节点在网络中的职能。因此，研究主张在关注复杂网络的细节接线时，分析者应超越随机游走，而基于轨道的描述提供了一种强大且可解释的替代路径。

引用: Windels, S.F.L., Malod-Dognin, N. & Pržulj, N. Combining graphlets and random walks for capturing complex network topology. Sci Rep 16, 14902 (2026). https://doi.org/10.1038/s41598-026-44410-x

关键词: 网络拓扑, 随机游走, 图元, 网络嵌入, 节点分类