dorsal/arxiv
View SchemaReliability of rank order in sampled networks
| Authors | Pan-Jun Kim, Hawoong Jeong |
|---|---|
| Categories | |
| ArXiv ID | physics/0702148 |
| URL | https://arxiv.org/abs/physics/0702148 |
| DOI | 10.1140/epjb/e2007-00033-7 |
| Journal | Eur. Phys. J. B 55, 109-114 (2007) |
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.
{
"annotation_id": "527c2db6-5b7a-4423-afc1-3f15c932046c",
"date_created": "2026-03-02T18:01:17.712000Z",
"date_modified": "2026-03-02T18:01:17.712000Z",
"file_hash": "12796d52d662e08ec59638ae874cd7d47c54ea0fb2b2e7f9da1b4de2765cdd12",
"private": false,
"record": {
"abstract": "In complex scale-free networks, ranking the individual nodes based upon their\nimportance has useful applications, such as the identification of hubs for\nepidemic control, or bottlenecks for controlling traffic congestion. However,\nin most real situations, only limited sub-structures of entire networks are\navailable, and therefore the reliability of the order relationships in sampled\nnetworks requires investigation. With a set of randomly sampled nodes from the\nunderlying original networks, we rank individual nodes by three centrality\nmeasures: degree, betweenness, and closeness. The higher-ranking nodes from the\nsampled networks provide a relatively better characterisation of their ranks in\nthe original networks than the lower-ranking nodes. A closeness-based order\nrelationship is more reliable than any other quantity, due to the global nature\nof the closeness measure. In addition, we show that if access to hubs is\nlimited during the sampling process, an increase in the sampling fraction can\nin fact decrease the sampling accuracy. Finally, an estimation method for\nassessing sampling accuracy is suggested.",
"arxiv_id": "physics/0702148",
"authors": [
"Pan-Jun Kim",
"Hawoong Jeong"
],
"categories": [
"physics.soc-ph",
"cond-mat.stat-mech",
"physics.data-an",
"stat.AP"
],
"doi": "10.1140/epjb/e2007-00033-7",
"journal_ref": "Eur. Phys. J. B 55, 109-114 (2007)",
"title": "Reliability of rank order in sampled networks",
"url": "https://arxiv.org/abs/physics/0702148"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b0c61702-18b1-4001-a1ed-f3b0b1f02f13",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}