The processes that generate the real world networks we are likely to analyze, produce characteristic signatures in the topology of networks. Common patterns in graphs are known as Network Motifs and can provide important information about the structure of our network and the process that generated it.
In this post we introduce the ESU algorithm to enumerate all the subgraphs of a network with a specific number of nodes and how we can use it to calculate the frequency of each network motif.
Network Motifs
The networks we encounter in the real world are produced as the result of some natural or artificial process. The details of these processes can result in specific signatures within the structure of the graphs they produce.
To make this point clear, let us consider a simple example of just 3 nodes. There’s only two possible ways to connected 3 nodes among themselves in a way that results in a connected graph, namely:
