|
Return to GeoComputation 99 Index
David O'Sullivan2
Centre for Advanced Spatial Analysis, University College London
david.osullivan@ucl.ac.uk
Space is a concept which is central to our understanding of the world. Indeed, in recent years it seems to have taken pride of place in many more fields of enquiry than might be thought strictly sensible. ‘Spaces’ of various sorts seem to be everywhere these days: geographic space, urban space, architectural space, virtual space, cyberspace (that old chestnut), body space, mental space, cognitive space, ‘the space of flows’, geographic space, psychological space, dream space, symbolic space... the list is potentially endless. The sheer multiplicity of spaces in contemporary academic discourse is overwhelming (see for example Benko and Strohmayer, 1997, Soja, 1989). Such widespread use is in danger of making the term meaningless. At the very least, it requires those of us who want to use the concept to define what we mean.
In this paper I use a recent concept from geographic modelling - proximal space - as the starting point for an exploration of the properties of space, in particular its effects on certain kinds of dynamic processes. Two possible representations of such a proximal model of space are introduced: graphs and cellular automata (CA), along with a brief consideration of some of the analytical techniques which have previously been used to investigate these representations.
A modelling approach which allows these two powerful representations to be combined in a natural way is then proposed: graph-CA models. In some respects such a model is not new and is similar to discrete component models (Zeigler, 1976), however, this perspective does allow us to investigate questions about the relationships between spatial structures and spatial processes in new ways. A possible investigative approach is then proposed. In direct analogy with physicists’ explorations of CA rule-space (Wolfram, 1983, 1984b, Langton, 1990), it is proposed that spatial theorists (geographers, architects, urbanists) might explore graph-CA cell space. This in turn may constitute the beginnings of a research program to answer the call for a specifically geo-computation made by Couclelis (1998).
It is clear that a wide variety of spatial concepts may be brought to bear when building spatial models to investigate spatial processes (Couclelis, 1992a, 1992b). Particular attention has often been paid to a long-standing division rooted in natural science and philosophy, between absolute and relative models of space. Rather than explore this division further, I want to use a recently introduced notion of space: proximal space. In the proximal conception of space, the fundamental element is the neighbourhood (Couclelis, 1997). A neighbourhood is defined by relations of nearness between spatial elements. Nearness depends on both (spatial) adjacency and (functional) influence. Proximal models are useful because they allow non-contiguous neighbourhoods, based on relations of influence between elements. They also allow the integration of functional and spatial relations, and of fuzzy concepts and phenomena. That proximal space has been developed in the context of a discussion of cellular automata models for urban and regional planning is significant (Takeyama, 1995, Takeyama and Couclelis, 1997, Couclelis, 1997) and strongly influences the methodology proposed here for developing the idea.
Allowing that proximal conceptions of space represent a useful innovation, on what bases might proximal spatial models be constructed? Various metrics are possible: a Voronoi approach is one such, wherein regions are associated with objects according to which is nearest, and the resulting spatial partition produces spatial elements (Gold, 1992). Extensions of the basic Voronoi concept of proximity polygons can be based on different metric systems (Okabe et al., 1994). This is illustrated in figure 1. Ideas from urban morphology (see for example Atkin, 1974a, 1974b, 1975, Hillier and Hanson, 1984, Krüger, 1979a, 1979b, Krafta, 1994, 1996) represent another rich set of ideas about how proximal models might be constructed. The proximal model approach is informed by pragmatism, and an interest in tackling problems, not by the abstract ideas of philosophers, so that Gould’s (1997: 128) remark seems relevant:
| "...we start with the idea that this strange no-thing [space] is structured by other things, which we relate in various ways to each other, and which we measure as various distances to each other as the fancy takes us according to our purpose of utility, curiosity, or ambition." |
 |
