| Abstract |
Network motif analysis is a form of pattern mining on graphs. It searches for subgraphs that are unexpectedly frequent with respect to a null model. To compute the expected frequency of the subgraph, the search for motifs is normally repeated on as many as 1000 random graphs sampled from the null model, a costly step. We've developed a method to avoid this step that limits motif analysis to graphs of around 10000 links. We've developed an approximation that avoids the graph samples and computes motif significance efficiently, allowing us to perform motif detection on graphs with billions of links, using commodity hardware. |