Large-scale network motif analysis using compression

Data Mining and Knowledge Discovery, vol. 34, pp. 1421–1453

Abstract

Abstract We introduce a new method for finding network motifs . Subgraphs are motifs when their frequency in the data is high compared to the expected frequency under a null model . To compute this expectation, a full or approximate count of the occurrences of a motif 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 literature to define a new measure of motif relevance. With our method, samples from the null model are not required. Instead we compute the probability of the data under the null model and compare this to the probability under a specially designed alternative model. With this new relevance test, we can search for motifs by random sampling, rather than requiring an accurate count of all instances of a motif. This allows motif analysis to scale to networks with billions of links.

Authors 2

1. Peter Bloem corresponding

   Vrije Universiteit Amsterdam

   Affiliation as printed

   Department of Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

2. Steven de Rooij Aachen Mathematisch Instituut

   Leiden University

   Affiliation as printed

   Mathematisch Instituut, Leiden University, Leiden, The Netherlands