Network Modeling

Background

The most familiar network models are those used to represent the networks with which much of the population interacts every day: transportation and utility networks. Figure 1 shows three networks (roads, rivers, and railroads) with their typical GISystems representations. For most, the objects that these networks represent are obvious due to a familiarity created by frequent use. Cartographic conventions serve to reinforce the interpretation of the functions of these networks. It is clear that these three networks represent fundamentally different phenomena: roads and railroads are man-made, while river networks are natural. Rivers flow only in one direction while—depending on the network model—roads and railroads can allow flow in both directions. Perhaps most importantly, different types of activities occur on these networks. Pedestrian, bicycle, car, and truck traffic occur only on the road network, and the others are similarly limited in the vehicles that use them.

Figure 1.

Geographic network datasets

Similar idiosyncrasies could be noted for many other types of networks that can be modeled in GISystems, including utility networks (electricity, telephone, cable, etc.), other transportation networks (airlines, shipping lanes, transit routes), and even networks based on social connections if there is a geographic component. Although the differences among the variety of networks that can be modeled allow for a great diversity of applications, it is the similarities in their structure that provide a basis for analysis.

Graph Theory For Network Modeling

Networks exist as a general class for geoinformatic research based on the concept of topology, and the properties of networks are formalized in the mathematical sub-discipline of graph theory. All networks or graphs (the terms can be used interchangeably), regardless of their application or function, consist of connected sets of edges (a.k.a. arcs or lines) and vertices (a.k.a. nodes or points). The topological properties of graphs are those that are not altered by elastic deformations (such as a stretching or twisting). Therefore, properties such as connectivity and adjacency are topological properties of networks, and they remain constant even if the network is deformed by some process in a GISystem (such as projecting or rubber sheeting). The permanence of these properties allows them to serve as a basis for describing, measuring, and analyzing networks.