Reliability of rank order in sampled networks

Abstract

In complex scale-free networks, ranking the individual nodes based upon their importance has useful applications, such as the identification of hubs for epidemic control, or bottlenecks for controlling traffic congestion. However, in most real situations, only limited sub-structures of entire networks are available, and therefore the reliability of the order relationships in sampled networks requires investigation. With a set of randomly sampled nodes from the underlying original networks, we rank individual nodes by three centrality measures: degree, betweenness, and closeness. The higher-ranking nodes from the sampled networks provide a relatively better characterisation of their ranks in the original networks than the lower-ranking nodes. A closeness-based order relationship is more reliable than any other quantity, due to the global nature of the closeness measure. In addition, we show that if access to hubs is limited during the sampling process, an increase in the sampling fraction can in fact decrease the sampling accuracy. Finally, an estimation method for assessing sampling accuracy is suggested.

References in corpus (12)

• Community structure in social and biological networks
• Epidemic spreading in scale-free networks
• Lethality and centrality in protein networks
• The large-scale organization of metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Universal Behavior of Load Distribution in Scale-free Networks
• Halting viruses in scale-free networks
• Statistical properties of sampled networks
• Truncation of power law behavior in "scale-free" network models due to information filtering
• Path finding strategies in scale-free networks
• Accuracy and Scaling Phenomena in Internet Mapping
• Traceroute sampling makes random graphs appear to have power law degree distributions

Cited by in corpus (6)

• Consistency and differences between centrality measures across distinct classes of networks
• Identifying the starting point of a spreading process in complex networks
• Correlation between centrality metrics and their application to the opinion model
• Estimating the sensitivity of centrality measures w.r.t. measurement errors
• Sampling networks by nodal attributes
• The impact of partially missing communities~on the reliability of centrality measures