Given the ubiquitous nature of infrastructure networks in today's society, there is a global need to understand, quantify, and plan for the resilience of these networks to disruptions. With the development of transport infrastructure, vulnerability analysis is a core process of man-made systems safety management. The main purpose of the paper is to identify the critical road sections and intersections in a road network which have great in uence on the normal functionality of the urban territory. In this paper the structure (topology) of highway network of Vladivostok city in Russia was investigated and analyzed based on the graph theory. The network model of the road system was constructed using Open Street Map data.
The quality of life of people in the present time is largely determined by the state of development of the technosphere. Modern society relies upon the collection of systems and institutions known as the infrastructure to support the welfare and living standard of people. A downside of this dependency is that sudden failures and disruptions in the systems may cause severe strains on the society.
With the development of economies more and more people living in cities, tra c congestion has become a very serious problem in many large cities of the world. Road network disruptions can threaten the possibility for people to receive medical care and other critical services. More generally, they impair people's accessibility to daily activities such as commuting to work and doing the shopping. Furthermore, there may be large costs associated with remedies and restoration of the transport system to a fully operational state.
Due to a number of catastrophic events, vulnerability analysis has been an area of increasing interest and research since the mid 1990's. There have been a number of major events that have disrupted transport networks around the world, but there are also everyday events that can cause disturbances such as accidents, road works or vehicle breakdowns. Disruptions can be caused by a wide range of events, some of ? This work was supported in part by the FEB RAS Project No. 15-I-4-007 (0262-2015-0063) Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org which originate within the transport system, including tra c accidents and technical failures. Other events are external strains imposed on the system, often caused by nature, as with oods, landslides, heavy snowfall, storms, wild res, earthquakes, etc. While accidents and technical failures may have limited extents, disruptions caused by nature may cover large areas in the road network.
Vulnerability is a generalized conception. There are a lot of di erent de nitions of
vulnerability. Vulnerability is usually portrayed in negative terms as the susceptibility
to be harmed. It is degree to which a systemic susceptible to and is unable to cope with
adverse e ects. The concept of transport infrastructure (road network) vulnerability
is not uniform so far [
One important observation giving rise to the broader studies of the topology of networks is that \the structure a ects function". In other words, there exists a large extent of interactions between network structure and its dynamics, which makes the study of the network topology crucial. In particular, this is true in the case of technological and physical networks where system topology is formed to support certain activities towards operational and service objectives. Subsequently, any change in the network topology will have consequences in terms of system operation and its ability to function.
According to the former researches, the concept of road network vulnerability is to
emphasize the loss or e ect after the network has been attacked by an accident [
Road network vulnerability analysis can be de ned as the study of potential
degradations of the road transport system and their impacts on society, modelling the road
infrastructure as a network with links (road segments) and nodes (intersections) [
The main purpose of road network vulnerability assessment is to nd the weak element, in other words, to nd the key point of the whole network where the loss is the most signi cant when the same level of attack is su ered. In this paper, we propose the method to evaluate the vulnerability of the network with respect to the loss of a road link, e.g. due to a car accident, road work or other jamming occurrences.
The recent advances in the eld of complex networks [
Graph theory is utilized to study the structure vulnerability of road network. Structural (topological) vulnerability refers to the systems own inherent instability and sensitivity. Road network is taken as undirected graphs which show the general structure of road network without considering the actual ow.
Let us consider a network of roads (hereafter also called links or edges) connecting a number of locations (hereafter also called nodes or vertices). The topology can be represented as a graph G = (V; E); V is the set of nodes, E is the set of edges.
There are several statistical measures commonly used to characterize the structure of complex networks and its vulnerability:
between vi; vj 2 V , n is the number of vertices in G. { degree centrality CD(v) = deg(v) is de ned as the number of edges connecting with node v. { betweenness centrality (v) =
P iji(jv) , where ij is the total number of shortest i6=v6=j paths from node i to node j and ij (v) is the number of those paths that pass through v.
1 P d(vi; vj ), where d(vi; vj ) is the shortest distance { average path length lG = n(n 1) i6=j
From the point of view of the topological characterization of the network, centralities are typically used to measure the vulnerability of the nodes. Degree tends to describe the importance of node from the local view, while betweenness tend to describe the importance of node from the overall view. 2.1
According to our concept of the topological vulnerability, de ned in the introduction together with nding vulnerable nodes we are also interested in failures on the network links. Under the topological edge vulnerability of the road network in this paper will understand the edge weight, de ned as the length of the shortest alternative paths through the nodes left after removal checked edge. Thus, the higher is the edge weight, the more vulnerable it is. To access edges vulnerability is proposed an algorithm consisting of several steps.
{ Step 1. Finding clusters in the network. { Step 2. Selecting the links passing through the clusters. { Step 3. The quantitative assessment of the found edges vulnerability.
OpenStreetMap (OSM) project is proposed to use as a cartographic base [
The result of Louvain clustering is a list of vertices with labels as clusters numbers. Therefore, the second step is to traversing the G edge list to nd edges which vertices belong to di erent clusters.
To determine the quantitative value of the topological edge vulnerability used another developed algorithm consisted of ve steps.
{ Step 1. For all edges set the initial edge weight w equal to +1. { Step 2. Remove checked link ejc from the network. Save start vjs and end vje node. { Step 3. Find the shortest path through vjs and vje nodes and calculate the length lse of the route.
j { Step 4. If the path exist then wj = ljse. Restore the ejc edge.
c { Step 5. Go to next ej+1 in the list.
The result of the algorithm is the list of edges with their weights. Edges with no alternatives routes have in nity weight. The failures of such links lead to serious consequences. The implementation of this algorithm was also carried out with the python and NetworkX module. The shortest path was calculated with Dijkstra's algorithm. 3 3.1
Today OSM map is the only one map that can be downloaded for free on almost any device, and the primary source of geodata for organizations that want to save on a cartography.
More than decade of e orts of numerous volunteers developing the Open Street
Map project[
Topological Vulnerability of Vladivostok city highway network Developed algorithms and programs were applied for construction the network of Vladivostok city in Russia. To obtain Vladivostok city transport network we download OSM XML le with Primorsky region map and prune it with osmosis program and POLY le that describes the city boundaries. The resulting Vladivostok OSM- le contains 132 552 node (node osm) and 7 818 lines (osm way). After the application of the developed program the topology of the Vladivostok city highway network as graph G was built. The network consist of jV j = 10480 nodes and jEj = 12574 edges.
Figure 2 illustrates a degree distribution of the nodes.
Figure 3 illustrates a scaled to size numerical values of the betweenness centrality nodes measure.
Interestingly, such nodes degree distribution is typical for natural structures like cracks on the earth surface or blood vessels. This suggests that the Vladivostok city topology formed in random way.
Betweenness centrality re ects the extent to which a node lies in between pairs or groups of other nodes of the graph. This can be also stated as the extent to which a node is an intermediate in communication over the network. Based on a priori knowing of the special features of the transport streams and problem zones of the Vladivostok city can be said that only a part of the results obtained by the evaluation in line with the real situation. Therefore, the task of developing new assessment remains valid and important.
The result of this algorithm is more consistent with expert assessment. It was found the central streets of the city and major transport interchanges. However, the resulting score is still far from perfect. 4
On the basis of network vulnerability research, the highway road network could be better planned and constructed, the network topology could be optimized and the most important nodes and links should be pay more attention to protect and operate. Complex network theory and graph theory are adopted to analyse and calculate the topological vulnerability of road network in Vladivostok city. To work with highway network as graph it was developed an information-computational system that allows to import data from OSM project in the spatial database and export it to graph edge list. On the process of vulnerability analysis and calculation, singly based on single metric is not accurate enough. Therefore, the problem of new structural vulnerability metrics developing is still important and up-to-date.