Subgraph Covers: An Information-Theoretic Approach to Motif Analysis in Networks

Phys. Rev. X 4, 041026 – Published 10 November 2014
Anatol E. Wegner

Abstract

Many real-world networks contain a statistically surprising number of certain subgraphs, called network motifs. In the prevalent approach to motif analysis, network motifs are detected by comparing subgraph frequencies in the original network with a statistical null model. In this paper, we propose an alternative approach to motif analysis where network motifs are defined to be connectivity patterns that occur in a subgraph cover that represents the network using minimal total information. A subgraph cover is defined to be a set of subgraphs such that every edge of the graph is contained in at least one of the subgraphs in the cover. Some recently introduced random graph models that can incorporate significant densities of motifs have natural formulations in terms of subgraph covers, and the presented approach can be used to match networks with such models. To prove the practical value of our approach, we also present a heuristic for the resulting NP hard optimization problem and give results for several real-world networks.

DOI: http://dx.doi.org/10.1103/PhysRevX.4.041026

  • Figure
  • Published 10 November 2014
  • Received 20 June 2014

This article is available under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Authors & Affiliations

Anatol E. Wegner*

  • Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 04103 Leipzig, Germany

  • *wegner@mis.mpg.de

Popular Summary

Many complex systems can be represented as networks of interacting elements, such as biological transcription in ensembles of cells. The connectivity structure of such systems can be represented as graphs. In some complex networks, certain connectivity patterns, called network motifs, appear much more frequently than is expected on the basis of pure chance. Network motifs, which are sometimes also referred to as basic building blocks of complex networks, are believed to play an important role in the structural and functional organization of networks.

We propose a new approach to motif analysis that is based on using subgraph covers as representations of graphs. A subgraph cover is essentially a decomposition of the graph into smaller building blocks. We define the motifs of a network to be connectivity patterns that occur in a subgraph cover that represents the network using minimal total information. The total information of a subgraph cover is the information required to describe the subgraph patterns occurring in the cover, as well as the configurations of the subgraphs in the subgraph cover. Finding a subgraph cover that minimizes the total information turns out to be a computationally difficult problem. Therefore, we propose a greedy heuristic that is based on constructing a subgraph cover incrementally. By analyzing several real-world networks from different fields, including networks representing the Internet and gene transcription, we find that networks representing the same kind of system also have very similar motif structures.

The method further enables networks to be fit to random graph models that incorporate network motifs, effectively leading to more accurate models.

Key Image

Subject Areas

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand

Authorization Required


×
×

Images

1 of 1
×

Log In

Cancel
×

Search


Article Lookup
Paste a citation or DOI

Enter a citation
×

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 3.0 License. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×