Robustness Analysis of City Road Network at Different Granularities - Space-Time Integration in Geography and GIScience - page 131

8.3.2 Beijing Road Network Characterization

The analysis, discrimination, and synthesis of complex networks therefore rely
on the use of measurements capable of expressing the most relevant topological
features (Newman 2010 ). The efficiency of a network is the basic function of a
transportation network. It is usually described by the average length of the shortest
paths L which is regarded as a sign of global efficiency and clustering coefficient
C which is considered as the local efficiency (Watts and Strogatz 1998 ). Here L
measures the typical separation between two nodes in a graph while C measures the
cliquishness of a typical neighborhood. The definition is as follows:

n .n 1/ X v 2 V X w ¤ v 2 V d .v; w/

1

L D (8.1)

Where n is the number of nodes and d(v, w) denotes the length of the shortest
path between node v and w which means the number of edges in the shortest path
connecting the two. If the graph is not connected, L is the average path length of the
largest connected component of the graph.
L measures the global transport efficiency in the network. A small L implies
a short path length between nodes and the dynamic flow of the network can be
transmitted faster. For instance, the social networks are known to have very short
average path length, with the “Six degree of separation”, where L D 6. Comparing
with the population of the world, the length is quite small, thus a network with a
small L is called small world network (Watts and Strogatz 1998 ).
In contrast, cluster coefficient which measures the local transport efficiency is
defined as:

n X v 2 V C v

1

C D (8.2)

Where n is the number of nodes and C v denotes the fraction of the actually existed
edges between the neighbors of C v compares to the all allowable edges. A higher
C means a more clustered neighborhood and the flow can be transmitted more
efficiently in the local area.
Tab le 8.1 shows these two basic characteristics of the Beijing road network
represented in three dual graphs.
Where N is the node number in the network and E is the edge number. L and C are
calculated using the formulas introduced before. Table 8.1 confirms that the different
representation can provide different structural information on the same initial road

Tabl e 8. 1 Characterization
of Beijing road network

N E L C

Segment-based 16,491 35,575 45.14 0.43

Stroke-based 377 833 4.86 0.18

Community-based 1,594 4,124 13.65 0.46