| Figure 1 A simple Voronoi partition and variants (Okabe et al., 1994) |
The origin of proximal space is Takeyama’s geo-algebra (Takeyama and Couclelis, 1997), which in turn is developed from work in ‘cellular geography’ (Tobler, 1979, Hägerstrand, 1967) and in later implementations of cellular automata models in geography and urban and regional studies (White, 1998, Batty et al., 1997). I want to propose a new way of thinking about the geo-algebra framework which opens up some new ways of investigating that very general spatial modelling framework. Geo-algebra is based on a relaxation of one of the rather strict criteria imposed by cellular automata models: that all cells have identical neighbourhoods. Thus each cell in a ‘relaxed CA’ in the geo-algebra framework has a different neighbourhood constructed according to the relations between whatever spatial elements are modelled. The spatial structure underlying such relaxed CA models is most conveniently described and understood as a graph. Thus we may think of such a model as a cellular automata running on a graph, a graph-based CA, or a graph-CA (GCA). Of course, a regular lattice-based CA is also running on a graph, it’s just that the graph is not required as a way of describing the spatial arrangement: ‘regular grid’ is sufficient.
This opens up an interesting avenue of research. Graph representations have often been used in describing and exploring sets of relations between elements. To take a typical application area, in social networks research various measures of graph structure are developed to aid in understanding the way in which social networks function (Wassermann and Faust, 1994). Again, graph representations have been successfully used in geography (Haggett and Chorley, 1969) and urban morphology (Hillier and Hanson, 1984, Krüger, 1979a, Krüger, 1979b). This is useful but limited to ‘comparative statics’ since the graph is fixed at any moment in time, and analysis is generally restricted to relating graph structural measures to other data sets.
Cellular automata, on the other hand, are highly dynamic, and offer a relatively obvious way of building models based on an understanding (or hypothesis) about processes which are relevant to the situation being modelled. In physics, CA models have been successfully related to theories in non-linear dynamics, computational theory, and statistical mechanics (Hanson and Crutchfield, 1995, Wolfram, 1983, 1984a, 1984b, Langton, 1990). However, in geography and urban and regional modelling, CA suffer from the unrealistic assumption that every location is identical. The validity of this assumption is clearly related to the scale of the model and the phenomenon being modelled, but is often questionable. The relaxed CA of geo-algebra are a way out of this difficulty but the connection of such models with the powerful theoretical ideas of non-linear dynamics and computation is weakened. Thinking of relaxed CA models as graph-CA models offers a way forward.
A particular graph-CA model may be thought of as existing in a multi-dimensional domain which contains all possible such models. This section proposes a framework for thinking about this domain which leads naturally to a way of exploring it.
In setting up a graph-CA model we are free to vary it in two fundamental ways: we can vary the underlying graph; or we can vary the rules governing cell evolution. The outcome of these modelling decisions will presumably be different model behaviours. If we can describe each of these variables (graph structure or cell space, the rule set or rule space, and the complexity of the dynamic behaviour) in terms of a single variable then the domain of all possible graph-CAs can be thought of as a three-dimensional space (see figure 2).
 |
