Soriano-Paños David, Xavier Costa Felipe, Rocha Luis M
Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain.
GOTHAM lab, Institute for Biocomputation and Physics of Complex Systems, University of Zaragoza, 50018 Zaragoza, Spain.
J Phys Complex. 2025 Sep 1;6(3):035005. doi: 10.1088/2632-072X/adf2ed. Epub 2025 Aug 1.
Sparsification aims at extracting a reduced core of associations that best preserves both the dynamics and topology of networks while reducing the computational cost of simulations. We show that the semi-metric topology of complex networks yields a natural and algebraically-principled sparsification that outperforms existing methods on those goals. Weighted graphs whose edges represent distances between nodes are when at least one edge breaks the triangle inequality (transitivity). We first confirm with new experiments that the -a unique subgraph of all edges that obey the triangle inequality and thus preserve all shortest paths-recovers susceptible-infected dynamics over the original non-sparsified graph. This recovery is improved when we remove only those edges that break the triangle inequality significantly, i.e. edges with large semi-metric distortion. Based on these results, we propose the new method to progressively sparsify networks in decreasing order of semi-metric distortion. Our method recovers the macro- and micro-level dynamics of epidemic outbreaks better than other methods while also yielding sparser yet connected subgraphs that preserve all shortest paths. Overall, we show that semi-metric distortion overcomes the limitations of edge betweenness in ranking the dynamical relevance of edges not participating in any shortest path, as it quantifies the existence and strength of alternative transmission pathways.
稀疏化旨在提取一个精简的关联核心，在降低模拟计算成本的同时，最好地保留网络的动态特性和拓扑结构。我们表明，复杂网络的半度量拓扑产生了一种自然且基于代数原理的稀疏化方法，在这些目标上优于现有方法。当至少一条边打破三角不等式（传递性）时，其边表示节点之间距离的加权图是[此处原文缺失描述]。我们首先通过新的实验证实，- 所有遵循三角不等式从而保留所有最短路径的边的唯一子图 - 在原始未稀疏化的图上恢复了易感 - 感染动态。当我们仅移除那些显著打破三角不等式的边，即具有大的半度量失真的边时，这种恢复得到了改善。基于这些结果，我们提出了新的[此处原文缺失方法名称]方法，以半度量失真的降序逐步稀疏化网络。我们的方法在恢复疫情爆发的宏观和微观层面动态方面比其他方法更好，同时还产生了更稀疏但连通的子图，保留了所有最短路径。总体而言，我们表明半度量失真克服了边介数在对不参与任何最短路径的边的动态相关性进行排序时的局限性，因为它量化了替代传播途径的存在和强度。
