Edited by David O. Siegmund, Stanford University, Stanford, CA, and approved March 31, 2006 (received for review January 4, 2006)
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 loge(t2t−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 loge(2t − 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 θ0 = θ, i.e., p0 = 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 θ0 = (1,0.33,0.33,0), i.e., p0 = 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.
|
Wiuf et al. 10.1073/pnas.0600061103. |
Supporting Text
Supporting Figure 6
Fig. 6. Shown are average run times for a single path by using importance sampling. Graphs with different number of nodes were generated with parameter q = (1, 0.66, 0.33, 0) (white) or (1, 0.33, 0.33, 0) (black), and a path was drawn 15 times using driving value, q0 = q . The average was computed and plotted. Number of nodes: n = 50, 100, 200, 1,000, and 2,000. The observed run times are approximately O(n2.34) and O(n2.84), respectively.
