Network Motif Discovery
A network motif of a graph G is a subgraph of G that appears signiﬁcantly more
than expected in G. Formally, network motif is a subgraph that exists with a much
higher frequency in G than expected in a similar random graph to G. A motif of
size k is called a k-motif. Milo et. al. were ﬁrst to discover these over-represented
subgraphs in the networks they studied and proposed the network motifs as the basic
building blocks of complex networks . Several motifs have been shown to have
functional signiﬁcance in biological networks such as the PPI networks  and the
gene regulating networks  some of which are shown in Figure 9.1.
The feed-forward loop motif for example, was shown to have information ﬁl-
tering capabilities during the gene regulation process. Network motifs may exist in
undirected graphs as in the PPI networks or in directed graphs such as the gene-
regulating networks. Network motif search is NP-hard, and therefore heuristic al-
gorithms are frequently used. This problem is closely related to the subgraph iso-
morphism where we search the isomorphic occurrences of a small graph in a large
In this chapter, we ﬁrst describe the network motifs in detail and analyze metrics
for their signiﬁcance. We then look into the related problem of subgraph isomor-
phism and describe fundamental algorithms that are used for subgraph isomorphism.
However, network motif discovery is not only ﬁnding an isomorphic subgraph of a
graph as we need to asses the number of occurrences of this subgraph to consider it
as a motif. In other words, we need to ﬁnd all occurrences of the motif. Finding all
existing motifs of a given size is called census and we investigate exact and approxi-
mate census algorithms in Section 1.4.