Reliability of Rank Order in Sampled Networks

In scale-free networks, ranking the individual nodes based on their importance has useful applications, e.g. identifying hubs for epidemic control. However, in most real situations only limited sub-structures of the complete networks are available, therefore the reliability of order relationship in the sampled networks is worth to investigate. With the set of randomly sampled nodes from the underlying original networks, we rank individual nodes by the three centrality measures -- degree, betweenness, and closeness. We show that the nodes of the higher ranks from the sampled networks provide a relatively better characterization of their ranks in the original networks than the nodes with lower ranks. We also reveal that closeness-based order relationship is more reliable than any other quantities due to the global characteristic of the closeness measure. Finally, it is demonstrated that if the access to hubs is limited during the sampling process, increase in sampling fraction can even lower the accuracy of sampling.