Chapter 7

NETWORK ANALYSIS

One of the important application areas of a GIS is facility management based on

network analysis. Specific areas of application could be to determine optimal and
shortest paths as a routing analysis, or allocating resources based on demand and capacity.
Much of this analysis is based on a set of connected linear features ie., network, that form
a framework through which resources flow. This framework could be visualised as a
road network through which vehicles move, a drainage network through which water
flows, electric links for electricity passage and so on. The real world is full of such
networks and these can be well represented as link graphs associated with a set of flow
constraints. Therefore, the representation, management and manipulation of
network linear features are an important module of a GIS.

1. What Is A Network

Network forms the infrastructure of the modern world. It is the system of

interconnected linear features through which resources are transported or communication
is achieved. The movement of people, transportation, distribution of services and
allocation and delivery of resources occurs through a network system (figure 1).

Figure 1. Drainage and road network

Network Module provides tools to -

 Find the shortest or minimum impedance path through a network (PATH)
 Most efficient path to a series of locations (TOUR)
 Assigns a portion of network to a location (ALLOCATION)
 Whether the location is connected to other (TRACING)

1
 Model the accessibility of location and interaction between location based on cost of
travel and communication (SPATIAL INTERACTION).

2. NETWORK DATA MODEL

It is a representation of the components and characteristics of the real world

network system. The model consists of network links, turns, stops, facility points, blocks
and nodes. The relationship between the characteristics of physical network systems is
represented by the elements of network model.

2.1 Impedance

Impedance measures resistance to movement. Impedance are attributes of arcs and

turns. Arc impedance is the amount of resistance required to traverse the arc from one end
to other. A larger impedance indicates more resistance to movement. The purpose of
impedance is to simulate the variable conditions along lines and turns in real network.
The results of an allocation or route will differ according to the impedance you assign to
the element in a network. The optimum path is the path of least resistance. Negative
impedance prevents movement, e.g. To indicate intersections where left turns are not
permitted, a negative value for the turn is used. One way street require a negative
impedance for the direction that cannot be traversed.

2.2 Network Elements in a GIS :

Each network consists of different elements, each of which could be associated

with an attribute defining the characteristics of the element. These two, in combination,
form the important part of the network analysis. The different elements and their
attributes are (figure 3) :

2.2.1 Links : The basic element of the network and serving as a conduit for the
movement of resources is a link. The connectivity of the links is an important aspect in
the network. The links have two types of attributes :
[Link] Resistance, which describes the amount of impedance offered by the links for the
flow of resources. The cost associated with traversing an entire network link is termed
the impedance of the link. A network link has two impedances; 'from-to' impedance and
'to-from' impedance. The impedance used depends upon the direction of arc traversed.
Impedance values are contained in the items defined by the user in the attribute table. A
negative link impedance signifies that the link can not be traversed in that direction. The
higher the value, the more the resistance offered to movement. Link resistance is a
measure of the impedance for traversing a link from one end to the other. The resistance
may be unidirectional or bi-directional. This is generally a user-defined value for each
link and could depend upon the characteristic of the network.

[Link] Resource Demand, is the number or amount of resources associated with each
line feature. For example, the number of students living along each road or the amount of

2
water required by people living along each pipeline, road capacity or width and so on.
Resource demand is especially critical for allocation problems.

2.2.2 Turns, qualifying the direction of flow of resources from one link to another
connected through a node. The turn is direction-specific and the flow of resources could
be restricted by the turns, for example, restriction of traffic taking a right or left turn at an
intersection (figure 2).

Figure 2. Turn Impedances

3
The attribute of turns relates to the additional resistance offered for negotiating a turn
from one link to another. The classic example of this is the time taken to negotiate left
turns and right turns at a traffic intersection would be different. As turns are direction-
specific, the attributes could be different for the turns in different directions.

2.2.3 Stops, representing locations where resources would be picked up or dropped off.
For example, a bus stop could be defined as a stop where passengers can be picked up
and/or dropped off. Resource demand are attributes of stops and are a measure of the
amount of resources to be picked up or dropped off.

2.2.4 Facility Points, which are locations that have a supply of resources to distribute to
links in the network, e.g., a reservoir that supplies a specific volume of water through
pipelinks. Facility points are also called as 'Centres'. Resource capacity is an important
attribute of a facility point and is a measure of the total resources that can be supplied
to/by the facility point. Another important attribute of the facility point is the influence
zone of the facility point a measure of the limit up to which resources can be supplied
from or received by a facility point.

2.2.5 Blocks, representing the locations through which no resources will flow. Blocks
are basically obstacles defined on the network to simulate and visualise a specific
condition of resource movement. Blocks do not have any attributes.

2.2.6 Nodes - These are end-points of the network links. Links are always connected at
nodes. Nodes represent intersection or interchange of road network, switches in power
grid etc.

Figure 3. Elements in a Network

EVALUATION OF NETWORK STRUCTURE

