Berlin 2005 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

SYBN: Biological and Social Networks

SYBN 3: Biologische und Soziale Netzwerke, Postersitzung

SYBN 3.9: Poster

Monday, March 7, 2005, 14:00–15:30, Poster TU E

Offdiagonal Complexity: A computationally quick complexity measure for graphs and networks — •Jens Christian Claussen — Theoretical Physics, University Kiel

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) [1] 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.

[1] J. C. Claussen, arxiv.org q-bio/0410024