Ranking influential nodes in networks from aggregate local information
Ranking influential nodes in networks from aggregate local information
复制标题
DOI：
10.1103/physrevresearch.5.033123
复制
发表时间：
2020-09
影响因子：
4.2
通讯作者：
Silvia Bartolucci;F. Caccioli;F. Caravelli;P. Vivo
中科院分区：
文献类型：
--
作者：
Silvia Bartolucci;F. Caccioli;F. Caravelli;P. Vivo
许多复杂的系统表现出一种自然的层次结构，其中的元素可以根据“影响力”的概念进行排序。虽然计算节点的影响通常需要完整和准确地了解组成部分之间的相互作用，但使用低秩近似，我们表明，在各种情况下，关于节点邻域的局部信息足以可靠地估计它们的影响程度，而无需推断或重建整个相互作用图。只要底层网络不是非常稀疏，我们的框架就能成功地以高精度逼近各种系统中影响的不同表现形式，如WWW PageRank、生态系统的营养水平、复杂经济体中工业部门的上游以及社会网络的中位性度量。我们还讨论了这种“新兴局部性”对非线性网络观测值近似计算的影响。
Many complex systems exhibit a natural hierarchy in which elements can be ranked according to a notion of"influence". While the complete and accurate knowledge of the interactions between constituents is ordinarily required for the computation of nodes' influence, using a low-rank approximation we show that in a variety of contexts local information about the neighborhoods of nodes is enough to reliably estimate how influential they are, without the need to infer or reconstruct the whole map of interactions. Our framework is successful in approximating with high accuracy different incarnations of influence in systems as diverse as the WWW PageRank, trophic levels of ecosystems, upstreamness of industrial sectors in complex economies, and centrality measures of social networks, as long as the underlying network is not exceedingly sparse. We also discuss the implications of this"emerging locality"on the approximate calculation of non-linear network observables.