Graph animals, subgraph sampling, and motif search in large networks

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 superexponential). 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 tandem affinity purification (TAP) 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 antimotifs ($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 that 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–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.

Figure 1

(Color online) Root mean square relative errors of connected subgraph counts, Eq. (10), for the yeast ($n=5$ to $8$) and E. coli $(n=7)$ networks. In most cases, clear minima indicate roughly the optimum value for $p$, with caveats as explained in the text. Each data point is based on $4\times {10}^9$ generated subgraphs. Smaller values of ${\sigma }_n\left(p\right)$ indicate that the census for subgraphs with $n$ nodes is on average more precise.

Figure 2

(Color online) Histograms of $wP\left(\ln w\right)=w^{2}P\left(w\right)$ for connected $n=8$ subgraphs of the yeast network. Each curve corresponds to one run ($4\times {10}^9$ generated subgraphs) with a fixed value of $p$, with $p$ increasing from the lower curves to the higher ones. Results are more reliable, the further to the left the maximum of the curve is and the faster the decrease of its tail at large $w$ is.

Figure 3

(Color online) Scatter plots of ${\widehat{c}}_G(p=0.025)$ and ${\widehat{c}}_G(p=0.07)$ against ${\widehat{c}}_G(p=0.04)$ for connected $n=8$ subgraphs of the yeast network. The clustering of the data along the diagonal indicates the basic reliability of the estimates, independent of the precise choice of $p$. Sample sizes were $4\times {10}^{10}$ for $p=0.04$, $2.4\times {10}^{10}$ for $p=0.025$, and $8\times {10}^9$ for $p=0.07$. The latter two correspond to roughly the same CPU time.

Figure 4

(Color online) Average clustering coefficients for nodes with fixed degree $k$ plotted versus the degree, for the giant component of the yeast and E. coli protein interaction networks. While the clustering coefficient decreases with $k$ for E. coli, it attains a maximum at $k\approx 15$ for yeast.

Figure 5

(Color online) Sizes of the $k$ cores for the two networks, plotted against $k$. Notice that the $k$ cores for yeast contain a nearly fully connected cluster with 17 nodes. In addition to the core sizes for the original networks, the figure also shows average core sizes for rewired networks as discussed in Sec. 5C.

Figure 6

(Color online) Counts for connected subgraphs with fixed topology and with $n\le 8$ in the E. coli network, plotted against $n^2+2\ell$. The variable $n^2+2\ell$ is used to spread out the data, so that the dependence on both $n$ and $\ell$ (number of links) can be seen independently, without data points overlapping. For most of the points, the error bars are smaller than the sizes of the symbols.

Figure 7

(Color online) Counts for subgraphs with fixed topology and with $n\le 8$ in the yeast network, plotted against $n^2+2\ell$ as in Fig. 6.

Figure 8

(Color online) Counts for $n=8$ subgraphs of the yeast network with $\ell =7$, 10, 13, and $18$, plotted against the variance of the node degrees within the subgraphs, as given by Eq. (14). Zero variance means that all nodes have exactly the same degree, whereas a higher variance indicates that the nodes differ more widely. Typically, subgraphs with more variation in their nodes (and thus with larger ${\sigma }^2$) have higher counts than those for which the degrees within the subgraph are more uniform.

Figure 9

(Color online) “Zipf” plots showing the counts for individual connected subgraphs with fixed $n$, plotted against their rank. Data are for the E. coli network.

Figure 10

(Color online) Ratios between the count estimates ${\widehat{c}}_G$ for connected subgraphs in the E. coli network, and the corresponding average counts $⟨{\widehat{c}}_G^{\left(0\right)}⟩$ in rewired networks. The data are plotted against $n^2+2\ell$, again to spread the points out conveniently. Most error bars are smaller than the symbols.

Figure 11

(Color online) Same as Fig. 10, but for the yeast network. Notice that most data points for large $n$ and $\ell$ are missing. Indeed, for $n=7$ all (!) data points with $\ell >16$ are missing, because no such subgraphs were found in the rewired ensemble.

Figure 12

The eight strongest motifs with $n=7$ in the E. coli protein interaction network. These tend to be almost bipartite graphs, and many pairs of nodes are linked to the same set of neighbors. Their $Z$ scores, in order from left to right, first then second row, are $2.9\times {10}^4$, 932, 885, 648, 595, 532, 516, and 377. Their estimated frequencies in the original E. coli network are, in the same order: $20936\pm 8$, $161521\pm 63$, $8312\pm 5$, $1331\pm 2$, $838\pm 2$, $5985\pm 5$, $5165\pm 4$, and $519\pm 1$.

Figure 13

Eight very strong motifs with $n=7$ for the yeast protein interaction network. These tend to be almost complete graphs with a single dangling node. Four of these graphs were not seen in any realization of the null model, so only lower bounds on their $Z$ scores can be given. From left to right, first then second row, the estimated $Z$ scores are $>3\times {10}^7$, $9\times {10}^5$, $>8\times {10}^6$, $5\times {10}^5$, $>4\times {10}^6$, $3\times {10}^5$, $2.5\times {10}^5$, and $>1.5\times {10}^6$. Estimated frequencies are, in the same order: $6.68\left(1\right)\times {10}^5$, $9.27\left(5\right)\times {10}^4$, $1.76\left(1\right)\times {10}^5$, $4.84\left(1\right)\times {10}^5$, $7.78\left(2\right)\times {10}^4$, $3.13\left(6\right)\times {10}^5$, $1.38\left(1\right)\times {10}^5$, and $3.35\left(1\right)\times {10}^4$.

Figure 14

(Color online) Count ratios $c_G∕⟨c_G^{\left(0\right)}⟩$ for individual subgraphs in the E. coli network, plotted against the count ratio for the same subgraph in the yeast network. To highlight the dependence on the number of twin nodes in the subgraph, subgraphs with $n_{\mathrm{twin}}>1(n_{\mathrm{twin}}>3)$ are marked by asterisks (bullets). Whereas almost all ratios are much higher in the yeast network, this is noticeably less true for subgraphs containing more than three pairs of twin nodes. These tend to fall on the diagonal indicated by the dashed line.

Figure 15

(Color online) Counts $c_G$, respectively, $⟨c_G^{\left(0\right)}⟩$ for individual subgraphs in the Escherichia coli network, plotted against counts for the same subgraph in the yeast network. It can be seen that the two rewired networks are much more similar (display higher correlation) than the original networks.

Figure 16

(Color online) Count ratios $c_G∕⟨c_G^{\left(0\right)}⟩$ for individual subgraphs in the yeast networks of Refs. 63, 64, plotted against counts for the same subgraph in the network of [47]. If all three networks were identical, all points should lie on the diagonal (indicated by the straight dashed line), whereas in fact systematic deviations are observed.