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

Jens Christian Claussen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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
Issue number1
Publication statusPublished - 15 Feb 2007

Bibliographical note

© 2007, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International


Dive into the research topics of 'Offdiagonal complexity: A computationally quick complexity measure for graphs and networks'. Together they form a unique fingerprint.

Cite this