I chose to review a paper by Milo, Itzkovitz, Kashtan, Reuven, Levitt, Shen-Orr, Ayzenshtat, Sheffer, and Alon titled “Superfamilies of Evolved and Designed Networks.” This paper tackles the problem of how to characterize networks despite vast differences in scale. It accomplishes this by identifying “network motifs” within the structure of various networks. Here a network motif is one of the thirteen directed graphs possible on three nodes or triad. The figure below shows the 13 possible triads.

Milo et al. analyzed networks present in different bacteria, larger organisms like fruit flies and worms, the world wide web, social networks, and finally models of different languages. These networks fell into four “superfamilies” with the world wide web and social networks showing similar structure and the other categories of networks showing similarity within themselves. These “superfamilies” were characterized as having different relative mixes of the various triads. For instance, the networks within bacteria had triad #7 more often than expected if the graph were a random graph. Triad # 7 represents a “feed forward” loop which is used to react to changes in the environment. Triad #10 was more present in networks describing the internal workings of larger organisms. This triad as well as triad #9 represent a two node feedback system that is regulated by a third node. The world wide web and social networks had similar structures with the “clique” triad (triad #13) most prevalent. As a side note, this family of networks had few triads that violated triadic closure (triad #6). Finally networks analyzing languages showed that the triads 7 -13 were underrepresented compared to a random graph, possibly because of the way words belong to certain categories and meaningful clauses have words from many categories.

Other than providing a useful way to describe the structure of networks, this paper also discusses how the timescale the network must respond on influences the structure of the network. This addresses the question asked in lecture about how response times might affect how clusters form. In bacteria where the signal process time must be on the order of minutes, the network is cascade adverse as this passing of information over many steps is not as efficient as a direct path. These networks can be characterized as a “rate limited network” because the response rate of the individual components is on the order of the desired response time of the entire network. In contrast, when the network is describing a higher level organism such as the synaptic connections between neurons, the speed at which the individual components work is much greater than the response time of the overall network. We therefore see more feedback loops and cascade elements. The languages and social structures are more networks of association, independent of time, and therefore have the more heavily linked structures. The paper suggests using higher order subgraph profiles, but I think the triad description is illuminating by itself. This technique of analyzing a network might also be used in reverse to design a large network: instead of generating a graph with random connections you might bias the connections so that certain triads formed. This might lead to a network that behaves more like a rate limited network or the other sorts discussed.

If you are interested in how to analyze the structure of a large network for your class paper, this short but fascinating paper might be a good resource for you.