School of Electronic Engineering and Computer Science, Queen Mary University of London, Mile End Road, London, E1 4NS, UK.
Sci Rep. 2020 Nov 5;10(1):19150. doi: 10.1038/s41598-020-75741-y.
Alternative paths in a network play an important role in its functionality as they can maintain the information flow under node/link failures. In this paper we explore the navigation of a network taking into account the alternative paths and in particular how can we describe this navigation in a concise way. Our approach is to simplify the network by aggregating into groups the nodes that do not contribute to alternative paths. We refer to these groups as super-nodes, and describe the post-aggregation network with super-nodes as the skeleton network. We present a method to describe with the least amount of information the paths in the super-nodes and skeleton network. Applying our method to several real networks we observed that there is scaling behaviour between the information required to describe all the paths in a network and the minimal information to describe the paths of its skeleton. We show how from this scaling we can evaluate the information of the paths for large networks with less computational cost.
网络中的备用路径在其功能中起着重要作用，因为它们可以在节点/链路故障下维持信息流。在本文中，我们探讨了考虑备用路径的网络导航，特别是如何以简洁的方式描述这种导航。我们的方法是通过将对备用路径没有贡献的节点聚合到组中来简化网络。我们将这些组称为超级节点，并将聚合后的网络描述为骨干网络。我们提出了一种用最少的信息来描述超级节点和骨干网络中的路径的方法。将我们的方法应用于几个真实网络，我们观察到在描述网络中所有路径所需的信息量和描述其骨干网络的路径的最小信息量之间存在缩放行为。我们展示了如何通过这种缩放，以较低的计算成本评估大型网络中路径的信息量。
