dorsal/arxiv
View SchemaSeeking for Simplicity in Complex Networks
| Authors | Luciano da Fontoura Costa, Francisco A. Rodrigues |
|---|---|
| Categories | |
| ArXiv ID | physics/0702102 |
| URL | https://arxiv.org/abs/physics/0702102 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
Complex networks can be understood as graphs whose connectivity deviates from those of regular or near-regular graphs, which are understood as being `simple'. While a great deal of the attention so far dedicated to complex networks has been duly driven by the `complex' nature of these structures, in this work we address the identification of simplicity, in the sense of regularity, in complex networks. The basic idea is to seek for subgraphs exhibiting small dispersion (e.g. standard deviation or entropy) of local measurements such as the node degree and clustering coefficient. This approach paves the way for the identification of subgraphs (patches) with nearly uniform connectivity, therefore complementing the characterization of the complexity of networks. We also performed analysis of cascade failures, revealing that the removal of vertices in `simple' regions results in smaller damage to the network structure than the removal of vertices in the heterogeneous regions. We illustrate the potential of the proposed methodology with respect to four theoretical models as well as protein-protein interaction networks of three different species. Our results suggest that the simplicity of protein interaction grows as the result of natural selection. This increase in simplicity makes these networks more robust to cascade failures.
{
"annotation_id": "4954ef97-e16f-4c86-8627-211822ba90eb",
"date_created": "2026-03-02T18:01:18.497000Z",
"date_modified": "2026-03-02T18:01:18.497000Z",
"file_hash": "ac53be43c46a2d83cae0bdc6f7500209ed64d764a1951b4ef840dd2d096f7d5c",
"private": false,
"record": {
"abstract": "Complex networks can be understood as graphs whose connectivity deviates from\nthose of regular or near-regular graphs, which are understood as being\n`simple\u0027. While a great deal of the attention so far dedicated to complex\nnetworks has been duly driven by the `complex\u0027 nature of these structures, in\nthis work we address the identification of simplicity, in the sense of\nregularity, in complex networks. The basic idea is to seek for subgraphs\nexhibiting small dispersion (e.g. standard deviation or entropy) of local\nmeasurements such as the node degree and clustering coefficient. This approach\npaves the way for the identification of subgraphs (patches) with nearly uniform\nconnectivity, therefore complementing the characterization of the complexity of\nnetworks. We also performed analysis of cascade failures, revealing that the\nremoval of vertices in `simple\u0027 regions results in smaller damage to the\nnetwork structure than the removal of vertices in the heterogeneous regions. We\nillustrate the potential of the proposed methodology with respect to four\ntheoretical models as well as protein-protein interaction networks of three\ndifferent species. Our results suggest that the simplicity of protein\ninteraction grows as the result of natural selection. This increase in\nsimplicity makes these networks more robust to cascade failures.",
"arxiv_id": "physics/0702102",
"authors": [
"Luciano da Fontoura Costa",
"Francisco A. Rodrigues"
],
"categories": [
"physics.data-an",
"cond-mat.dis-nn",
"physics.comp-ph"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Seeking for Simplicity in Complex Networks",
"url": "https://arxiv.org/abs/physics/0702102"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7d0e558e-f4cf-46a8-b163-2ca9a96f0a14",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}