An example of a graph with 10 nodes where most nodes are removable. A and B can be removed by all other nodes; C can be removed by D–J; D can be removed by E, H, and I; E can be removed by H; F can be removed by G–I; G can be removed by H; H cannot be removed; I can be removed by H; and J can be removed by E and G–I. The graph can be reduced to a single node.

Complexity of likelihood recursion. (Upper) The logarithm of the number of recursive calls made when calculating the likelihood of a graph with Eq. 1 and a library for storing already computed likelihoods of subgraphs for different parameter values. Index 1: θ = (π, p, q, r) = (0,0,0,0.25); index 2: (0,0,0,0.5); index 3: (0,0,0,0.75); index 4: (0.5,0.25,0.5,0.5); index 5: (0.5,0.5,0.5,0.5); index 6: (0.5,0.75,0.5,0.5); index 7: (1,0.25,0.5,0); index 8: (1,0.5,0.5,0); and index 9: (1,0.75,0.5,0). Index 10 shows the log of the number of calls for a complete graph or a graph with no links at all. This number is log_e(t2^t−1 − t + 1), where t is number of nodes. t = 5 nodes (blue), 10 nodes (green), 15 nodes (red), and 20 nodes (purple). The average over 30 random graphs was computed for each value of t and θ, and all graphs were generated from a single node. (Lower) Shown is the log of the library size when calculating the same likelihood as in Upper. The number for index 10 is log_e(2^t − 1).

Likelihood curve for the graph in Fig. 1 for variable p, but with all other parameters fixed to the true values. The graph is generated with parameter θ = (1,0.66,0.33,0). (Upper) The likelihood curve is calculated by using IS with driving value θ₀ = θ, i.e., p₀ = 0.66. The average over several paths is computed. n = 10 paths (light blue), 100 paths (blue), 1,000 paths (green), and 10,000 paths (red). For 100,000 the curve is almost impossible to distinguish from the true likelihood curve that is shown in black. (Lower) Here the driving value is θ₀ = (1,0.33,0.33,0), i.e., p₀ = 0.33. The average over several paths is computed. n = 10 paths (light blue), 100 paths (blue), 1,000 (green), and 10,000 (red). For 100,000 the curve is almost impossible to distinguish from the true likelihood curve that is shown in black.

Shown is the likelihood curve (in units of thousands) of the C. elegans data set of 2,368 nodes. After removing all removable nodes the graph comprises 735 nodes. The likelihood curve was generated by using 1,000 paths and driving value θ = (1,0.66,0.33,0). All parameters but p were fixed: π = 1, q = 0.33, and r = 0. Average of 10 paths (blue), 100 paths (green), and 1,000 paths (red). Each path took ≈400 central processing unit sec on our machine.

Shown is the degree distribution of the full C. elegans data set (Upper) and the reduced data set (Lower). Both data sets look like the degree distribution can be described by a power law with coefficient ≈2. In the full data set there are no nodes of degree 0 because the network is connected, and in the reduced data set there are no nodes of degrees 0 and 1, because they can always be removed.