dorsal/arxiv
View SchemaOffdiagonal Complexity: A computationally quick complexity measure for graphs and networks
| Authors | Jens Christian Claussen |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0410024 |
| URL | https://arxiv.org/abs/q-bio/0410024 |
| DOI | 10.1016/j.physa.2006.08.067 |
| Journal | Physica A 375, 365 (2007) |
Abstract
A vast variety of biological, social, and economical networks shows topologies drastically differing from random graphs; yet the quantitative characterization remains unsatisfactory from a conceptual point of view. Motivated from the discussion of small scale-free networks, a biased link distribution entropy is defined, which takes an extremum for a power law distribution. This approach is extended to the node-node link cross-distribution, whose nondiagonal elements characterize the graph structure beyond link distribution, cluster coefficient and average path length. From here a simple (and computationally cheap) complexity measure can be defined. This Offdiagonal Complexity (OdC) is proposed as a novel measure to characterize the complexity of an undirected graph, or network. While both for regular lattices and fully connected networks OdC is zero, it takes a moderately low value for a random graph and shows high values for apparently complex structures as scale-free networks and hierarchical trees. The Offdiagonal Complexity apporach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates.
{
"annotation_id": "90f96b5d-97ef-4e76-8aa1-c5e13a99754b",
"date_created": "2026-03-02T18:01:31.486000Z",
"date_modified": "2026-03-02T18:01:31.486000Z",
"file_hash": "cd5cb57f04fb738df50837b5b13302501ac9f42b924eb5111c916a1aba8a3039",
"private": false,
"record": {
"abstract": "A vast variety of biological, social, and economical networks shows\ntopologies drastically differing from random graphs; yet the quantitative\ncharacterization remains unsatisfactory from a conceptual point of view.\nMotivated from the discussion of small scale-free networks, a biased link\ndistribution entropy is defined, which takes an extremum for a power law\ndistribution. This approach is extended to the node-node link\ncross-distribution, whose nondiagonal elements characterize the graph structure\nbeyond link distribution, cluster coefficient and average path length. From\nhere a simple (and computationally cheap) complexity measure can be defined.\nThis Offdiagonal Complexity (OdC) is proposed as a novel measure to\ncharacterize the complexity of an undirected graph, or network. While both for\nregular lattices and fully connected networks OdC is zero, it takes a\nmoderately low value for a random graph and shows high values for apparently\ncomplex structures as scale-free networks and hierarchical trees. The\nOffdiagonal Complexity apporach is applied to the Helicobacter pylori protein\ninteraction network and randomly rewired surrogates.",
"arxiv_id": "q-bio/0410024",
"authors": [
"Jens Christian Claussen"
],
"categories": [
"q-bio.MN",
"q-bio.QM"
],
"doi": "10.1016/j.physa.2006.08.067",
"journal_ref": "Physica A 375, 365 (2007)",
"title": "Offdiagonal Complexity: A computationally quick complexity measure for graphs and networks",
"url": "https://arxiv.org/abs/q-bio/0410024"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b8c3b07e-a1e7-4e6a-83fb-3f5f614dc5c9",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}