Efficient exploration of multiplex networks
Efficient exploration of multiplex networks
复制标题
DOI：
10.1088/1367-2630/18/4/043035
复制
发表时间：
2016-04-25
影响因子：
3.3
通讯作者：
Latora, Vito
中科院分区：
文献类型：
--
作者：
Battiston, Federico;Nicosia, Vincenzo;Latora, Vito
利用本地信息导航网络的有效技术是对大规模在线社会系统进行采样和在点对点系统中检索资源的基础。有偏随机行走，即其运动对相邻节点的属性有偏的行走，已被很大程度上用于设计智能局部策略来探索网络，例如通过构造最大混合轨迹或允许节点的几乎均匀采样。在这里，我们介绍和研究了多重网络上的有偏随机漫步，其中节点通过不同类型的链接在不同的相互作用层中组织而成的图，并提供了它们的长期特性的解析解，包括平稳占用概率分布和熵率。我们专注于度偏随机行走，并区分了两类行走，即那些转移概率依赖于大量参数的行走，这些参数在层数上是广泛的，以及那些运动依赖于相邻节点的内在多重属性的行走。我们分析了多路网络的结构对行走者稳态行为的影响，发现异构度分布以及层间度相关性和边缘重叠的存在决定了多路网络可以通过有偏行走有效探索的程度。最后，我们表明，在现实世界的多路交通网络中，有效导航和链路故障弹性之间的权衡导致系统的扩散特性与适当随机化的多路图的扩散特性有质的不同。这一事实表明，在现实世界系统的建模中，多重性是一个重要的因素。
Efficient techniques to navigate networks with local information are fundamental to sample large-scale online social systems and to retrieve resources in peer-to-peer systems. Biased random walks, i.e. walks whose motion is biased on properties of neighbouring nodes, have been largely exploited to design smart local strategies to explore a network, for instance by constructing maximally mixing trajectories or by allowing an almost uniform sampling of the nodes. Here we introduce and study biased random walks on multiplex networks, graphs where the nodes are related through different types of links organised in distinct and interacting layers, and we provide analytical solutions for their long-time properties, including the stationary occupation probability distribution and the entropy rate. We focus on degree-biased random walks and distinguish between two classes of walks, namely those whose transition probability depends on a number of parameters which is extensive in the number of layers, and those whose motion depends on intrinsically multiplex properties of the neighbouring nodes. We analyse the effect of the structure of the multiplex network on the steady-state behaviour of the walkers, and we find that heterogeneous degree distributions as well as the presence of inter-layer degree correlations and edge overlap determine the extent to which a multiplex can be efficiently explored by a biased walk. Finally we show that, in real-world multiplex transportation networks, the trade-off between efficient navigation and resilience to link failure has resulted into systems whose diffusion properties are qualitatively different from those of appropriately randomised multiplex graphs. This fact suggests that multiplexity is an important ingredient to include in the modelling of real-world systems.