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

Claussen, Jens Christian (2007). Offdiagonal complexity:A computationally quick complexity measure for graphs and networks. Physica A: Statistical Mechanics and its Applications, 375 (1), pp. 365-373.


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: Engineering & Applied Sciences
Additional Information: © 2007, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Uncontrolled Keywords: Statistics and Probability,Condensed Matter Physics
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
https://www.sci ... 9484?via%3Dihub (Publisher URL)
Published Date: 2007-02-15
Authors: Claussen, Jens Christian ( 0000-0002-9870-4924)

Export / Share Citation


Additional statistics for this record