Offdiagonal complexity: A computationally quick complexity measure for graphs and networks

Jens Christian Claussen*

*Corresponding author for this work

Research output: Contribution to journalArticle

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 OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates.

Original languageEnglish
Pages (from-to)365-373
Number of pages9
JournalPhysica A: Statistical Mechanics and its Applications
Volume375
Issue number1
DOIs
Publication statusPublished - 15 Feb 2007

Fingerprint

Complexity Measure
Scale-free Networks
Graph in graph theory
Random Graphs
Protein Interaction Networks
Power-law Distribution
Path Length
Extremum
Vertex of a graph
Complex Structure
Undirected Graph
Network Topology
Biased
Entropy
range (extremes)
Zero
Coefficient
topology
entropy
proteins

Bibliographical note

© 2007, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/

Cite this

@article{4316d31e722c44e5a89a2d64aef5cd4b,
title = "Offdiagonal complexity: A computationally quick complexity measure for graphs and networks",
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 OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates.",
author = "Claussen, {Jens Christian}",
note = "{\circledC} 2007, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/",
year = "2007",
month = "2",
day = "15",
doi = "10.1016/j.physa.2006.08.067",
language = "English",
volume = "375",
pages = "365--373",
journal = "Physica A",
issn = "0378-4371",
publisher = "Elsevier",
number = "1",

}

TY - JOUR

T1 - Offdiagonal complexity

T2 - A computationally quick complexity measure for graphs and networks

AU - Claussen, Jens Christian

N1 - © 2007, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/

PY - 2007/2/15

Y1 - 2007/2/15

N2 - 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 OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates.

AB - 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 OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates.

UR - http://www.scopus.com/inward/record.url?scp=33751416849&partnerID=8YFLogxK

UR - https://www.sciencedirect.com/science/article/pii/S0378437106009484?via%3Dihub

U2 - 10.1016/j.physa.2006.08.067

DO - 10.1016/j.physa.2006.08.067

M3 - Article

AN - SCOPUS:33751416849

VL - 375

SP - 365

EP - 373

JO - Physica A

JF - Physica A

SN - 0378-4371

IS - 1

ER -