Reliability of rank order in sampled networks

P.-J. Kim and H. Jeong ()

The European Physical Journal B: Condensed Matter and Complex Systems, 2007, vol. 55, issue 1, 109-114

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. Copyright EDP Sciences/Società Italiana di Fisica/Springer-Verlag 2007

Keywords: 89.75.Hc Networks and genealogical trees; 89.75.Fb Structures and organization in complex systems (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://hdl.handle.net/10.1140/epjb/e2007-00033-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurphb:v:55:y:2007:i:1:p:109-114

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/10051

DOI: 10.1140/epjb/e2007-00033-7

Access Statistics for this article

The European Physical Journal B: Condensed Matter and Complex Systems is currently edited by P. Hänggi and Angel Rubio

More articles in The European Physical Journal B: Condensed Matter and Complex Systems from Springer, EDP Sciences
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().