De Vico Fallani Fabrizio, Rolland Thibault
Sorbonne University, Paris Brain Institute (ICM), CNRS, Inria, Inserm, AP-HP, Pitie-Salpetriere Hospital, Paris, France.
PNAS Nexus. 2025 Jun 18;4(7):pgaf203. doi: 10.1093/pnasnexus/pgaf203. eCollection 2025 Jul.
Network representation is crucial across various scientific, societal, technological, and artistic domains. The primary goal is to highlight patterns out of nodes interconnected by edges that are easy to understand, facilitate communication, and support decision-making. This is typically achieved by rearranging the nodes to minimize the edge crossings responsible of unintelligible and often unesthetic trends. But when the nodes cannot be moved, as in spatial and physical networks, this procedure is not viable. Here, we overcome this impasse by turning the edge crossing problem into a graph filtering optimization. By introducing the concept of progressive cost, we demonstrate that longer connections prompt the optimal solution to yield sparser networks, thereby limiting the number of intersections and getting more readable layouts. This theoretical result matches human behavior and provides an ecologically inspired criterion to visualize and model real-world interconnected systems.
网络表示在各种科学、社会、技术和艺术领域都至关重要。其主要目标是从由边相互连接的节点中突出易于理解、便于交流并支持决策的模式。这通常是通过重新排列节点以尽量减少导致难以理解且往往不美观趋势的边交叉来实现的。但当节点无法移动时，如在空间和物理网络中，此过程不可行。在此，我们通过将边交叉问题转化为图滤波优化来克服这一僵局。通过引入渐进成本的概念，我们证明更长的连接促使最优解产生更稀疏的网络，从而限制交叉数量并获得更具可读性的布局。这一理论结果与人类行为相符，并为可视化和建模现实世界的互联系统提供了一个受生态启发的标准。
