Home | Business News | Browse by Publication | C | Cartography and Geographic Information Science

Network analysis in geographic information science: review, assessment, and projections.

Article Excerpt
Introduction

Network data structures were one of the earliest representations in geographic information systems (GIS), and network analysis remains one of the most significant and persistent research areas in geographic information science (GIScience). This paper will describe the theoretical basis for network data structures and review several major types of network data structures as they have historically been implemented in GIS. This is followed by a concise but comprehensive review of the current capabilities for network analysis in GIS, and the consequent deficiencies in GIS implementations of networks. A set of challenges is suggested for network analysis in GIS, through increased implementation of existing network theory, through expansion of existing theory and practice in the areas of network design and location, and through interactions with a wide variety of other disciplines.

The Theoretical Basis for Network Analysis in GIS

Network analysis in GIS rests firmly on the theoretical foundation of the mathematical sub-disciplines of graph theory and topology. Any graph or network (the terms are synonymous in this context) consists of a set of vertices and the edges that connect them. Within graph theory there are methods for describing, measuring, and comparing graphs, and techniques for proving the properties of individual graphs or classes of graphs. Some elements of graph theory are not concerned with the cartographic characteristics (e.g., shape or length) of the features that comprise a network but, rather, with the topological attributes of those features. The topological invariants of a network are those properties that are not altered by elastic deformations. Therefore, properties such as connectivity, adjacency, and incidence are topological invariants of a network, since they will not vary if the network is deformed by a cartographic process, such as a projection. The permanence of these properties allows them to serve as a basis for describing, measuring, and analyzing networks.

Graph theoretic descriptions of networks can range from simple statements of the number of features in the network, the degree of the vertices of the graph, or the number of cycles in a graph, to more complex descriptions based on structural characteristics of networks. In some cases these network structures can be classified into idealized network types (e.g., tree networks, hub-and-spoke networks, Manhattan networks, etc.). In turn, these ideal types may be proven to have properties that encourage their use for particular applications.

Moving beyond description, quantitative measures of the properties of graphs can be computed through network indices. Measures such as the Beta, Mpha, and Gamma indices (Kansky 1963) measure the relative connectivity of a network by comparing the number of edges to the number of vertices (in the case of the Beta Index), or by comparing proven properties of graphs to observed properties. Additional measures and analytical techniques exist within graph theory for applied instances of networks, which depend on non-topological properties such as edge length or capacity (Rodrigue et al. 2006). Although this is not the appropriate venue to review them there are many more advanced graph theoretic techniques for describing networks, for categorizing them, and for proving their properties (Harary 1982; Wilson 1996).

Implementations of Network Data Structures in GIS

While the graph theoretic definition of a network remains constant, the ways in which networks are structured in computer systems have changed dramatically through the history of GIScienee. Network data structures must store the edge and vertex features that populate these network datasets, the attributes of those features, and--most importantly for network analysis--the topological relationships among the features. The choice of a network data structure can significantly influence the analyses that can be performed.

Non-Topological Data Structures

The earliest computer-based systems for automated cartography stored network edges as independent records in a database. Each record contained a starting and ending point, and the edge was defined as the connection between those points. Attribute fields were associated with each record, and some implementations included a list of "shape points" that approximated curvature. This structure did not contain any information regarding the topological properties of...