dorsal/arxiv
View SchemaGraph animals, subgraph sampling and motif search in large networks
| Authors | Kim Baskerville, Peter Grassberger, Maya Paczuski |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0702029 |
| URL | https://arxiv.org/abs/q-bio/0702029 |
| DOI | 10.1103/PhysRevE.76.036107 |
Abstract
We generalize a sampling algorithm for lattice animals (connected clusters on a regular lattice) to a Monte Carlo algorithm for `graph animals', i.e. connected subgraphs in arbitrary networks. As with the algorithm in [N. Kashtan et al., Bioinformatics 20, 1746 (2004)], it provides a weighted sample, but the computation of the weights is much faster (linear in the size of subgraphs, instead of super-exponential). This allows subgraphs with up to ten or more nodes to be sampled with very high statistics, from arbitrarily large networks. Using this together with a heuristic algorithm for rapidly classifying isomorphic graphs, we present results for two protein interaction networks obtained using the TAP high throughput method: one of Escherichia coli with 230 nodes and 695 links, and one for yeast (Saccharomyces cerevisiae) with roughly ten times more nodes and links. We find in both cases that most connected subgraphs are strong motifs (Z-scores >10) or anti-motifs (Z-scores <-10) when the null model is the ensemble of networks with fixed degree sequence. Strong differences appear between the two networks, with dominant motifs in E. coli being (nearly) bipartite graphs and having many pairs of nodes which connect to the same neighbors, while dominant motifs in yeast tend towards completeness or contain large cliques. We also explore a number of methods that do not rely on measurements of Z-scores or comparisons with null models. For instance, we discuss the influence of specific complexes like the 26S proteasome in yeast, where a small number of complexes dominate the $k$-cores with large k and have a decisive effect on the strongest motifs with 6 to 8 nodes. We also present Zipf plots of counts versus rank. They show broad distributions that are not power laws, in contrast to the case when disconnected subgraphs are included.
{
"annotation_id": "586aadd4-9fce-434a-964e-bd213a0bb2cd",
"date_created": "2026-03-02T18:01:35.859000Z",
"date_modified": "2026-03-02T18:01:35.859000Z",
"file_hash": "70bacb8e8f446064d86e903979b8e5cae776c8e52bd4b4f947a5e17da6b5e1ce",
"private": false,
"record": {
"abstract": "We generalize a sampling algorithm for lattice animals (connected clusters on\na regular lattice) to a Monte Carlo algorithm for `graph animals\u0027, i.e.\nconnected subgraphs in arbitrary networks. As with the algorithm in [N. Kashtan\net al., Bioinformatics 20, 1746 (2004)], it provides a weighted sample, but the\ncomputation of the weights is much faster (linear in the size of subgraphs,\ninstead of super-exponential). This allows subgraphs with up to ten or more\nnodes to be sampled with very high statistics, from arbitrarily large networks.\nUsing this together with a heuristic algorithm for rapidly classifying\nisomorphic graphs, we present results for two protein interaction networks\nobtained using the TAP high throughput method: one of Escherichia coli with 230\nnodes and 695 links, and one for yeast (Saccharomyces cerevisiae) with roughly\nten times more nodes and links. We find in both cases that most connected\nsubgraphs are strong motifs (Z-scores \u003e10) or anti-motifs (Z-scores \u003c-10) when\nthe null model is the ensemble of networks with fixed degree sequence. Strong\ndifferences appear between the two networks, with dominant motifs in E. coli\nbeing (nearly) bipartite graphs and having many pairs of nodes which connect to\nthe same neighbors, while dominant motifs in yeast tend towards completeness or\ncontain large cliques. We also explore a number of methods that do not rely on\nmeasurements of Z-scores or comparisons with null models. For instance, we\ndiscuss the influence of specific complexes like the 26S proteasome in yeast,\nwhere a small number of complexes dominate the $k$-cores with large k and have\na decisive effect on the strongest motifs with 6 to 8 nodes. We also present\nZipf plots of counts versus rank. They show broad distributions that are not\npower laws, in contrast to the case when disconnected subgraphs are included.",
"arxiv_id": "q-bio/0702029",
"authors": [
"Kim Baskerville",
"Peter Grassberger",
"Maya Paczuski"
],
"categories": [
"q-bio.MN",
"cond-mat.stat-mech",
"physics.bio-ph"
],
"doi": "10.1103/PhysRevE.76.036107",
"title": "Graph animals, subgraph sampling and motif search in large networks",
"url": "https://arxiv.org/abs/q-bio/0702029"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a27cee3e-1483-437b-8115-3ea07ba70299",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}