Statistical and Machine Learning Approaches for Network Analysis

2.8 Network Motif

The clustering property and hierarchical modularity indicates the organization of modules in real-world networks. However, the question is: How do we find such modules (building blocks) from real-world networks? Milo et al. [30] proposed a detection method for such modules.

It is expected that the modules and building blocks are not randomly constructed; thus, such modules are frequently observed to be more than those in random networks. For this reason, such subnetworks are referred to as “network motifs” [30,31]. Employing the above difference between real-world networks and random networks, we may find the modules.

This detection method focuses on the appearance frequencies of a given subnetwork (i.e., subgraph) in a real network and random networks, that is, F_real and F_rand, respectively. Random networks are generated from the real network by the randomization method, in which the terminals of two randomly selected edges are mutually exchanged at each time step: when the connected node pairs (i, j) and (m, n) are selected, we delete these edges and generate the newly connected pairs (i, n) and (m, j) (see Ref. [30] for details). We obtain the average F_rand and the standard deviation SD for F_rand from many randomized networks generated by the above procedure. The ...