Subgraph fluctuations in random graphs

The pattern of over- and under-representations of three-node subgraphs has become a standard method of characterizing complex networks and evaluating how this intermediate level of organization contributes to network function. Understanding statistical properties of subgraph counts in random graphs, their fluctuations, and their interdependences with other topological attributes is an important prerequisite for such investigations. Here we introduce a formalism for predicting subgraph fluctuations induced by perturbations of unidirectional and bidirectional edge densities. On this basis we predict the over- and under-representation of subgraphs arising from a density mismatch between a network and the corresponding pool of randomized graphs serving as a null model. Such mismatches occur, for example, in modular and hierarchical graphs.

Figure 1

The three different placements for the three possible types of edges. Shown on the right are the different types of edges that can occupy the placements and their notation for templates and subgraphs.

Figure 2

Probabilities $p_n$ (red solid line), $p_u$ (blue dotted line), and $p_b$ (green dashed line) as functions of the edge density $p$.

Figure 3

To illustrate the prediction quality of the subgraph counts we show the predicted (full curve) and numerically observed (dots) counts of the first six three-node subgraphs in a random network with $N=100$. The connectivity is varied over the whole range ($p=0-100\%$). The numerical points are obtained by averaging over 100 random graphs. The subgraphs, together with their IDs, are indicated above each plot. The figures for the full 13 motifs are available in Ref. [27].

Figure 4

Fluctuations of the number of unidirectional and bidirectional edges in a random graph with $N=100$ nodes and varying edge density. We show the numerical results together with the corresponding predictions.

Figure 5

Fluctuations of the first six three-node subgraphs in a random network with $N=100$. The connectivity is varied over the whole range ($p=0-100\%$) and contribution (i) (orange dashed line), contribution (ii) (green dotted line), the total expected value (red solid line), and numerical results (blue dots) are shown. The subgraphs, together with their IDs, are indicated above each plot. The figures for the full 13 motifs are available in Ref. [27].

Figure 6

Motif $z$ scores for a network that is composed of five strong modules. (a) Example of such a random modular graph. Two different randomization schemes are applied: (1) simple flipping of two-edge end points and (2) flipping while preserving the module structure. As the analyzed network is random apart from its modularity the z-score using the correct randomization scheme must be 0. This is shown for different densities: (b) $N=500,M=2000,\mathrm{and}\rho =0.08$ and (c) $N=500,M=8000,\mathrm{and}\rho =0.16$.

Figure 7

Composition of the first six three-node subgraphs in a modular network. The ratio of intermodular edges is varied over the whole range and the contribution of intramodule subgraphs (orange dotted line), intermodule subgraphs (green dashed line), mixed subgraphs (blue dot-dashed line), the total expected value (red solid line), and numerical results (blue dots) are shown ($N=500$ and $M=2000$). The subgraphs, together with their IDs, are indicated above each plot. The figures for the full 13 motifs are available in Ref. [27].

Figure 8

Sum over the squared errors that occurs from applying different randomization schemes over the ratio of intermodule edges ($N=500$ and $M=2000$). We show the numerical results for two different randomization schemes together with our prediction.