| Figure 2 The domain of all possible GCA models |
Wolfram (1983) was the first to attempt a systematic phenomenological investigation of regular CA. He undertook an exhaustive statistical study of a limited subset of possible CAs and classified the various possible rule sets according to their dynamic behaviour. There are some difficulties in assigning CAs to particular behavioural classes, but a number of measures exist which may allow automatic classification, principally entropy-like measures (Wuensche, 1998). Langton’s (1990) work was a first step towards parameterising CA rule space using a single value. Although his conclusions and his 
parameter have since been challenged (Hordijk et al., 1996, Mitchell et al., 1993) as an over-simplification, there does seem to be a correspondence between CA behaviour and CA rule space, so that the first steps towards understanding the subtle effects of rules on global behaviour have been taken.
The obvious question now becomes: can similar relationships be found between the structure of cell space in a graph-CA and the emergent dynamic behaviour? Answering this question would seem to be a task for geo-computational theory. As the label on the cell-space axis of figure 2 suggests, one approach is to characterise cell space using graph structural measures, and to carry out similar work to Langton’s, this time exploring variation in behaviour in cell space rather than rule space.
Before describing results in detail, it is important to explain the procedure adopted and the reasoning behind it.
As set out in section 4.1 the general aim is an exploration of the cell space of the domain of all possible graph-CA models. This domain is unthinkably vast. If were to consider only graphs of 20 vertices, then there are around 1039 possible connected graphs of this size (Beineke and Wilson, 1997: 27). Considering only 2 state CAs, each of these possible graphs has 2220 = 10315653 possible rule sets. Even considering only totalistic rules, where only the number of neighbours in a given state affects the next state, there are 221 = 2 x 106 possible rule sets. 1039 x 2 x 106 = 2 x 1045 is a very large number. Therefore, we need some way of exploring the space in an intelligent way. The method adopted here is to start with well known ‘interesting’ regular CAs, and to progressively deform their cell space. Thus we might start with the ‘Game of Life’ CA (Poundstone, 1985), and steadily alter the structure of the grid (its cell-space), observing changes in the resulting behaviour.
This approach presents difficulties of its own. Perhaps the foremost of these is whether or not it is possible to alter the distribution of graph neighbourhood sizes and simultaneously hold the rule set constant in a meaningful way. This effectively poses the question: is there a relationship between cell space and rule space? (Put another way, can we choose parameters which make the cell space and rule space axes of figure 2 orthogonal?) Consider a uniform grid of cells, where cell neighbourhoods include the cell itself and its immediately adjacent cells in all eight directions so that all neighbourhoods consist of 9 cells. A rule set for this cell space need only(!) specify 2512 outcomes (assuming 2 allowable states). If deforming the cell space results in neighbourhoods of sizes other than 9, then how do we apply the original rule set to these neighbourhoods? The answer is that there is no easy answer. Possibilities include:
In the experiments described in section 5, method (i) has been adopted, although the deformation rule adopted in method (i) is not the non-symmetric one described above (see section 4.3). All the experiments described in section 6 start with regular grids in which all cells have the same neighbourhood size, so that a neighbourhood-preserving deformation process ensures that a rule set can be defined with one neighbourhood size in mind from the outset, thus side-stepping the difficulties in (ii) and (iii).
Whichever approach is adopted, the overall effect is that an experiment traces a trajectory through GCA space. Clearly, the two axes, cell-space and complexity must be calibrated or scaled in some way. The measures used are described in the next two sections.
One of the major motivations for the current approach is the ready availability of numerous measures of graph structure, which in the current context may be regarded as proxies for measures of cell-space. Various measures suggest themselves, ranging from total distance in the graph from every vertex to every other, to more complex information-based measures where paths between vertices are included according to their length (Stephenson and Zelen, 1989). The most obvious approaches are based on centrality, (the extent to which each vertex is central to the graph), and centralisation (the extent to which the whole graph is dominated by central vertices).
An alternative approach, adopted here, is to use some relative measure of graph structure, based on how different from one another are consecutive graphs in a sequence of graphs along a trajectory through GCA-space. The easiest way to do this, at least, initially, is to deform the graph by the same amount in the same way at each step, so that trajectories start at some origin and each subsequent graph is equally spaced along the cell space axis. In keeping with the restriction mentioned in option (i) in section 4.2, the deformation method used is a neighbourhood-preserving edge swap. Four vertices v0, v1, v2 and v3 are randomly selected such that v0v1 and v2v3 are edges in the graph, and v0v2 and v1v3 are not. Edges v0v1 and v2v3 are then replaced by v0v2 and v1v3. Restrictions are placed on how remote from each other the four vertices may be. The distance between two graphs G0 and G1 in cell space can then be approximated by the number of edge-swaps of this kind that are required to transform G0 into G1. Measures broadly of this type have been proposed in the mathematical literature on graphs (Hrnciar et al., 1996, Goddard and Swart, 1996, Chartrand et al., 1998).
Note also that this deformation is significantly different from that used by Watts and Strogatz (1998) in their investigation of ‘small-world’ networks where edges may are replaced by randomly connecting to any other vertex in the graph. The deformation considered in the present work has the property of preserving what might be called the local coherence of the graph. That is, if the initial graph is such that vertices are only connected to spatially near neighbours, then even after several deformations, most neighbourhood relations will still be between spatially close vertices. The difference between this sort of deformation and the ‘small-world’ deformation is significant.
The complexity or dynamic behaviour axis is also problematic. In his seminal work on classifying CA Wolfram (1983, 1984a, 1984b) introduced an entropy based measure, spatial set entropy, which attempts to assess the extent to which the evolution of a CA leads to statistically unlikely configurations. Spatial set entropy S, in a system with s allowable states, is given by
 |
(1) |
where pj(x) denotes the probability of occurrence of each of the sX possible neighbourhood states in sequences of cells of length X. This measure is in the range 0 to 1 where 0 indicates a very ordered arrangement of cell states and 1 indicates a completely disorganised arrangement of states. The measure is applied over some number of cells, so that a particular configuration of cell states may seem random at X = 1, but exhibit order at some other value of X. Wuensche (1998) uses this measure with X set equal to the neighbourhood size, and this is the approach adopted here. In Wuensche’s work the determination of p(x) is unproblematic, because neighbourhoods can be naturally ordered, so that an X cell neighbourhood, in a CA with s allowed states has sX equiprobable possible states.
In a graph-CA, determination of p is more problematic because there is no natural ordering of cells in each neighbourhood. A related information measure has therefore been developed as follows (see Applebaum, 1996 for the relationship between entropy and information). To allow for the co-existence of various neighbourhood sizes k we define the total system information I as
 |