4
The structure of a network can be defined rigorously in mathematical terms specially in the graph theory.
Graph theory, as a branch of combinational topology provides us with appropriate tools which are suitable
for evaluation or analysis of network structure. The measures of network structure derived from graph
theoretical concepts may be classified into two groups.
a. non-ratio measures, and
b. ratio measures

a. Non-ratio measures: These measures are constructed predominantly as ratios between the whole system
and its individual elements. The examples of the non-ratio measures are the cyclomatic number (μ) and
diameter (δ).
Cyclomatic number (μ): This number is the arithmetic comparison between individual elements of the
system, and is fundamental indices of graph theory. It is defined as the count of the number of basic circuits
existing in the network. Mathematically it can be written as

μ = L- n + p
where L = number of edges or routes
n = number of vertices or nodes
p = number of non- connected sub-graphs

This index has two properties which are important for transportation studies.
i) The cyclomatic number of a linear network is equal to the maximum number of independent
circuits in the network.
ii) In a connected network, the cyclomatic number is equal to the maximum number of
fundamental circuits.

Diameter (δ): Diameter is an important measure of network structure. The diameter of a network
represents the maximum number of steps (links) required to move from any node to any other node through
the shortest possible routes within a connected network. If in any network, the number of steps (links) are
five to move from 4th node (say) to 5th node (say) through a shortest route then the diameter of the network
will be five.

b. Ratio measures: In view of the fact that non-ratio measures are not suitable for comparison of different
networks, this problem can be illustrate by the new types of indices which are called ratio measures. There
are three major groups of category, to measure the network structure-

i) Indices which express relationship between the distinguishable elements of the network, the
number of fundamental circuits, number of maximal circuits and the ratio of the observed to
maximum edges/vertices. Alpha (α), Beta (β), and Gamma (γ) indices fall in this category.
ii) Indices which represent relationship between the network as a whole and one of its individual
elements, whole network with respect to its edges. Eta (η), and Pi (π) are the two measures
falling in this group.
iii) Indices which express relationship between the network as a whole and the remaining
elements. Iota (ί), and Theta (θ) belong to this category.

A detailed description of these different types of indices is as follows-

Alpha (α) index: The Alpha index (α) is an adjustment form of the cyclomatic number. It can be defined
for non-planer graphs as the ratio of the observed number of fundamental circuits to the maximum number
of circuits which may be exist in the network. . A circuit is a loop in the network. If three nodes are
connected by two links, then there is no circuit among them, and there is only one way to go from any node
to any other node. If three nodes connected by three links, then one circuit exists because the three nodes
are linked by a loop. When a loop exists, each node has two ways to reach any other node in the network.

5
α index evaluates network structure in terms of the number of ways you can proceed from one node to
another. In order for α index to be meaningful, all nodes in the network must be connected. If a network is
divided into two separate groups of links that are completely separated, the evaluation of circuits is not
meaningful. To completely connect a network, the number of links must be at least one less than the
number of nodes (i.e. L=n-1). Every additional link beyond that required for the minimally connected
network creates a circuit. Thus, the maximum number of circuits in a network is equal to the difference
between the maximum number of links and the minimum number of links to the completely connect a
network i.e.

Cmax =Lmax - L = {3(n-2) – (n-1)} = 2n – 5

Thus, for non-planer graph, mathematically the α index can be expressed as

α = actual circuits/ maximum circuits

α = C / Cmax = C/ (2n-5)
α = (L - n + 1)/ (2n – 5)

Where „C‟ denotes the actual number of circuits.

In general, a better developed transportation network has higher values of α index which correspond to
higher levels of complexity and connectivity. This index is useful for evaluating the change in network
structure over time or comparing the structures of different networks.

Beta (β) index: Beta index is the simplest form of the three measures which record the relation between
two individual elements of a network and has been defined as

β=L/n

The logical basis of Beta index is similar to the μ and α measures. For highly connected network, Beta will
have high value and for simple structure, it will have a low value. Some important properties of β index are-
i) β index value for disconnected networks would always be less than 1. It would take zero value when
there are no edges in the network.
ii) β index value for any network structure with one circuit would always equal to 1.
iii) β index value exceeds 1 for a complicated network structure having more than one circuits.

Gamma (γ) index: The γ index is defined as the ratio of the actual number of links ( or edges) in a network
to the maximum possible number of links in a network. In a planar graph, the maximum number of links is
always equal to 3(n-2), where n denotes the number of nodes in the graph (i.e. Network of linear features).
Mathematically the γ index is expressed as

γ = L ⁄ Lmax = e / 3(n-2)

where „L‟ is the number of links in a network. The value of the γ index ranges between 0 and 1. A value
close to 0 indicates a simpler network structure with fewer links. A large value close to 1 indicates a better
connected network with more links. For applications based on non-planar graphs, such as those used in
airline transportation, the maximum number of links is equal to n(n-1)/2, instead of 3(n-2) in the
denominator.

