Abstract

Complex networks are found in biology, ecology, sociology, technology and communications, and understanding how their global properties arise from local structure has been the subject of considerable investigation. A recent and important observation is that some local network structures, or network motifs, are much more frequently observed in complex networks than would be expected by chance [1,2]. Although this biased distribution of motifs appears to apply to a broad range of networks, it remains unclear why some motifs are ubiquitous and others are not. What is likely, however, is that the global behaviour results in a hierarchical manner from smaller network modules performing specific tasks. Understanding the comparative advantages of different small networks would explain why natural and designed complex networks make disparate use of network motifs.

We study the computing power of small networks by evaluating all possible boolean update rules (the software) over all possible network topologies (the hardware). By changing the software, we find that some small networks are fundamentally more capable of executing a variety of tasks than others. We calculate the value of a network by comparing its versatility to its cost and find that many programs can perform the same task but with varying levels of network complexity and resistance to mutations. The emerging picture explains why some network motifs might be favoured over others and suggests design principles for network engineering.

[1] R.\ Milo {\it et al.}, ``Network Motifs: Simple Building Blocks of Complex Networks,’‘ {\it Science} {\bf 298}, 824 (2002).

[2] R.\ Milo {\it et al.}, ``Superfamilies of Evolved and Designed Networks,’‘ {\it Science} {\bf 303}, 1538 (2004).

Collaborators: Sebastian Ahnert, Emmanuel Barillot