距离骨干合成（DBS）优化复杂网络稀疏化中的传播动力学与中心性排名

《PLOS Complex Systems》：Distance backbones optimize spreading dynamics and centrality ranks in the sparsification of complex networks

　　

社会、生物及其他复杂系统的精细网络模型通常较为稠密，这增加了模拟与分析中的计算复杂度。为应对该计算挑战，图稀疏化（graph sparsification）被用于在保留所需网络属性的同时移除边。例如，加权图（weighted graphs）的距离骨干（distance backbones）是极其稀疏的图，能够保留社区结构（community structure）和传播动力学（spreading dynamics）。此类骨干省略了原始图中对于任意给定路径长度度量（path-length measure）会破坏广义三角不等式（generalized triangle inequality）的边，并保留加权图的所有最短路径。它们也最能保留节点中心性排名（node centrality ranks），以及传播现象中的局部和全局动力学。研究人员通过引入距离骨干合成（DBS）发现了骨干的这种优越性能；DBS根据一族一般的嵌套距离骨干逐步稀疏化加权图，其中每条边与包含它的最小距离骨干相关联。DBS提供了一种有原则且自然的方法，在保持连通性的同时覆盖所有可能的稀疏化等级，从而能够在多目标准则下精确研究（有向和无向）加权图稀疏化。它通过揭示与每条边相关的精确拓扑空间，为边重要性提供了代数上有原则的解释。该理论通过一组来自不同场景真实社会活动的社会接触网络（social contact networks）进行了演示。该研究还表明，节点中心性和传播动力学的最优保留发生在满足路径长度度量广义三角不等式的距离骨干上，该骨干从所研究的经验网络中移除了超过一半的边。

社会、生物等复杂系统的网络分析常用于揭示中心组件、社区等复杂模式，但更详细的系统描述会产生更多节点和边，带来计算资源与理论可解释性挑战，因此需要能够保留系统网络表示中关注特征的子图稀疏化方法。现有方法各有局限：权重阈值（W）移除弱边常导致网络不连通，且弱边可能在结构与动力学中起关键作用；差异过滤（DispFilt）依赖零模型而存在偏倚；加权有效电阻（wEffRes）需计算或近似拉普拉斯矩阵伪逆；高显著性骨架、基于omega的连边移除和半度量失真稀疏化（SmD）等多依赖网络特定阈值参数；度量骨干（metric backbone）删除破坏三角不等式的边，是精确、代数上可解释且可扩展的稀疏化方法，超度量骨干（ultrametric backbone）则为所有最小生成森林的并集。基于此，研究人员引入距离骨干合成（DBS；通过参数化三角距离范数族对加权图进行渐进稀疏化的方法），按边所属的最小距离骨干排序，系统覆盖从最小骨干到原图的稀疏化等级，并在经验社会接触网络上评估其保留特征向量中心性（eigenvector centrality；按连接数量与质量衡量节点重要性）排名和SI模型（Susceptible-Infected，易感-感染）传播动力学的性能。研究表明，基于最短路径冗余的DBS与SmD在保留中心性排名和传播动力学方面总体优于W、DispFilt和wEffRes；总体最优骨干位于乘积骨干（product backbone）与度量骨干之间，移除超过一半连接同时保留超过80%的性能指标。其意义在于为边重要性提供拓扑空间解释，并给出可精确、可扩展且保持连通性的网络稀疏化框架。

关键技术方法（不超过250字）：研究人员使用公开可得的12个经验社会接触网络，来自不同真实社会活动场景，由RFID/Bluetooth设备约20秒间隔记录近距接触并构建交互强度，再将邻近度经连续严格递减映射转为交互距离。比较DBS与W、DispFilt、wEffRes和SmD。以特征向量中心性Spearman秩相关评估中心性排名，以SI模型进行基于智能体的传播模拟（15%节点为种子，每个种子100次），用平均感染顺序秩相关和半感染时间t_0.5评估微观与宏观动力学，并以曲线下面积（AUC）汇总至稀疏化上限；最后以加权目标函数优化DBS参数。

研究结果如下。3.1 建立距离骨干合成：研究人员通过引入DBS并参数化三角距离范数（td-norm；定义路径长度计算方式的二元运算）族，证明不同骨干嵌套，每条边存在首个最小合成参数，从而诱导边排序并覆盖所有最短路径拓扑空间；Dombi族中的g₁(x,y)=x+y推广传统最短路径和pathfinder网络。经验网络中多数边位于亚线性或分形拓扑空间；DBS保持连通性直至超度量骨干，而SmD仅保证至度量骨干；DBS运行时间比识别单一骨干慢两个数量级，但所有稀疏化不超过2分钟，说明其可系统覆盖稀疏化等级并保持连通。3.2 距离骨干保留中心性与动力学：通过12个社会接触网络的AUC与统计检验，DBS和SmD在保留特征向量中心性排名及Katz中心性方面优于wEffRes、DispFilt和W；在SI微观平均感染顺序上DBS优于wEffRes和SmD，在宏观半感染时间t_0.5上wEffRes、SmD和DBS优于DispFilt和W，但wEffRes受高中心性种子驱动，在任意种子和随机网络中SmD与DBS更稳健。结论是最短路径冗余稀疏化能优化中心性和传播动力学的保留。3.3 距离骨干合成揭示最优骨干：通过优化中心性排名、感染时间排名、感染时间尺度和稀疏度的加权和，发现最优骨干位于乘积骨干与度量骨干之间，二者分别给出宽松和严格边界；总体最优骨干移除超过一半连接并保留超过80%性能指标；DBS较SmD给出更精确的跨网络最优子图阈值，而SmD计算更快。

讨论部分总结：DBS根据路径长度度量识别每条边所属拓扑空间，较高合成参数诱导更强稀疏化；DBS与SmD性能相近，因二者均处理最短路径冗余，但DBS提供更深拓扑理解和理论依据，SmD更实用快速。研究网络在规模、连通性和模块性上多样，仍支持移除最短路径冗余可稀疏化而不丢失重要信息；DBS计算成本较高且需选择阈值，SmD可作为更快替代。乘积骨干和度量骨干给出宽松与严格稀疏化边界；总体最优骨干在保留多指标的同时移除超过一半连接。最优合成参数提示DBS参数可能是传播动力学所需分形拓扑的特征，未来可研究SIS、SIR等更复杂动力学和同步现象对分形拓扑的需求，并可拓展至距离闭包理论。研究结论部分翻译：本研究中，研究人员考察距离骨干如何用于构建更稀疏但动态和结构上忠实于复杂网络的表示。DBS根据路径长度度量方式识别每条边所属的拓扑空间；较高合成参数值诱导更强稀疏化，因为它们给间接路径分配更短距离。由路径长度度量诱导的不同骨干是不同间接路径成本归因下的主要子图。研究人员发现一个总体最优骨干，该骨干移除超过一半连接，同时保留超过80%的性能指标。由于合成参数定义边所属拓扑空间，最优参数提示DBS参数可能是传播动力学所需分形拓扑的一个特征。这为未来研究更复杂动力学模型（如SIS和SIR流行病）及同步现象在多大程度上需要分形拓扑提供了方向。