(2) |
where Ik is the information measure for the set of neighbourhoods of size k, and the summation is over the n neighbourhoods in the graph G. Ik is calculated over the nk neighbourhoods of size k:
 |
(3) |
where pk(m) is the proportion of the nk neighbourhoods of size k which have m cells in the state of interest s*, and is the prior probability of such a neighbourhood configuration occurring, and I(1)=I(0)=0. If there are n* cells in state s* in a system of size n, qk(m) is given by
 |
(4) |
where xCy is the number of ways of selecting x elements from a set of y elements, and is given by
 |
(5) |
Returning to equation (3), it is obvious that 
, and that
 |
(6) |
The minimum value of qk(m) obviously occurs when all the cells in the k-neighbourhood in question are in the least likely configuration, that is m = 0 or k, when n* is nearer to n or 0, respectively. If we denote min(n*, (n - n*)) by n’ , then we can show that3,
 |
(7) |
so that,
 |
(8) |
If, for clarity, we denote min(k, n’) by a, and max(k, n’) by b, and use (8) to normalise the expression in equation (3), we get
 |
(9) |
Substituting (9) into (2) gives us a final expression
 |
(10) |
In the results reported in section 6, the expression in equation (10) has been used to produce a time-series describing the evolution of each model. The immediate neighbourhood of each cell is used to determine pk(m) and qk(m). To demonstrate the behaviour of this rather complicated measure, its evolution for two well-known grid-based CA is plotted in figure 3.
 |
| Figure 3 Spatial information time-series for two ‘classic’ CAs |
The upper (shorter) time-series represents the evolution of a segregation type CA rule, whereby each vertex (cell) adopts the same state as the majority of its neighbours (this sort of model is similar to Schelling’s (1971, 1978) models of racial segregation phenomena in social systems). This kind of rule exhibits a distinctive rapid increase in spatial information, as the system ‘sorts’ itself into distinct areas of connected vertices in the same state. Once segregation is complete the spatial information attains a fixed value. The other time-series shows the evolution on this measure of the ‘Game of Life’ CA a much cited example of complex CA behaviour (Poundstone, 1985). The rule in this case involves vertex births when the number of live neighbours to a vertex is neither too low (death by isolation), nor too high (death by overcrowding). This seemingly innocuous rule leads to very complex dynamic behaviour with activity persisting over many time steps even in the finite system shown here. Although the actual value of spatial information attained is much lower than in the segregation CA case (note the right hand axis on figure 3) there is a distinct increase over the near-zero value of the random starting configuration. Note that both of these time-series have been generated by averaging the spatial information at each time step for a set of 50 different randomly generated starting configurations. It is beyond the scope of this paper to show that this approach is statistically valid, but it is in keeping with practice in the wider CA research community.
Having developed an experimental approach and the measures required to implement it, the next two sections describe the computing environment used to apply the approach (section 5), and some preliminary results (section 6).
The experiments in the next section have been carried out using a simple set of tools (GraphCA) developed for building graph-CA models. GraphCA is written in Java. Figure 4 shows a screenshot of these tools in use.
 |
| Figure 4 The GraphCA program |
Currently, GraphCA provides a number of utilities 4:
The GraphCA environment is still being developed. Indeed it has largely been developed in response to the emerging needs of the research outlined in the next section. This is a result of the potentially limitless scope of an investigation into the relationships between structure and process, which makes it hard to anticipate all the requirements in advance, and therefore to design an experimental environment.
This section describes some initial investigations carried out along the lines proposed in section 4 using the GraphCA software. All the examples in this section are based on GCA-space trajectories originating with a 400 vertex ‘toroidal grid’ graph, in which each vertex has as its neighbours itself, and its four orthogonally and four diagonally nearest neighbours. Vertices along the ‘edges’ of this grid are connected to vertices on the opposite edge so that all vertices are identical. The edge-swap deformation process described in section 4.3 is used to trace the trajectories described.
In figure 5 the effect of a short series of 10 edge-pair swap deformations on the segregation CA described in section 4.4 is shown. Clearly the sort of dynamic behaviour observed as described by the spatial information time-series recorded in each case is broadly similar, although the final stable value of spatial information attained in each case is different.
 |
