Complexity of networks I: The set-complexity of binary graphs

The balance between symmetry and randomness as a property of networks can be viewed as a kind of complexity. We use here our previously defined set complexity measure (Galas et al., IEEE Trans Inf Theory 2010, 56), which was used to approach the problem of defining biological information, in the mathematical analysis of networks. This information theoretic measure is used to explore the complexity of binary, undirected graphs. The complexities, Psi of some specific classes of graphs can be calculated in closed form. Some simple graphs have a complexity value of zero, but graphs with significant values of Psi are rare. We find that the most complex of the simple graphs are the complete bipartite graphs (CBGs). In this simple case, the complexity, ?, is a strong function of the size of the two node sets in these graphs. We find the maximum Psi binary graphs as well. These graphs are distinct from, but similar to CBGs. Finally, we explore directed and stochastic processes for growing graphs (hill-climbing and random duplication, respectively) and find that node duplication and partial node duplication conserve interesting graph properties. Partial duplication can grow extremely complex graphs, while full node duplication cannot do so. By examining the eigenvalue spectrum of the graph Laplacian we characterize the symmetry of the graphs and demonstrate that, in general, breaking specific symmetries of the binary graphs increases the set-based complexity, Psi. The implications of these results for more complex, multiparameter graphs, and for physical and biological networks and the processes of network evolution are discussed. (c) 2011 Wiley Periodicals, Inc. Complexity, 17,5164, 2011