Title: Finding Network Motifs in Large Graphs using Compression as a Measure of Relevance,
Abstract: We introduce a new method for finding network motifs: interesting or
informative subgraph patterns in a network. Current methods for finding motifs
rely on the frequency of the motif: specifically, subgraphs are motifs when
their frequency in the data is high compared to the expected frequency under a
null model. To compute this expectation, the search for motifs is normally
repeated on as many as 1000 random graphs sampled from the null model; a
prohibitively expensive step. We use ideas from the Minimum Description Length
(MDL) literature to define a new measure of motif relevance, and a new
algorithm for detecting motifs. Our method allows motif analysis to scale to
networks with billions of links, while still resulting in informative motifs.