A new type of dynamic spatial model is described: graph-cellular automatoa (graph-CA). First, the proximal model of space and geo-algebra are briefly introduced. Then, the graph-CA model is described, with an emphasis on understanding it as a reworking of the proximal model of space and also of geo-algebra. It is shown that graph-CA with particular structural properties defined in terms of the relationships between subsets of cells are a useful generalisation of traditional cellular automaton (CA) which enable meaningful descriptions of model structure to be developed. This enables further development of novel types of model in the same ‘family’ while retaining links to simpler, better understood examples. It is further argued that the derivation of the graph-CA from both the graph and CA formalisms permits the simultaneous use of well-developed ways of describing model structure and process dynamics, and that this could form the basis of a research programme into the elusive relations between the two. The relationship of graph-CA to other discrete models is briefly discussed, and a classification scheme which indicates the particular geographical interest of such models is suggested.
Get full access to this article
View all access options for this article.
References
1.
AllenP M, 1997Cities and Regions as Self-organizing Systems: Models of Complexity volume 1 of Environment Problems and Social Dynamics (Gordon and Breach, Amsterdam)
BattyM, 1999, “Editorial: a research programme for urban morphology”Environment and Planning B: Planning and Design26475–476
4.
BattyMLonglegsP A, 1986, “The fractal simulation of urban structure”Environment and Planning A181143–1179
5.
BattyMXieY, 1997, “Possible urban automata”Environment and Planning B: Planning and Design24175–192
6.
BattyMCouclelisHEichenM (Eds), 1997, “Special issue—urban systems as cellular automata”Environment and Planning B: Planning and Design24159–305
7.
BeinekeL WWilsonR J, 1997Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics volume 5 of Oxford Lecture Series in Mathematics and its Applications (Clarendon Press, Oxford)
8.
ClarkeK CHoppenSGaydosL, 1997, “A self-modifying cellular automaton model of historical urbanization in the San Francisco Bay area”Environment and Planning B: Planning and Design24247–261
9.
CouclelisH, 1984, “The notion of prior structure in urban modelling”Environment and Planning A16319–338
10.
CouclelisH, 1985, “Cellular worlds: a framework for modelling micro–macro dynamics”Environment and Planning A17585–596
11.
CouclelisH, 1988, “Of mice and men: what rodent populations can teach us about complex spatial dynamics”Environment and Planning A2099–109
12.
CouclelisH, 1997, “From cellular automata to urban models: new principles for model development and implementation”Environment and Planning B: Planning and Design24165–174
13.
CouclelisH, 1998, “Geocomputation and space”Environment and Planning B: Planning and Design 25th anniversary issue 25 S41–S47
14.
DonningerC, 1986, “The distribution of centrality in social networks”Social Networks8191–203
15.
GouldP, 1997, “The structure of space(s)”Geografiska Annaler B79125–140
16.
HaggettPChorleyR J, 1969Network Analysis in Geography (Arnold, London)
17.
HarveyD, 1996Justice, Nature and the Geography of Difference (Blackwell, Maiden, MA)
18.
JungnickelD, 1999Graphs, Networks and Algorithms volume 5 of Algorithms and Computation in Mathematics (Springer, Berlin)
19.
KauffmanS A, 1984, “Emergent properties in random complex automata”Physica D10145–156
20.
KraftaR, 1994, “Modelling intraurban configurational development”Environment and Planning B: Planning and Design2167–82
21.
KraftaR, 1996, “Urban convergence: morphology and attraction”Environment and Planning B: Planning and Design2337–48
22.
KrügerM J T, 1979a, “An approach to built form connectivity at an urban scale: system description and its representation”Environment and Planning B: Planning and Design667–88
23.
KrügerM 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 and Design6305–320
24.
MorrillR, 1995, “Racial segregation and class in a liberal metropolis”Geographical Analysis27(1) 22–41
25.
O'SullivanD, 1999, “Exploring the structure of space: towards geocomputational theory”, paper presented at 4th International Conference on GeoComputation, 25–28 July, Mary Washington College, Fredericksburg, VA, http://www.geovista.psu.edu/sites/geocomp99/029/gc929.htm
26.
O'SullivanD, 2000Graph-based Cellular Automaton Models of Urban Spatial Processes unpublished PhD thesis, Centre for Advanced Spatial Analysis, University of London, London
27.
O'SullivanD, 2001, “Exploring spatial process dynamics using irregular graph-based cellular automaton models”Geographical Analysis331–18
28.
O'SullivanDTorrensP M, 2001, “Cellular models of urban systems”, in Theoretical and Practical Issues on Cellular Automata: Proceedings of the Fourth International Conference on Cellular Automata for Research and Industry (ACRI 2000) Eds BandiniSWorschT (Springer, London)
29.
PoundstoneW, 1985The Recursive Universe (Morrow, New York)
30.
SackR D, 1997Homo Geographicus: A Framework for Action, Awareness and Moral Concern (Johns Hopkins University Press, Baltimore, MD)
31.
SemboloniF, 2000, “The growth of an urban cluster into a dynamic self-modifying spatial pattern”Environment and Planning B: Planning and Design27549–564
32.
SojaE W, 1989Postmodern Geographies: The Reassertion of Space in Critical Social Theory (Verso, London)
33.
TakeyamaM, 1996Geo-algebra: A Mathematical Approach to Integrate Spatial Modelling and GIS unpublished PhD thesis, Department of Geography, University of California, Santa Barbara, CA
34.
TakeyamaM, 1997, “Building spatial models within GIS through geo-algebra”Transactions in GIS2245–256
35.
TakeyamaMCouclelisH, 1997, “Map dynamics: integrating cellular automata and GIS through Geo-Algebra”International Journal of Geographical Information Science1173–91
36.
TollisI GDi BattistaGEadesPTamassiaR, 1999Graph Drawing: Algorithms for the Visualization of Graphs (Prentice-Hall, Englewood Cliffs, NJ)
37.
TomlinC D, 1990Geographical Information Systems and Cartographic Modeling (Prentice-Hall, Englewood Cliffs, NJ)
38.
TorrensP MO'SullivanD, 2001, “Cellular automata and urban simulation: where do we go from here?”Environment and Planning B: Planning and Design28163–168
39.
WassermannSFaustK, 1994Social Network Analysis: Methods and Applications (Cambridge University Press, Cambridge)
40.
WattsD J, 1999Small Worlds: The Dynamics of Networks between Order and RandomnessPrinceton Studies in Complexity (Princeton University Press, Princeton, NJ)
41.
WattsD JStrogatzS H, 1998, “Collective dynamics of ‘small-world’ networks”Nature393440–442
42.
WhiteR, 1998, “Cities and cellular automata”Discrete Dynamics in Nature and Society2111–125
43.
WhiteREngelenG, 1993, “Cellular automata and fractal urban form: a cellular modelling approach to the evolution of urban land-use patterns”Environment and Planning A251175–1199
44.
WhiteREngelenG, 1997, “Cellular automata as the basis of integrated dynamic regional modelling”Environment and Planning B: Planning and Design24235–246
45.
WhiteREngelenGUljeeI, 1997, “The use of constrained cellular automata for high-resolution modelling of urban land-use dynamics”Environment and Planning B: Planning and Design24323–343
46.
WilsonR J, 1996Introduction to Graph Theory4th edition (Longman, Harlow, Essex)
47.
WolframS, 1983, “Statistical mechanics of cellular automata”Review of Modern Physics55601–643
48.
WolframS, 1984, “Universality and complexity in cellular automata”Physica D101–35
