Ranking influential nodes in networks from partial information

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.

arXiv comment13 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 (24)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Lethality and centrality in protein networks
• Specificity and stability in topology of protein networks
• Critical phenomena in complex networks
• Communicability in complex networks
• The statistical mechanics of networks
• Random walks and diffusion on networks
• The Physics of Communicability in Complex Networks
• Consistency and differences between centrality measures across distinct classes of networks
• The Physics of Financial Networks
• Trophic coherence determines food-web stability
• Mean field solution of the Ising model on a Barabasi-Albert network
• Systemic risk analysis in reconstructed economic and financial networks
• Toolbox model of evolution of prokaryotic metabolic networks and their regulation
• Linking the Network Centrality Measures Closeness and Degree
• Correlation between centrality metrics and their application to the opinion model
• Reconstruction methods for networks: the case of economic and financial systems
• How Market Ecology Explains Market Malfunction
• Dense Power-law Networks and Simplicial Complexes
• Beyond ranking nodes: Predicting epidemic outbreak sizes by network centralities
• Dense networks with scale-free feature
• Low Rank Approximation Method for Efficient Green's Function Calculation of Dissipative Quantum Transport
• Second largest Eigenpair Statistics for Sparse Graphs

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