Ranking influential nodes in networks from partial information
arXiv:2009.06307 · doi:10.1103/PhysRevResearch.5.033123
Abstract
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.
13 pages, 7 figures. Significant changes in title and content (references added, more data sets analyzed, effect of network sparsity studied in more detail)
References in corpus (6)
Cited by in corpus (6)
- Upstreamness and downstreamness in input-output analysis from local and aggregate information
- Reconstructing supply networks
- Correlation between upstreamness and downstreamness in random global value chains
- Predicting Nodal Influence via Local Iterative Metrics
- On the area swept by a biased diffusion till its first-exit time: Martingale approach and gambling opportunities
- Statistics of the non-zero eigenvalues and singular values of low-rank random matrices with non-negative entries