Geographic networks analysis: a graph-based model for analyses the roads networks impact on land cover

Morgado et al. Geographic networks analysis Proceedings of 7VCT, Lisbon, Portugal, 11-13 October 2011 | 223 Geographic networks analysis A graph-based model for analyses the roads networks impact on land cover Paulo MORGADO1; Nuno COSTA2 1Centro de Estudos Geográficos/Instituto de Geografia e Ordenamento do Território Alameda da Universidade, 1600-214 Lisboa, Portugal +351 217940218, [email protected] 2 Centro de Estudos Geográficos/Instituto de Geografia e Ordenamento do Território Alameda da Universidade, 1600-214 Lisboa, Portugal +351 217940218, [email protected] Keywords: graph-theoretic measures, geographic networks, geocomputation, GIS, Land-use Introduction To claim that all geographic networks are “the same” or that could they could be “treated” the same way and analysed by the same model may sound as an easy analogy. Are stream systems, transport systems and communication systems the same? No, they are not. They have different origins, configurations and structures. However, they also share equivalent spatial structures to which we can apply the same mathematical models. In fact, geographic network analysis (GNA) is not new (see Haggett and Chorley, 1969). However due the limited data available and poor computing resources, geographers tend to drive their attention to other topics, or have revealed a preference for more descriptive studies over modelling and measuring. It’s trite to say that transportation networks amplify the development of societies [1] and provide the blueprint for territory organization. We could therefore conclude that without transportation networks civilization, as we know it, could not exist [2]. This statement frames transport networks, either stream networks, road networks, railway networks or airline networks as key subjects in geographical research and explains why geographers have been pioneers in the research of transport networks and their territorial impact on regional development (see Garrison, 1960; Garrison and Marble, 1961; Kansky, 1963; Taaffe and Gauthier, 1973). Although the use of computers in geography studies is not new - ever since the early 1960 quantitative geographers have replaced calculators for computers in their statistical and mathematical modelling -, geographers have neglected the full potential of computing. Only recently, due to the GIS revolution of the mid 80s and the availability of high performance computing, did geography recover her quantitative legacy [3]. There is a natural affinity between Graph theory and Geography. Topology, which is a branch of mathematics that encloses graph theory, also echoes Tobler’s groundbreaking work (e.g. spatial dependence, spatial interaction models and GISc) [4]. The main objective of this paper is to test accessibility measures and analyse Morgado et al. Geographic networks analysis 224 | Proceedings of 7VCT, Lisbon, Portugal, 11-13 October 2011 what impact they have on land cover changes. To do this we have built and implemented a graph-based model (geo_graph) into a GIS program, e.g. ArcGIS, and tested it on road networks. The paper is organized as follows. First, we review and present the measures integrated in the model, and what they represent for our case studies. Second, we present the architecture of the model, the cautions that have to be taken into account when preparing data to be analyzed through the model, as well the reason that explains why we have chose to develop our own model to run in a hosted GIS program instead of using some other network analysis program. Third, we present and discuss the main results and underline its ‘critical points’, and finally we introduce a section on further developments. Graph-theory measures From the point of view of geography, graph-theory measures are a powerful tool not only to illustrate transport networks structural problems, but also to describe and analyse network structure and accessibility, and to evaluate and compare the evolution of networks through time. The use of graph theory measures allow us to understand how objects covering the surface interact and what are the implications they have on spatial organization [5]. We can split graph-theory measures into two groups: the connectivity measures and the accessibility measures. To compare the structural complexity of the networks, we need measurements that allow us to describe the degree of network connectivity. This is what connectivity measures do. However, if we need to identify what has changed individually on the network and causes these structural changes then accessibility measures (table 1) are what we need. Graph-theoretic measures of nodal accessibility can be considered as an upgrade of network analysis, as they can analyse networks as a whole as well consider networks individual properties, e.g. nodes accessibility, which are fundamental for understanding spatial networks and they territorial impacts. Name Índex Meaning Remark Shimbel Índex of accessiblitiy 1 n ij ac dij ¦ Indicates the number of links to get from node i to node j , taking the shortest-path. Lower the value, higher t he node accessibility. Average Shimbel Índex of accessiblitiy 1 1 n j i dij AC n  ¦ Indicates the average of the sum of the shimbel index of a node to all other networks nodes. Lower the value, higher the node accessibility. Table 1 – Graph-theoretic measures of nodes accessibility To measure the accessibility impact of nodes on the network we need to treat graph as a matrix. There are a set of graph-theoretic accessibility measures derived from a Morgado et al. Geographic networks analysis Proceedings of 7VCT, Lisbon, Portugal, 11-13 October 2011 | 225 set of matrix, (e.g. C matrix - gives you the direct connections between nodes), T matrix (gives you the direct and undirect connections between nodes), D matrix or Shimbel matrix (gives you the topologic shortest-distance between any pair of nodes) and L matrix (gives you the real shortest-distance between any pair of nodes), but for this paper we only going to refer the ones resulting from matrix D, L (extremely important when studying spatial networks) and Pi matrix (gravity model – interaction potential) then cross them with some spatial analysis, namely mean centre and standard deviational ellipse, and cross-tabulation for land-use changes. Figure 1: Matrix Cn Different from the matrix C, D and T, matrix L is a weighted matrix, in this case weighted by the physical distance (km2) between any pair of nodes of the road network. We can compute matrix L2, L3, …, Ln based on the following algorithm: 21 1 min( ( 1,... ) ( 1,... )) ij ik jk LLknLkn  (1) This sets the accessibility measures consider in our model (geo_graph) evaluating and measuring the impact of road networks on the territory and in particular, for the last two time periods in analysis, on land-use changes. In addition, we have also integrated into the geo_graph model some algorithms from complex networks, as the betweenness centrality index, which measures how often a node appears on shortest path between nodes in the network. Geo_Graph model architecture We can perceive models as a simplified structure of reality which presents supposedly the most significant features or relationships in generalized and sometimes abstract forms. The model build-up here is a geocomputation product, as it wraps intensive use of computing tools and basic computer science. We have decided to build-up our own model because: (i) GIS have become a fundamental tool for geographic analysis and geographic research; (ii) although Morgado et al. Geographic networks analysis 226 | Proceedings of 7VCT, Lisbon, Portugal, 11-13 October 2011 geographers main study object demands high computational power GIS programs still can’t fulfil all the geographic analysis demands. Therefore we have chosen to build-up a ‘tailored’ program. Geo_graph model is developed on a programming language (Visual Basic Application) that could be used as a script in most of GIS programs so it could appear as a plug-in in GUI. No programming skills are needed, and this way we make our model available for a larger audience. Users only have to focus on the spatial issues. This way, not only it reduces time and effort, as minimizes the probability for human error. # Model Description 1 Main Model where we define the sequences of operation to realize 2 CMatrix Model that allow representing graph as a matrix and where we define the matrix calculations. 3 NetworksMXDAnalysis Model that allow take graph created in a GIS environment (geometric network) into a matrix, so CMatrix could be executed. 4 Dijkstra Shortest-path algorithm. 5 NetworkMatrix Model where the connectivity and some accessibility algorithms are settle. The outputs are automatically exported in a txt format files with data and time named. Table 2 – Geo_graph model architecture in VBA Main results To test our model and take full advantage of the GIS spatial analysis and graphtheoretic measures we have considered Portugal mainland highway networks as our study object, from ancient roman vias, through the 1800 main roads, 1945 national plan, 1985 highway plan, to the 2000 highway plan (figure 2). Figure 2: Mainland roads networks from different time periods in Portugal The accessibility measures have revealed a spatial dynamic of settlements, underlined by crossing them with spatial statistics analysis e.g., mean center and Morgado et al. Geographic networks analysis Proceedings of 7VCT, Lisbon, Portugal, 11-13 October 2011 | 227 standard deviational ellipse. Precisely, a trend of coastal approach emerges (figure 3). Figure 3 –Mainland settlements most accessible through time in Portugal Accordingly to figure 3, the most accessible settlement is (Ponte de Sôr) – due to roman vias configuration – followed up to North (Abrantes settlement, due to 1800 road network), and it keeps on going to north centre to the Vila de Rei settlement and the Ansião settlement (due to 1945 and 1985 road network configuration that have privilege coast for road investment). That trend reveals a policy of road investments in the year 2000 that reinforces Coimbra settlement position. We could also see some results that help to explain some spatial decision policies regarding the plan for road networks and territory, by analyzing some other geo_graph accessibility measures (table 3). Morgado et al. Geographic networks analysis 228 | Proceedings of 7VCT, Lisbon, Portugal, 11-13 October 2011 Shimbel index (D) Shortest geographic distance (L) Spatial interaction potential (Pi) Betweenness (B) Roman vias Ad Septem Aras (Campo Maior) - Ad Septem Aras (Campo Maior) 1800 Madalena Madalena - Madalena 1945 Vila de Rei Vila de Rei Coruche Coruche 1985 Leiria Coimbra Coimbra Leiria 2000 Coimbra Coimbra Table 3 – Accessibility measures likeness thought time By crossing these accessibility indicators with land cover classes and analysing changes in an 8km radius, the minimum distance between highway nodes, we can verify that there is an impact on land cover dynamics e.g. spread of urban class and the decrease of agricultural and forest areas, around Coimbra (table 4). artificiel surfaces agricultural and agro-forest areas Forest and semi-natural areas water bodies artificiel surfaces 18,395,100.00 0.00 0.00 0.00 agricultural and agro-forest areas 3,886,700.00 90,841,200.00 34,300.00 0.00 Forest and seminatural areas 1,413,600.00 211,500.00 83,443,500.00 0.00 water bodies 0.00 0.00 0.00 2,836,700.00 corine land cover 1990 Corine land cover 2000 Table 4 – Land cover changes between 1990 and 2000 in a 8km radio around the most central and accessibility settlement in Portugal mainland, Coimbra Further developments Further developments must focus on how to integrate complex networks algorithms into the model, e.g. small world, clustering coefficient and hubs and test the model on larger spatial and also non-spatial networks, but that we could add a geographic reference, e.g. economic networks (companies business partnerships), scientific networks (universities and faculty’s scientific projects and inter-courses), sport networks (football-clubs contracts), just to mention some. References [1] Ascher, François (2011), Les nouveaux principles de l’urbanisme, Editions de l’Aube, Paris [2] Bell, M. and Lida, Y. (1997), Transportation network analysis. Ed. John Wiley&Sons, Chichester Morgado et al. Geographic networks analysis Proceedings of 7VCT, Lisbon, Portugal, 11-13 October 2011 | 229 [3] Openshaw, S. and Abrahart, R. (1996), Geocomputation. Proceeding1st international conference on Geocomputation, University of Leeds, Leeds [4] Sui, D. (2004), Tobler’s first law of geography. A big idea for a small world? Annals of the American Association of Geographers, 94, pp. 269-277 [5] Taaffe, E. and Gauthier, H. (1973), Geography of Transportation. In Foundations of Economic Geography Series. Prentice Hall, Englewood Cliffs [6] Openshaw, S. and Abrahart, R. (1996), Geocomputation. Proceeding1st international conference on Geocomputation, University of Leeds, Leeds