Offdiagonal complexity: A computationally quick complexity measure for graphs and networks
Saved in:
| Title: | Offdiagonal complexity: A computationally quick complexity measure for graphs and networks |
|---|---|
| Authors: | Claussen, Jens Christian1 claussen@theo-physik.uni-kiel.de |
| Source: | Physica A. Feb2007, Vol. 375 Issue 1, p365-373. 9p. |
| Subjects: | Random graphs, Linear algebra, Topology, Thermodynamics |
| Abstract: | 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. [Copyright &y& Elsevier] |
| Copyright of Physica A is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