Eta (η) index: The Eta index has been found to be quite useful when some spatial characteristics of the
network are under examination. Broadly speaking, the generalized form of the Eta index for any measurable
characteristic may be defined as the ratio between the total kilometers of the network and the observed
number of edges or

6
 η = average edge length = M/E

Where M= total network length in km

E= the observed number of edges

Pi (π) index: Let us assume that the total route length of a network system is analogous to the
circumference of a circle and the total mileage of all edges of the diameter of the network is analogous to
the diameter of a circle. Then the ratio between the length of the network and the length of the network‟s
diameter would always be a real number which analogous to π. Therefore the π index may be written as

π = C/d
where C is the total mileage of a given transport network and d is its diameter. The application of π index
to transportation network would give a numerical value which would be or equal to one.

Theta (θ) index: The theta index is the modified form of η index and may be represented as follows

θ = T/V
Where T is the total traffic flow, or the total volume of freight carried, and V is the observed vertices. Thus
the Theta index would denote the volume of freight per vertex.

Iota (ί) index: The iota index is quite useful for the analysis of networks as it has been developed on the
basis of following three aspects of networks:

i) structure
ii) length, and
iii) functions

The index may be written in the form ί = M/T

Where, M is the total route length and T is the number expressing the total traffic flow. This is widely used
in transportation studies under the name- “Average distance per tone”.

3. NETWORK ANALYSIS:

Network analysis in a GIS may be dependent on the utilities under concern, as

each utility service would have customised requirements as discussed above. However,
fundamental to all these requirements would be the following analysis;

3.1 Path Determination: Path finding is the process of calculating an optimal path
through series of points in a network and simulating the flow of resources through them.
Path finding functions could be categorised into two major groups, the applications of
which are different:

3.1.1 Source-Destination path, as an optimal path from a pre-defined source to a pre-

defined destination. In this case, the path of least resistance is determined from the
source to the destination by evaluating the link resistance and also the turn resistance for
all connected links. The minimum resistance is a cumulation of the link and turn
resistance (figure 4).

7
3.1.2 Optimal Cyclic path, mainly as an implementation of the set covering problem, an
example of which could be the Travelling Salesman‟s Problem. In this case, the problem
is to determine the optimal path after visiting all or a specified set of links in the network.
In this case, the optimal path is determined from a matrix of resistance for each pair of
links in the network. The matrix is evaluated to determine the order of visiting links in
the network and to define the actual path. Optimal cycle path is also called 'TOUR'. It
determines the order in which the stops are visited. The ordering of stops is
accomplished by determining the minimum path between each stop and every stop, based
on the impedances.

Figure 4. Routing based on arc impedance

3.2 Resource allocation or distribution analysis: Resource allocation is a type of
districting problem where links are associated with resource centres. As links are
assigned to a centre, a portion of the resource of the centre is allocated to meet the
demand of the link. Links are allocated based on the least resistance rule (the cumulative
resistance of the link resistance and turn resistance, as in the path-finding procedure).
The allocation procedures occurs simultaneously for each facility point and for all
possible turns/links at an intersection in successive passes (figure 5).

8
 Figure 5: Streets Allocated to school

3.3 Utility locating or siting analysis

A variation of the allocation problem is to determine the location of facility points for
a network (as against the earlier case where the facility point locations are specified) and
also determine their capacities to meet the demands of the network. This variation is
useful for planning facility locations and capacities. The location of facilities is
determined based on a set of constraints defined by the facility points such as capacity
associated with facility, influence zone area, number of facilities and so on, and the flow
restrictions such as demands of each link and so on.

3.4 Finding the Closest Facility

Closest facility refers to anything providing a certain type of service that is closest to
a given location, known as an event. It can be the closest fire hydrant to a fire, or the
closest drug store to a house etc. In some situations, one facility is not enough. For
example, a taxi dispatcher might need to send three taxis to a destination.

4. Application Context Of Network In GIS

 Network applications in a GIS are oriented towards planning, administering and

operational management of resource facilities. Some of the crucial application areas
are:

 Traffic routing for transportation planners, facility managers for efficient routing of
facility movement and so on;

 Facilities management for planning demand-capacity ratios for resources and optimal
allocation of resources based on demand and capacity;

 Districting or partitioning for associating links to facilities to define a service area for
each facility;

 Facility locating, siting and locating of different facilities.

References:

Burroughs, P.A (1986)., Principles of Geographical Information Systems for Land

9
 Resources Assessment. Oxford University Press.

Jones, Christopher (1997), Geographical Information Systems and Computer

Cartography. Addison Wesley Longman

Rao, Mukund (1992). Network module for ISROGIS: design consideration and
specifications. Space Applications Centre - SAC/RSA/SPUCC/TN73.

Rao, Mukund (1993). 3-D GIS: Concepts, Lecture notes prepared for the training course
on GIS for Resources Management and Development Planning held at Space
Application Centre, Ahmedabad, 23 August - 11 September.

10