text: Let  and  be two graphs. Graph  is a sub-graph of graph  (written as ) if  and . If  and  contains all of the edges   with , then  is an induced sub-graph of . We call  and  isomorphic (written as ), if there exists a bijection (one-to-one correspondence)  with   for all . The mapping  is called an isomorphism between  and .
  When  and there exists an isomorphism between the sub-graph  and a graph , this mapping represents an appearance of  in . The number of appearances of graph  in   is called the frequency  of  in . A graph is called recurrent (or frequent) in  when its frequency  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  of random graphs corresponding to the null-model associated to . We should choose  random graphs uniformly from   and calculate the frequency for a particular frequent sub-graph  in . If the frequency of  in  is higher than its arithmetic mean frequency in  random graphs , where , we call this recurrent pattern significant and hence treat  as a network motif for . For a small graph , the network , and a set of randomized networks , where , the Z-score of the frequency of  is given by
  where  and  stand for the mean and standard deviation of the frequency in set , respectively. The larger the , the more significant is the sub-graph  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   (as its null-hypothesis), where   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  is defined as
  where  indicates the number of randomized networks,  is defined over an ensemble of randomized networks, and the Kronecker delta function  is one if the condition  holds. The concentration of a particular n-size sub-graph  in network  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
  where index  is defined over the set of all non-isomorphic n-size graphs. Another statistical measurement is defined for evaluating network motifs, but it is rarely used in known algorithms. This measurement is introduced by Picard et al. in 2008 and used the Poisson distribution, rather than the Gaussian normal distribution that is implicitly being used above.
  In addition, three specific concepts of sub-graph frequency have been proposed. As the figure illustrates, the first frequency concept  considers all matches of a graph in original network. This definition is similar to what we have introduced above. The second concept  is defined as the maximum number of edge-disjoint instances of a given graph in original network. And finally, the frequency concept  entails matches with disjoint edges and nodes. Therefore, the two concepts  and  restrict the usage of elements of the graph, and as can be inferred, the frequency of a sub-graph declines by imposing restrictions on network element usage. As a result, a network motif detection algorithm would pass over more candidate sub-graphs if we insist on frequency concepts  and .