Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequences

The simplest null models for networks, used to distinguish significant features of a particular network from a priori expected features, are random ensembles with the degree sequence fixed by the specific network of interest. These “fixed degree sequence” (FDS) ensembles are, however, famously resistant to analytic attack. In this paper we introduce ensembles with partially-fixed degree sequences (PFDS) and compare analytic results obtained for them with Monte Carlo results for the FDS ensemble. These results include link likelihoods, subgraph likelihoods, and degree correlations. We find that local structural features in the FDS ensemble can be reasonably well estimated by simultaneously fixing only the degrees of a few nodes, in addition to the total number of nodes and links. As test cases we use two protein interaction networks (Escherichia coli, Saccharomyces cerevisiae), the internet on the autonomous system (AS) level, and the World Wide Web. Fixing just the degrees of two nodes gives the mean neighbor degree as a function of node degree, ${⟨k^{\prime }⟩}_k$, in agreement with results explicitly obtained from rewiring. For power law degree distributions, we derive the disassortativity analytically. In the PFDS ensemble the partition function can be expanded diagrammatically. We obtain an explicit expression for the link likelihood to lowest order, which reduces in the limit of large, sparse undirected networks with $L$ links and with $k_{\max }⪡L$ to the simple formula $P(k,k^{\prime })=k{k}^{\prime }∕(2L+k{k}^{\prime })$. In a similar limit, the probability for three nodes to be linked into a triangle reduces to the factorized expression $P_{\Delta }(k_1,k_2,k_3)=P(k_1,k_2)P(k_1,k_3)P(k_2,k_3)$.

Figure 1

(Color online) Log-log scatter plot of the naive analytic estimate of link likelihood $k_{\mathit{\text{out}},i}{k}_{\mathit{\text{in}},j}∕L$ (directed network, St. Martin foodweb [37]) or $k_i{k}_j∕2L$ (undirected network, Escherichia coli protein interaction network [38]) versus the ratio of the Monte Carlo rewiring estimate to the naive estimate for the corresponding nodes. Note that the directed network has considerably more scatter for given $k_{\mathit{\text{out}},i},k_{\mathit{\text{in}},j}$.

Figure 2

(Color online) Average degree of the neighbor ${⟨k^{\prime }⟩}_k$ vs node degree $k$ for an Escherichia coli protein interaction network [38] in several ensembles. The FDS ensemble, sampled by Monte Carlo rewiring, shows disassortativity as ${⟨k^{\prime }⟩}_k$ is a decreasing function of $k$. For the naive estimate $p_{ij}=k_i{k}_j∕2L$ and using the exact degree sequence, there is no disassortativity [while using a power law as in Eq. (10) leads to divergence]. However, using the naive estimate but forbidding self-connection results in slight disassortativity. Approximate $Z_3$, exact $Z_3$, and $Z_4(k_1,k_2,k_{\max })$ are increasingly refined estimates of the FDS ensemble. Notice that the latter two can hardly be distinguished.

Figure 3

(Color online) ${⟨k^{\prime }⟩}_k$ versus $k$ for the Internet at the AS level from [39]. We plot the analytic estimate of Eq. (11) for $\gamma =2.3$; for comparison we plot the results in the approximate $Z_3$ and $Z_3$ ensembles, computed directly from the degree sequence of [39], as well as Monte Carlo rewiring estimates of the FDS ensemble.

Figure 4

Schematic decomposition of the adjacency matrix $\mathcal{M}$ into the three submatrices $\mathcal{A}$, $B$, $C$ discussed in the text. Note that $\mathcal{M}$ is symmetric for undirected networks.

Figure 5

Diagrammatic expansion for the connected (a) and disconnected (b) contributions to the partition function $Z_4$ for $p_{12}$.

Figure 6

(Color online) Scatter plot comparing estimates of the link likelihood in an Escherichia coli protein interaction network. On the horizontal logarithmic axis we plot the naive estimate $\frac{k_i{k}_j}{2L}$; on the vertical logarithmic axis we plot for all corresponding nodes the ratio of the Monte Carlo rewiring estimate to the naive, $Z_3$ (no hub), and $Z_4$ (one hub) estimates. The latter two nearly coincide.

Figure 7

(Color online) Correlation profile $R_{Z_3\mid \mathrm{FDS}}(k,k^{\prime })$ for the Escherichia coli protein interaction network [38]. Note that the dark regions (blue online) are artificially set to the value .7; they correspond to values of $(k,k^{\prime })$ for which no data exist.