Large-scale network motif analysis using compression

Abstract

We introduce a new method for finding network motifs: interesting or informative subgraph patterns in a network. 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 (MDL) 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.

References in corpus (5)

• An information-theoretic framework for resolving community structure in complex networks
• The Babe Ruth Algorithm: a fast, unbiased procedure to randomize presence-absence data matrices with fixed row and column totals
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts
• A tutorial on MDL hypothesis testing for graph analysis

Cited by in corpus (6)

• The Minimum Description Length Principle for Pattern Mining: A Survey
• Compressing network populations with modal networks reveals structural diversity
• Compression-based inference of network motif sets
• Partition and Code: learning how to compress graphs
• Finding Motifs in Knowledge Graphs using Compression
• A Neighborhood-preserving Graph Summarization