Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism

Abstract

A new heuristic based on vertex invariants is developed to rapidly distinguish non-isomorphic graphs to a desired level of accuracy. The method is applied to sample subgraphs from an E.coli protein interaction network, and as a probe for discovery of extended motifs. The network's structure is described using statistical properties of its $N$-node subgraphs for $N\le 14$. The Zipf plots for subgraph occurrences are robust power laws that do not change when rewiring the network while fixing the degree sequence -- although the specific subgraphs may exchange ranks. However the exponent depends on $N$. The study of larger subgraphs highlights some striking patterns for various $N$. Motifs, or connected pieces that are over-abundant in the ensemble of subgraphs, have more edges, for a given number of nodes, than antimotifs and generally display a bipartite structure or tend towards a complete graph. In contrast, antimotifs, which are under-abundant connected pieces, are mostly trees or contain at most a single, small loop. The extension to directed graphs is straightforward.

13 pages, 14 figures

References in corpus (10)

• Emergence of scaling in random networks
• The large-scale organization of metabolic networks
• Classes of behavior of small-world networks
• Specificity and stability in topology of protein networks
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Local graph alignment and motif search in biological networks
• Subgraphs in random networks
• Inferring Network Mechanisms: The Drosophila melanogaster Protein Interaction Network
• Topological Generalizations of network motifs
• Systematic identification of statistically significant network measures

Cited by in corpus (7)

• Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
• Dynamics and Processing in Finite Self-Similar Networks
• Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence
• Graph animals, subgraph sampling and motif search in large networks
• Subgraph Counting: Color Coding Beyond Trees
• Revealing effective classifiers through network comparison
• One Node at a Time: Node-Level Network Classification