Offdiagonal complexity: measuring network complexity
What is the best way to measure network complexity? Complexity can be defined as presence of a diversity of cliques that are hierarchically connected by a number of central nodes. Thus, the network should have both as many cliques as possible, as well as a number of nodes with high level of be tweeness that connect these cliques as efficiently as possible. Another way to describe this is by saying that the network should provide as much local interaction between nodes as possible, while at the same time providing means for nodes to reach peers in other cliques as economically as possible. Long story short, I was thinking of using betweennnes centrality to get at “complexity” until I found this measure of “offdiagonal complexity” http://arxiv.org/PS_cache/q-bio/pdf/0410/0410024v2.pdf:
Many complex biological, social, and economical networks show topologies drastically differing from random graphs. But, what is a complex network, i.e.\ how can one quantify the complexity of a graph? Here the Offdiagonal Complexity (OdC), a new, and computationally cheap, measure of complexity is defined, based on the node-node link cross-distribution, whose nondiagonal elements characterize the graph structure beyond link distribution, cluster coefficient and average path length. The OdC apporach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates thereof. In addition, OdC is used to characterize the spatial complexity of cell aggregates. We investigate the earliest embryo development states of Caenorhabditis elegans. The development states of the premorphogenetic phase are represented by symmetric binary-valued cell connection matrices with dimension growing from 4 to 385. These matrices can be interpreted as adjacency matrix of an undirected graph, or network. The OdC approach allows to describe quantitatively the complexity of the cell aggregate geometry.
