Network motif

Network motifs are recurrent and statistically significant subgraphs or patterns of a larger graph. All networks, including biological networks, social networks, technological networks (e.g., computer networks and electrical circuits) and more, can be represented as graphs, which include a wide variety of subgraphs. Network motifs are sub-graphs that repeat themselves in a specific network or even among various networks. Each of these sub-graphs, defined by a particular pattern of interactions between vertices, may reflect a framework in which particular functions are achieved efficiently. Indeed, motifs are of notable importance largely because they may reflect functional properties. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Although network motifs may provide a deep insight into the network's functional abilities, their detection is computationally challenging.

Definitions Let G = (V, E) and G′ = (V′, E′) be two graphs. Graph G′ is a sub-graph of graph G (written as G′ ⊆ G) if V′ ⊆ V and E′ ⊆ E ∩ (V′ × V′). If G′ ⊆ G and G′ contains all of the edges ⟨u, v⟩ ∈ E with u, v ∈ V′, then G′ is an induced sub-graph of G. We call G′ and G isomorphic (written as G′ ↔ G), if there exists a bijection (one-to-one correspondence) f:V′ → V with ⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E for all u, v ∈ V′. The mapping f is called an isomorphism between G and G′. When G″ ⊂ G and there exists an isomorphism between the sub-graph G″ and a graph G′, this mapping represents an appearance of G′ in G. The number of appearances of graph G′ in G is called the frequency FG of G′ in G. A graph is called recurrent (or frequent) in G when its frequency FG(G′) is above a predefined threshold or cut-off value. We use terms pattern and frequent sub-graph in this review interchangeably. There is an ensemble Ω(G) of random graphs corresponding to the null-model associated to G. We should choose N random graphs uniformly from Ω(G) and calculate the frequency for a particular frequent sub-graph G′ in G. If the frequency of G′ in G is higher than its arithmetic mean frequency in N random graphs Ri, where 1 ≤ i ≤ N, we call this recurrent pattern significant and hence treat G′ as a network motif for G. For a small graph G′, the network G, and a set of randomized networks R(G) ⊆ Ω(R), where R(G) = N, the Z-score of the frequency of G′ is given by

Z ( G ′ ) = F G ( G ′ ) − μ R ( G ′ ) σ R ( G ′ ) {\displaystyle Z(G^{\prime })={\frac {F_{G}(G^{\prime })-\mu _{R}(G^{\prime })}{\sigma _{R}(G^{\prime })}}}

where μR(G′) and σR(G′) stand for the mean and standard deviation of the frequency in set R(G), respectively. The larger the Z(G′), the more significant is the sub-graph G′ as a motif. Alternatively, another measurement in statistical hypothesis testing that can be considered in motif detection is the p-value, given as the probability of FR(G′) ≥ FG(G′) (as its null-hypothesis), where FR(G′) indicates the frequency of G' in a randomized network. A sub-graph with p-value less than a threshold (commonly 0.01 or 0.05) will be treated as a significant pattern. The p-value for the frequency of G′ is defined as

P ( G ′ ) = 1 N ∑ i = 1 N δ ( c ( i ) ) c ( i ) : F R i ( G ′ ) ≥ F G ( G ′ ) {\displaystyle P(G^{\prime })={\frac {1}{N}}\sum _{i=1}^{N}\delta (c(i))\quad c(i):F_{R}^{i}(G^{\prime })\geq F_{G}(G^{\prime })}

where N indicates the number of randomized networks, i is defined over an ensemble of randomized networks, and the Kronecker delta function δ(c(i)) is one if the condition c(i) holds. The concentration of a particular n-size sub-graph G′ in network G refers to the ratio of the sub-graph appearance in the network to the total n-size non-isomorphic sub-graphs' frequencies, which is formulated by

C G ( G ′ ) = F G ( G ′ ) ∑ i F G ( G i ) {\displaystyle C_{G}(G^{\prime })={\frac {F_{G}(G^{\prime })}{\sum _{i}F_{G}(G_{i})}}}

… excerpt ends here. Continue reading the full article.