5.4 Network Applications

Networks are used in applications to find how different objects are connected to each other.

The connectivity is often expressed in terms of adjacency and path relationships. Two nodes are adjacent if they are connected by a link. There are often several paths between any two given nodes, and you may want to find the path with the minimum cost.

This topic describes some typical examples of different kinds of network applications.

• Road Network Example
  
• Subway (Train) Network Example
  
• Multimodal Network and Temporal Examples
  
• Utility Network Example
  
• Biochemical Network Example
  

5.4.1 Road Network Example

In a typical road network, the intersections of roads are nodes and the road segments between two intersections are links. The spatial representation of a road is not inherently related to the nodes and links in the network. For example, a shape point in the spatial representation of a road (reflecting a sharp turn in the road) is not a node in the network if that shape point is not associated with an intersection; and a single spatial object may make up several links in a network (such as a straight segment intersected by three crossing roads). An important operation with a road network is to find the path from a start point to an end point, minimizing either the travel time or distance. There may be additional constraints on the path computation, such as having the path go through a particular landmark or avoid a particular intersection.

5.4.2 Subway (Train) Network Example

The subway network of any major city is probably best modeled as a logical network, assuming that precise spatial representation of the stops and track lines is unimportant. In such a network, all stops on the system constitute the nodes of the network, and a link is the connection between two stops if a train travels directly between these two stops. Important operations with a train network include finding all stations that can be reached from a specified station, finding the number of stops between two specified stations, and finding the travel time between two stations.

5.4.3 Multimodal Network and Temporal Examples

Multimodal networks are networks that consist of multiple modes, such as a network consisting of driving and walking routes. They are usually modeled as individual networks (of the specific mode) and are treated as an aggregate network so that routes of single mode as well as multiple modes can be represented and computed. In general, multimodal networks are "connected" by schedules of different modes, and in such cases they are also temporal networks. An example is to compute an itinerary with walking to nearest bus stop, taking the fastest bus route, getting off at the stop that is closest to the destination, then walking to your destination. You could also add modes like driving or flight to be taken into consideration.

Temporal modeling and analysis adds a temporal (time) dimension to network modeling and analysis. The time factor provides cost and/or constraints on top of static (non-temporal) networks. An example is to consider traffic patterns (time-dependent travel time costs) instead of static travel-time costs.

Many metropolitan transportation networks consist of multiple modes such as buses, subways, and commuter rail lines, where transfers across modes are possible (for example, from a bus to the subway). Each transportation mode has a component network within the larger transportation network. The component networks can be modeled using nodes and links, and the transfers across modes can be modeled as links that connect the stops where transfers are possible.

An important feature of such multimodal transportation networks is their schedule-based operation. When performing common network operations such as computing the fastest route from a start point to an end point, the schedule information and possible transfers across modes must be considered. The schedule information at stops can be represented as user-defined data at the nodes representing these stops. Examples of operations that use schedule information in a multimodal network are (A) finding the fastest route (minimum travel time) from a start point to an end point for a specified start time, and (B) finding the latest departure time at a start point to reach an end point by a specified arrival time.

5.4.4 Utility Network Example

Utility networks, such as power line or cable networks, must often be configured to minimize the cost. An important operation with a utility network is to determine the connections among nodes, using minimum cost spanning tree algorithms, to provide the required quality of service at the minimum cost. Another important operation is reachability analysis, so that, for example, if a station in a water network is shut down, you know which areas will be affected.

5.4.5 Biochemical Network Example

Biochemical processes can be modeled as biochemical networks to represent reactions and regulations in living organisms. For example, metabolic pathways are networks involved in enzymatic reactions, while regulatory pathways represent protein-protein interactions. In this example, a pathway is a network; genes, proteins, and chemical compounds are nodes; and reactions among nodes are links. Important operations for a biochemical network include computing paths and the degrees of nodes.