dorsal/arxiv
View SchemaSubgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
| Authors | Kim Baskerville, Maya Paczuski |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0606023 |
| URL | https://arxiv.org/abs/q-bio/0606023 |
| DOI | 10.1103/PhysRevE.74.051903 |
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\leq 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.
{
"annotation_id": "f40b4084-e2e1-483c-9b9e-c9617d9d96f8",
"date_created": "2026-03-02T18:01:35.337000Z",
"date_modified": "2026-03-02T18:01:35.337000Z",
"file_hash": "d867bdfdbb4905e745fcf939be4a7c1c8745748a0815ed489c5d1e15bad30272",
"private": false,
"record": {
"abstract": "A new heuristic based on vertex invariants is developed to rapidly\ndistinguish non-isomorphic graphs to a desired level of accuracy. The method is\napplied to sample subgraphs from an E.coli protein interaction network, and as\na probe for discovery of extended motifs. The network\u0027s structure is described\nusing statistical properties of its $N$-node subgraphs for $N\\leq 14$. The Zipf\nplots for subgraph occurrences are robust power laws that do not change when\nrewiring the network while fixing the degree sequence -- although the specific\nsubgraphs may exchange ranks. However the exponent depends on $N$. The study of\nlarger subgraphs highlights some striking patterns for various $N$. Motifs, or\nconnected pieces that are over-abundant in the ensemble of subgraphs, have more\nedges, for a given number of nodes, than antimotifs and generally display a\nbipartite structure or tend towards a complete graph. In contrast, antimotifs,\nwhich are under-abundant connected pieces, are mostly trees or contain at most\na single, small loop. The extension to directed graphs is straightforward.",
"arxiv_id": "q-bio/0606023",
"authors": [
"Kim Baskerville",
"Maya Paczuski"
],
"categories": [
"q-bio.QM",
"cond-mat.stat-mech",
"q-bio.MN"
],
"doi": "10.1103/PhysRevE.74.051903",
"title": "Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism",
"url": "https://arxiv.org/abs/q-bio/0606023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b3d8b77b-270a-42a3-a029-e31380f204fa",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}