| Figure 5 The effect of a series of 10 edge-swap deformations a segregation GCA |
Figure 6 confirms that the shape of the time-series observed in each case is very similar. This indicates that the general ‘segregation’ behaviour of this transition rule is robust under these deformations of the underlying graph. It is useful to plot the trend in the final stable value of the spatial information attained, against the number of edge-swaps made. This has been done in figure 7. For this single GCA-space trajectory, the trend is clear: as the graph on which the segregation graph-CA is run becomes less regular, the degree of irregularity attained, as measured by the spatial information, is reduced. Of course, this is only a single possible sequence of deformations. To confirm that there is any kind of trend, further examples are required.
 |
| Figure 6 Normalised time-series for the data in figure 5 |
 |
| Figure 7 Summary diagram showing effect of deformation on the final value of spatial information attained by the segregation GCA |
In figure 8 a number of GCA-space trajectories are summarised. It is not absolutely clear from the raw data (the left hand plot) that deforming the regular grid on which a segregation transition rule runs always leads to a reduction in the long-term spatial information. However normalising the time-series by their initial value, as on the right hand side of the diagram, shows a more marked effect. To confirm the long term trend, the untypical rising trend (experiment 170299_1) has been extended by further deforming the graph. This is shown in figure 9. It would seem from these limited results that there may be a general trend associated with steadily deforming the graph underlying this type of segregation transition rule graph-CA. Of course these results only represent a tiny fraction of all the possible 400 vertex graphs with the constraint that each vertex has 9 neighbours. More extensive exploration is required to confirm this tentative result.
 |
| Figure 8 A number of GCA-space trajectories for the segregation transition rule |
 |
| Figure 9 Further deformation of the grid for experiment 170299_1 |
To understand the meaning of this result it is instructive to examine a sequence of typical final configurations of the graph-CA models involved. Figure 10 shows the final state of the segregation CA for one starting configuration (i), as it is deformed by respectively (ii) 0, (iii) 100, (iv) 200, (v) 500, and (vi) 1000 edge-pair swaps. The way in which deformation alters which locations in the graph allow the formation of large connected components can be seen. That the underlying graph remains locally coherent so that vertices near each other ‘in the grid’ are still more likely to be connected (as in the initial regular graph) can be seen from the similarity of the final configurations across the sequence. This is true at least up to the 1000 edge-pair case (iv), by which time the underlying graph is so distorted as to be almost random. In fact, although a general trend towards reduced order in the final configuration is discernible, and is confirmed by the information measure, the more striking finding is the robustness of this transition rule under severe deformation of its underlying graph.
 |
| Figure 10 Final configuration for starting configuration (i) for (ii) 0, (iii) 100, (iv) 200, (v) 500 and (vi) 1000 edge-pair swaps deformations of the regular grid lattice |
A similar experiment to that presented in figure 5 was carried out for the Game of Life CA (Poundstone, 1985). It is harder to interpret the results in this case because the behaviour as traced by the spatial information time-series is less clear-cut. However, using a 10-point moving average to smooth the time-series data, the result in figure 11 is obtained. Again, deformation of the graph has a clear effect on the CA behaviour. In this case, it is best described as a reduction in the transient time during which the spatial information is above that associated with random configurations. In this case the effect seems to occur much more rapidly, and is quite marked after only 100 edge-pair swaps, so that we can think of the Life CA as not being robust under this sort of deformation. The behaviour of the Life CA clearly sensitively depends on the coherence of the cell-space in which it runs.
 |
