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


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.

Publication DOI:
Divisions: College of Engineering & Physical Sciences
Additional Information: © 2007, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Uncontrolled Keywords: Statistics and Probability,Condensed Matter Physics
Publication ISSN: 1873-2119
Last Modified: 29 Apr 2024 07:26
Date Deposited: 12 Dec 2018 09:56
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
https://www.sci ... 9484?via%3Dihub (Publisher URL)
PURE Output Type: Article
Published Date: 2007-02-15
Authors: Claussen, Jens Christian (ORCID Profile 0000-0002-9870-4924)

Export / Share Citation


Additional statistics for this record