Next: Applications to Sparse Random Up: ENSEMBLES OF REARRANGEMENT PATHWAYS Previous: Complete Graphs   Contents

# Graph Transformation Method

The problem of calculation of the properties of a random walk on irregular networks was addressed previously by Goldhirsch and Gefen [208,209]. They described a generating-function-based method where an ensemble of pathways is partitioned into `basic walks'. A walk was defined as a set of paths that satisfies a certain restriction. As the probability generating functions corresponding to these basic walks multiply, the properties of a network as a whole can be inferred given knowledge of the generating functions corresponding to these basic walks. The method was applied to a chain, a loopless regularly branched chain and a chain containing a single loop. To the best of our knowledge only one [243] out of the 30 papers [253,245,247,221,257,255,244,249,210,254,243,258,240,260,264,209,262,220,251,211,252,261,259,222,263,219,248,250,256,246] that cite the work of Goldhirsch and Gefen [208] is an application, perhaps due to the complexity of the method.

Here we present a graph transformation (GT) approach for calculating the pathway sums and the mean escape times for . In general, it is applicable to arbitrary digraphs, but the best performance is achieved when the graph in question is dense. The algorithm discussed in this section will be referred to as DGT (D for dense). A sparse-optimised version of the GT method (SGT) will be discussed in Section 4.5.

The GT approach is similar in spirit to the ideas that lie behind the mean value analysis and aggregation/disaggregation techniques commonly used in the performance and reliability evaluation of queueing networks [187,265,267,266]. It is also loosely related to dynamic graph algorithms [270,271,269,268], which are used when a property is calculated on a graph subject to dynamic changes, such as deletions and insertions of nodes and edges. The main idea is to progressively remove nodes from a graph whilst leaving the average properties of interest unchanged. For example, suppose we wish to remove node from graph to obtain a new graph . Here we assume that is neither source nor sink. Before node can be removed the property of interest is averaged over all the pathways that include the edges between nodes and .The averaging is performed separately for every node . Next, we will use the waiting time as an example of such a property and show that the mean first passage time in the original and transformed graphs is the same.

The theory is an extension of the results used to perform jumps to second neighbours in previous KMC simulations [272,8]. Consider KMC trajectories that arrive at node , which is adjacent to . We wish to step directly from to any node in the set of nodes that are adjacent to or , excluding these two nodes themselves. To ensure that the mean first-passage times from sources to sinks calculated in and are the same we must define new branching probabilities, from to all , along with a new waiting time for escape from , . Here, corresponds to the mean waiting time for escape from to any , while the modified branching probabilities subsume all the possible recrossings involving node that could occur in before a transition to a node in . Hence the new branching probabilities are:

 (6.34)

This formula can also be applied if either or vanishes.

It is easy to show that the new branching probabilities are normalised:

 (6.35)

To calculate we use the method of Section 4.1.4:

 (6.36)

The modified branching probabilities and waiting times could be used in a KMC simulation based upon graph . Here we continue to use the notation of Section 4.1.4, where sinks correspond to nodes and sources to nodes in , and contains all the nodes in expect for the set, as before. Since the modified branching probabilities, , in subsume the sums over all path paths from to that involve we would expect the sink probability, , of a trajectory starting at ending at sink , to be conserved. However, since each trajectory exiting from acquires a time increment equal to the average value, , the mean first-passage times to individual sinks, , are not conserved in (unless there is a single sink). Nevertheless, the overall mean first-passage time to is conserved, i.e.  . To prove these results more formally within the framework of complete sums consider the effect of removing node on trajectories reaching node from a source node . The sink probability for a particular sink is

 (6.37)

and similarly for any other node adjacent to . Hence the transformation preserves the individual sink probabilities for any source.

Now consider the effect of removing node on the mean first-passage time from source to sink , , using the approach of Section 4.1.4.

 (6.38)

where the tildes indicate that every branching probability is replaced by , as above. The first and last terms are unchanged from graph in this construction, but the middle term,

 (6.39)

is different (unless there is only one sink). However, if we sum over sinks then

 (6.40)

for all , and we can now simplify the sum over as

 (6.41)

The same argument can be applied whenever a trajectory reaches a node adjacent to , so that , as required.

The above procedure extends the BKL approach [190] to exclude not only the transitions from the current state into itself but also transitions involving an adjacent node . Alternatively, this method could be viewed as a coarse-graining of the Markov chain. Such coarse-graining is acceptable if the property of interest is the average of the distribution of times rather than the distribution of times itself. In our simulations the average is the only property of interest. In cases when the distribution itself is sought, the approach described here may still be useful and could be the first step in the analysis of the distribution of escape times, as it yields the exact average of the distribution.

The transformation is illustrated in Figure 4.8 for the case of a single source.

Figure 4.8 (a) displays the original graph and its parametrisation. During the first iteration of the algorithm node is removed to yield the graph depicted in Figure 4.8 (b). This change reduces the dimensionality of the original graph, as the new graph contains one node and three edges fewer. The result of the second, and final, iteration of the algorithm is a graph that contains source and sink nodes only, with the correct transition probabilities and mean waiting time [Figure 4.8 (c)].

We now describe algorithms to implement the above approach and calculate mean escape times from complete graphs with multiple sources and sinks. Listings for some of the algorithms discussed here are given in Appendix B. We follow the notation of Section 4.1.4 and consider a digraph consisting of source nodes, sink nodes, and intervening nodes. therefore contains the subgraph .

The result of the transformation of a graph with a single source and sinks using Algorithm B.3 is the mean escape time and pathway probabilities , . Solving a problem with sources is equivalent to solving single source problems. For example, if there are two sources and we first solve a problem where only node is set to be the source to obtain and the pathway sums from to every sink node . The same procedure is then followed for .

The form of the transition probability matrix is illustrated below at three stages: first for the original graph, then at the stage when all the intervening nodes have been removed (line 16 in Algorithm B.3), and finally at the end of the procedure:

 (6.42)

Each matrix is split into blocks that specify the transitions between the nodes of a particular type, as labelled. Upon termination, every element in the top right block of matrix is non-zero.

Algorithm B.3 uses the adjacency matrix representation of graph , for which the average of the distribution of mean first passage times is to be obtained. For efficiency, when constructing the transition probability matrix we order the nodes with the sink nodes first and the source nodes last. Algorithm B.3 is composed of two parts. The first part (lines 1-16) iteratively removes all the intermediate nodes from graph to yield a graph that is composed of sink nodes and source nodes only. The second part (lines 17-34) disconnects the source nodes from each other to produce a graph with nodes and directed edges connecting each source with every sink. Lines 13-15 are not required for obtaining the correct answer, but the final transition probability matrix looks neater.

The computational complexity of lines 1-16 of Algorithm B.3 is . The second part of Algorithm B.3 (lines 17-34) scales as . The total complexity for the case of a single source and for the case when there are no intermediate nodes is and , respectively. The storage requirements of Algorithm B.3 scale as .

We have implemented the algorithm in Fortran 95 and timed it for complete graphs of different sizes. The results presented in Figure 4.9 confirm the overall cubic scaling. The program is GPL-licensed [273] and available online [274]. These and other benchmarks presented in this chapter were obtained for a single Intel Pentium  4 3.00GHz 512Kb cache processor running under the Debian GNU/Linux operating system [275]. The code was compiled and optimised using the Intel Fortran compiler for Linux.

Next: Applications to Sparse Random Up: ENSEMBLES OF REARRANGEMENT PATHWAYS Previous: Complete Graphs   Contents
Semen A Trygubenko 2006-04-10