    Next: Graph Transformation Method Up: ENSEMBLES OF REARRANGEMENT PATHWAYS Previous: Chain Graphs   Contents

# Complete Graphs

In a complete digraph each pair of nodes is connected by two oppositely directed edges . The complete graph with graph nodes is denoted , and has nodes and edges, remembering that we have two edges per connection (Figure 4.4). Due to the complete connectivity we need only consider two cases: when the starting and finishing nodes are the same and when they are distinct. We employ complete graphs for the purposes of generality. An arbitrary graph is a subgraph of with transition probabilities for non-existent edges set to zero. All the results in this section are therefore equally applicable to arbitrary graphs.

The complete graph will not be considered here as it is topologically identical to the graph . The difference between the and graphs is the existence of edges that connect nodes and . Pathways confined to can therefore contain cycles, and for a given path length they are significantly more numerous (Figure 4.5). The can again be derived analytically for this graph: (6.30)

The results for any other possibility can be obtained by permuting the node indices appropriately.

The pathway sums for larger complete graphs can be obtained by recursion. For any path leaving from and returning to can be broken down into a step out of to any , all possible paths between and within , and finally a step back to from . All such paths can be combined together in any order, so we have a multinomial distribution : (6.31)

To evaluate we break down the sum into all paths that depart from and return to , followed by all paths that leave node and reach node 1 without returning to . The first contribution corresponds to a factor of , and the second produces a factor for every : (6.32)

where is defined to be unity. Any other can be obtained by a permutation of node labels.

Algorithm B.2 provides an example implementation of the above formulae optimised for incomplete graphs. The running time of Algorithm B.2 depends strongly on the graph density. (A digraph in which the number of edges is close to the maximum value of is termed a dense digraph .) For the algorithm runs in time, while for an arbitrary graph it scales as , where is the average degree of the nodes. For chain graphs the algorithm runs in time and therefore constitutes a recursive-function-based alternative to Algorithm B.1 with linear memory requirements. For complete graphs an alternative implementation with scaling is also possible.

Although the scaling of the above algorithm with may appear disastrous, it does in fact run faster than standard KMC and MM approaches for graphs where the escape probabilities are several orders of magnitude smaller than the transition probabilities (Algorithm B.2). Otherwise, for anything but moderately branched chain graphs, Algorithm B.2 is significantly more expensive. However, the graph-transformation-based method presented in Section 4.4 yields both the pathway sums and the mean escape times for a complete graph in time, and is the fastest approach that we have found.

Mean escape times for are readily obtained from the results in Equation 4.30 by applying the method outlined in Section 4.1.5: (6.33)

We have verified this result analytically using first-step analysis and numerically for various values of the parameters and . and obtained quantitative agreement (see Figure 4.6). Figure 4.7 demonstrates how the advantage of exact summation over KMC and MM becomes more pronounced as the escape probabilities become smaller.     Next: Graph Transformation Method Up: ENSEMBLES OF REARRANGEMENT PATHWAYS Previous: Chain Graphs   Contents
Semen A Trygubenko 2006-04-10