dorsal/arxiv
View SchemaExploring Complex Networks through Random Walks
| Authors | Luciano da Fontoura Costa |
|---|---|
| Categories | |
| ArXiv ID | physics/0604193 |
| URL | https://arxiv.org/abs/physics/0604193 |
| DOI | 10.1103/PhysRevE.75.016102 |
| Journal | Phys. Rev. E 75, 016102 (2007) |
Abstract
Most real complex networks -- such as protein interactions, social contacts, the internet -- are only partially known and available to us. While the process of exploring such networks in many cases resembles a random walk, it becomes a key issue to investigate and characterize how effectively the nodes and edges of such networks can be covered by different strategies. At the same time, it is critically important to infer how well can topological measurements such as the average node degree and average clustering coefficient be estimated during such network explorations. The present article addresses these problems by considering random and Barab\'asi-Albert (BA) network models with varying connectivity explored by three types of random walks: traditional, preferential to untracked edges, and preferential to unvisited nodes. A series of relevant results are obtained, including the fact that random and BA models with the same size and average node degree allow similar node and edge coverage efficiency, the identification of linear scaling with the size of the network of the random walk step at which a given percentage of the nodes/edges is covered, and the critical result that the estimation of the averaged node degree and clustering coefficient by random walks on BA networks often leads to heavily biased results. Many are the theoretical and practical implications of such results.
{
"annotation_id": "9e62bf6e-84ee-4f7a-9e93-e56a190e6753",
"date_created": "2026-03-02T18:01:06.760000Z",
"date_modified": "2026-03-02T18:01:06.760000Z",
"file_hash": "e55e577ee0799cd0bca26fe176e2c56bccd0213bfab70787b60694e9fad3d945",
"private": false,
"record": {
"abstract": "Most real complex networks -- such as protein interactions, social contacts,\nthe internet -- are only partially known and available to us. While the process\nof exploring such networks in many cases resembles a random walk, it becomes a\nkey issue to investigate and characterize how effectively the nodes and edges\nof such networks can be covered by different strategies. At the same time, it\nis critically important to infer how well can topological measurements such as\nthe average node degree and average clustering coefficient be estimated during\nsuch network explorations. The present article addresses these problems by\nconsidering random and Barab\\\u0027asi-Albert (BA) network models with varying\nconnectivity explored by three types of random walks: traditional, preferential\nto untracked edges, and preferential to unvisited nodes. A series of relevant\nresults are obtained, including the fact that random and BA models with the\nsame size and average node degree allow similar node and edge coverage\nefficiency, the identification of linear scaling with the size of the network\nof the random walk step at which a given percentage of the nodes/edges is\ncovered, and the critical result that the estimation of the averaged node\ndegree and clustering coefficient by random walks on BA networks often leads to\nheavily biased results. Many are the theoretical and practical implications of\nsuch results.",
"arxiv_id": "physics/0604193",
"authors": [
"Luciano da Fontoura Costa"
],
"categories": [
"physics.soc-ph",
"cond-mat.stat-mech",
"physics.data-an"
],
"doi": "10.1103/PhysRevE.75.016102",
"journal_ref": "Phys. Rev. E 75, 016102 (2007)",
"title": "Exploring Complex Networks through Random Walks",
"url": "https://arxiv.org/abs/physics/0604193"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "942604b6-7098-4886-b6b6-dbf891837d33",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}