| Figure 11 10-point moving average of the spatial information time-series for deformation of the ‘Game of Life’ CA |
This paper has introduced a potential avenue for investigation and development of what could represent the beginnings of geo-computational theory. I have drawn on ideas from the computational investigation of cellular automata to propose a methodology for investigating the effects of space on CA based models. CA have been recast as graph-based CA, to facilitate the central task of finding a relationship between spatial structure and the spatial behaviour of processes.
Using the methods described, the impact of spatial structure on the behaviour of two particular CAs has been briefly explored, and evidence of some spatial effects has been found. It is noteworthy that the effects observed here are less marked than those observed by Watts and Strogatz (1998), in their small-worlds work, where more dramatic (albeit not specifically spatial) changes in a graph were introduced, and observed to alter processes embedded in the graph. The small-worlds work, together with earlier work by Kauffman (1984, 1995), suggests further directions in which the present work could be developed, as well as potentially defining the boundaries of specifically geo-computational research.
It is worth emphasising the tentative nature of this work. This paper covers a lot of ground, and many of the ideas and approaches presented require further investigation and could be developed further. It is clear, for example, that the spatial information measure outlined in section 4.4 may be susceptible to spatial auto-correlation effects. Improvements to this measure might draw on earlier work in spatial analysis on spatial auto-correlation (Cliff and Ord, 1973) and on entropy measures (Batty, 1976, Batty, 1974). Finally, the GraphCA software described was initially developed to allow the construction of graph-based CA models, not for in depth exploration of GCA space, and any significant extension of this exploration requires tools designed with the scale of that task in mind.
Applebaum, D., 1996, Probability and information theory An integrated approach, (Cambridge University Press: Cambridge).
Atkin, R. H., 1974a, 'An approach to structure in architectural and urban design 1: Introduction and mathematical theory', Environment and Planning B: Planning & Design, 1, 51-67.
Atkin, R. H., 1974b, 'An approach to structure in architectural and urban design 2: Algebraic representation and local structure', Environment and Planning B: Planning & Design, 1, 173-191.
Atkin, R. H., 1975, 'An approach to structure in architectural and urban design 3: illustrative examples', Environment and Planning B: Planning & Design, 2, 21-57.
Batty, M., 1974, 'Spatial entropy', Geographical Analysis, 6, 1-31.
Batty, M., 1976, 'Entropy in spatial aggregation', Geographical Analysis, 8, 1-21.
Batty, M., Couclelis, H. and Eichen, M. (eds.), 1997, Environment and Planning B: Planning & Design, Special Issue - Urban systems as cellular automata, (Pion Ltd.
Beineke, L. W. and Wilson, R. J., 1997, Graph Connections, Relationships between Graph Theory and other Areas of Mathematics, (Clarendon Press: Oxford).
Benko, G. and Strohmayer, U., 1997, Space and social theory : interpreting modernity and postmodernity, (Blackwell Publishers: Oxford, England; Cambridge, Mass.).
Chartrand, G., Kubicki, G. and Schultz, M., 1998, 'Graph similarity and distance in graphs', Aequationes Mathematicae, 55, 129-145.
Cliff, A. and Ord, J., 1973, Spatial Autocorrelation, (Pion: London).
Couclelis, H., 1992a, 'Location, Place, Region, and Space', pp. 215-233 in Geography's inner worlds Pervasive themes in contemporary American geography, Abler, R. F., Marcus, M. G. and Olson, J. M. (eds.), (Rutgers University Press: New Brunswick NJ).
Couclelis, H., 1992b, 'People manipulate objects (but cultivate fields): Beyond the raster-vector debate in GIS', pp. 65-77 in Lecture Notes in Computer Science 639 Theories and methods of spatio-temporal reasoning in geographic space, Frank, A. U., Campari, I. and Formentini, U. (eds.), (Springer-Verlag: Berlin).
Couclelis, H., 1997, 'From cellular automata to urban models: new principles for model development and implementation', Environment and Planning B: Planning & Design, 24, 165-174.
Couclelis, H., 1998, 'Geocomputation in context', pp. 17-29 in Geocomputation A Primer, Longley, P. A., Brooks, S. M., McDonnell, R. and MacMillan, B. (eds.), (John Wiley & Sons: Chichester, England).
Goddard, W. and Swart, H. C., 1996, 'Distances between graphs under edge operations', Discrete Mathematics, 161, 121-132.
Gold, C. M., 1992, 'The meaning of neighbour', pp. 220-235 in Lecture Notes in Computer Science 639. Theories and methods of spatio-temporal reasoning in geographic space, Frank, A. U., Campari, I. and Formentini, U. (eds.), (Springer-Verlag: Berlin).
Gould, P., 1997, 'The structure of space(s)', Geogafiska Annaler B, 79(3), 125-140. Hägerstrand, T., 1967, Innovation diffusion as a spatial process, (University of Chicago Press: Chicago,).
Haggett, P. and Chorley, R. J., 1969, Network Analysis in Geography, (Edward Arnold: London).
Hanson, J. E. and Crutchfield, J. P., 1995, 'Computational mechanics of cellular automata: an example', Santa Fe Institute, Working Paper, 95-10-095.
Hillier, B. and Hanson, J., 1984, The Social Logic of Space, (Cambridge University Press).
Hordijk, W., Crutchfield, J. P. and Mitchell, M., 1996, 'Embedded-particle computation in evolved cellular automata', Santa Fe Institute, 96-09-073.
Hrnciar, P., Haviar, A., Monoszova, G. and Bystrica, B., 1996, 'Some characteristics of the edge distance between graphs', Czechoslovak Mathematical Journal, 46(121), 665-675.
Kauffman, S., 1995, At Home in the Universe, The search for laws of complexity, (Penguin: London).
Kauffman, S. A., 1984, 'Emergent properties in random complex automata', Physica D, 10, 145-156.
Krafta, R., 1994, 'Modelling intraurban configurational development', Environment and Planning B: Planning & Design, 21, 67-82.
Krafta, R., 1996, 'Urban convergence: morphology and attraction', Environment and Planning B: Planning & Design, 23, 37-48.
Krüger, M. J. T., 1979a, 'An approach to built form connectivity at an urban scale: system description and its representation', Environment and Planning B: Planning & Design, 6, 67-88.
Krüger, M. J. T., 1979b, 'An approach to built form connectivity at an urban scale: variations of connectivity and adjacency measures amongst zones and other related topics', Environment and Planning B: Planning & Design, 6, 305-320.
Langton, C. G., 1990, 'Computation at the edge of chaos: phase transitions and emergent computation', Physica D, 42, 12-37.
Mitchell, M., Crutchfield, J. P. and Hraber, P. T., 1993, 'Dynamics, computation and the "Edge of Chaos": a re-examination', Santa Fe Institute, Working Paper, 93-06-040.
Okabe, A., Boots, B. and Sugihara, K., 1994, 'Nearest neighbourhood operations with generalized Voronoi diagrams: a review', International Journal of Geo-Information Systems, 8, 43-71.
Poundstone, W., 1985, The Recursive Universe, (Morrow: New York).
Schelling, T. C., 1971, 'Dynamic models of segregation', Journal of Mathematical Sociology, 1, 143-186.
Schelling, T. C., 1978, Micromotives and macrobehavior, (Norton: New York).
Soja, E. W., 1989, Postmodern geographies : the reassertion of space in critical social theory, (Verso: London ; New York).
Stephenson, K. and Zelen, M., 1989, 'Rethinking centrality: methods and examples', Social Networks, 11, 1-37.
Takeyama, M., 1995, Geo-Algebra: a mathematical approach to integrate spatial modelling and GIS, UCSB, Santa Barbara.
Takeyama, M. and Couclelis, H., 1997, 'Map dynamics: integrating cellular automata and GIS through Geo-Algebra', International Journal of Geo-Information Science, 11, 73-91.
Tobler, W. R., 1979, 'Cellular geography', pp. 379-386 in Philosophy in Geography, Gale, S. and Olsson, G. (eds.), (D Reidel Publishing Company: Dordrecht, Holland).
Wassermann, S. and Faust, K., 1994, Social Network Analysis, Methods and Applications, (Cambridge University Press).
Watts, D. J. and Strogatz, S. H., 1998, 'Collective dynamics of 'small-world' networks', Nature, 393(4 June), 440-442.
White, R., 1998, 'Cities and cellular automata', Discrete Dynamics in Nature and Society, 2, 111-125.
Wolfram, S., 1983, 'Statistical mechanics of cellular automata', Review of Modern Physics, 55, 601-643.
Wolfram, S., 1984a, 'Computation theory of cellular automata', Communications in Mathematical Physics, 96, 15-57.
Wolfram, S., 1984b, 'Universality and complexity in cellular automata', Physica D, 10, 1-35.
Wuensche, A., 1998, 'Classifying Cellular Automata Automatically', Santa Fe Institute, Working Paper, 98-02-018.
Zeigler, B., 1976, Theory of modelling and simulation, (Wiley: New York).
1A pdf version of this paper is available at http://www.casa.ucl.ac.uk/david/publications.html.
2This research has been carried out during an EPSRC studentship held at the Bartlett Faculty of the Built Environment at University College London.
3Details available from the author.
4A version of GraphCA can be seen on the author's website.