A distance-based tool-set to track inconsistent
urban structures through complex-networks
Gabriel Spadon1 , Bruno B. Machado2 ,
Danilo M. Eler3 , and Jose F. Rodrigues-Jr1

arXiv:1803.09136v1 [cs.CE] 24 Mar 2018

1

2

University of Sao Paulo, Sao Carlos – SP, Brazil
Federal University of Mato Grosso do Sul, Ponta Pora – MS, Brazil
3
Sao Paulo State University, Presidente Prudente – SP, Brazil
spadon@usp.br, bruno.brandoli@ufms.br,
daniloeler@fct.unesp.br, junio@icmc.usp.br

Abstract. Complex networks can be used for modeling street meshes
and urban agglomerates. With such a model, many aspects of a city can
be investigated to promote a better quality of life to its citizens. Along
these lines, this paper proposes a set of distance-based pattern-discovery
algorithmic instruments to improve urban structures modeled as complex
networks, detecting nodes that lack access from/to points of interest in
a given city. Furthermore, we introduce a greedy algorithm that is able
to recommend improvements to the structure of a city by suggesting
where points of interest are to be placed. We contribute to a thorough
process to deal with complex networks, including mathematical modeling
and algorithmic innovation. The set of our contributions introduces a
systematic manner to treat a recurrent problem of broad interest in cities.
Keywords: Complex Network; Network Analysis; Urban Structure.

1

Introduction and Related Works

The synergy of real-world systems can be described as complex networks that
exchange information through their entities’ relationships. Such networks can
model complex systems from neuronal networks to subway systems [1] and also,
they can shape cities when linking the network topology with georeferenced data.
By analyzing the complex network of a city, it is possible to extract features
that can describe urban problems, which are meaningful indicators for city
planners [2]. Such features can reveal, for instance, sites where social activities
are more intense, regions where facilities should be placed, and neighborhoods
that lack street access. Particularly, these networks can expose distance-based
inconsistencies, which is how we refer to nodes that lack efficient street access
from/to others in the same network, possibly resulting in structural bottlenecks.
Along these lines, we identified a lack of methods to analyze and improve the
structure, mobility, and street access of cities. Consequently, in this paper, we
contribute with a mathematical tool-set and algorithms to track distance-based

inconsistencies by analyzing the complex-network topology of a city. Our results
have implications for the street access, supporting a finer street planning by
enhancing mobility indicators and providing better city’s structural assessment.
The core assumption of this study is that the network is supposed to provide
streets that render the shortest distance between places. In this regard, our
tool-set uses two distance-functions to track nodes that do not provide shortest
distance routes between them and other nodes that are of some interest. Nodes
that fail in providing minimum-length routes are considered to be inconsistent
nodes, which are evidence of problems in the city structure. Accordingly, in the
face of an inconsistency, we raise two hypotheses: (A) the network lacks a more
appropriate mesh; or, instead, (B) the city lacks its points of interest placed in
better locations. The first one indicates the need for new points of interest to
distribute their load. Contrarily, the second one indicates the need for relocating
points of interest because the topology of the terrain cannot afford new streets.
A vast number of studies have been conducted to analyze inherent properties
and behaviors found in cities. For instance, multiple metrics have been adopted to
explain their structural conditions [3], their intense traffic of vehicles [4], and the
emergence of collective behavior [5]. In other studies, the authors centered on the
geometrical perspective of the network [6], and on the elements positioning [7, 8].
Furthermore, there are those who reviewed the role of the city elements [9, 10],
that addressed the support to the urban planning and design [11, 12], and
that improved the facility-location analysis and planning of street meshes [13].
In addition to the ones that inspected the effectiveness of the underground
systems [10] and the improvement of long-range connections [14], besides those
who defined the concept of accessibility through complex networks and cities [15]
and that tested the centrality of cities considering their space syntax [16–18].
In this paper, we contribute with a tool-set that improve the analysis of
cities by tracking inconsistent urban structures through complex networks. This
proposal follows by showing that the distance between two nodes can reveal
ill-located points of interest and that such information can be used to make a
city better distance-efficiently to their citizens. To present our contributions, this
paper is organized as follows: Section 2 discusses our mathematical formulation
and related algorithms; Section 3 discusses the results about the applicability of
the proposed tool-set; and, Section 4 presents the conclusions and final remarks.

2
2.1

Mathematical Formulation and Algorithms
Preliminaries

Along the text, we refer to a complex network as a distance-weighted directed
graph G = {V, E}, which is composed by a set V of |V| nodes and a set E of |E|
edges. To model a city as a complex network, we considered streets as the edges
and their crossings as the nodes, aiming to preserve their element’s geometry.
An edge e ∈ E is an ordered pair hi, ji, in which i ∈ V is named source and
j ∈ V is named target, i 6= j. Each node i ∈ V has two properties {Liat , Lion }

that correspond to their coordinates — Liat is the latitude and Lion the longitude.
Based on such coordinates, we conferred to the edges in E a floating-point weight
that refers to the great-circle (or inline) distance between their source and target.
Our mathematical tool-set tracks inconsistencies identified through distance
functions to detect which element does not follow a pattern. The pattern that
we consider refers to the real-world distance between the nodes of the network,
which in turn can provide insights about the locomotion through the city streets.
In this regard, we begin by tracking a set P ⊂ V of points of interest; the idea,
then, is to determine two sets of nodes that surrounds a point of interest p ∈ P,
which can reveal the city’s inconsistencies through applying algebraic operations.
We introduce these two sets as the perimeter set of p and the network set of p.
2.2

Grouping nodes in the surroundings of points of interest

The first set matches the closest nodes to a point of interest p according to the
great-circle (or inline) distance, which is referred as the perimeter set of p:
VEp = {v ∈ V|dEvp < dEvp̄ , ∀p ∈ P, ∀p̄ ∈ P, p 6= p̄}

(1)

where dEij is the great-circle distance between i and j in the surface of Earth:


j
j
)
dEij = R × arcos sin(Liat )sin(Lat ) + cos(Liat )cos(Lat )cos(4Lij
on

(2)

is the difference between the longitudes
where Liat and Ljat are the latitudes, 4Lij
on
Lion and Ljon , both of nodes i and j. Also, R is the radius of Earth (6,378 km),
and all values are represented in radians. Given a graph G = {V, E} and a set of
points of interest P, a node v ∈ V pertains to the perimeter set of only one p ∈ P.
∴ VEp and VEp̄ — ∀p ∈ P, ∀p̄ ∈ P, p 6= p̄ — are mutually disjoint.
The second set corresponds to the network set of p, which is made of nodes
closest to a point of interest p according to the length of their shortest paths:
VNp = {v ∈ V|dNvp < dNvp̄ , ∀p ∈ P, ∀p̄ ∈ P, p 6= p̄}

(3)

where dNij is the length of the shortest directed path (spathij ) between i and j
— i.e. the sum of weights of all the edges in a minimum-length path, as follows:
minimum length(spathij ) =

X

weight(e)

(4)

e∈spathij

Recall that, the edge weight is given by the straight-line distance between
their nodes using the great-circle distance (see Equation 2). We refer to the
shortest path length as network distance, in the sense that one must necessarily
(in the best case) move across this path to go from the source node to the target
node. Notice that any node v ∈ V is network-closest to one and only one p ∈ P.

∴ VNp and VNp̄ — ∀p ∈ P, ∀p̄ ∈ P, p 6= p̄ — are mutually disjoint.
In cases where the complex network is directed, the network-distance TO a
point of interest is not necessarily the same as the network-distance FROM a
point of interest, which may result in different network sets for the same p. This
detail is addressed in the following section, where we define the network set from
a point of interest to the nodes in V by mean of the reversed network-set of p:
V̄Np = {v ∈ V|dNpv < dNp̄v , ∀p ∈ P, ∀p̄ ∈ P, p 6= p̄}
2.3

(5)

Compartmentalizing inconsistencies for directed networks

Consider different public services of a city as points of interest; such services
may have different ways to assist the population, but all of them must require
locomotion as a condition for assistance. For example, in the case of doctors’
clinics, it is desired that patients get there efficiently. In turn, police stations
require that their police officers efficiently reach the house of the citizens. In
the case of schools, the daily routine demands an efficient back-and-forth transit
to students. Along with other services that can be fitted with this assumption.
Notice that, we are referring to efficient paths as the ones with minimum length.
In the first example, there is an implicit displacement from a node v to a
node p; in the second one, the displacement is from the node p to the node v;
and, in the third case, there is a bi-directional displacement between v and p, in
which v is an ordinary node and p is a specific point-of-interest. Based on the
network direction, those three cases led to the following definitions:
1. Inward Inconsistency: nodes that are inline-closest to a point of interest,
but network-closest (from v to p, as given by Equation 3) to a different one:
ΨIp = VEp − VNp

(6)

2. Outward Inconsistency: the same as the previous category, but in the
opposite direction (from p to v, as given by Equation 5), resulting in the set:
ΨOp = VEp − V̄Np

(7)

3. Absolute Inconsistency: nodes that are, simultaneously, considered to be
inward and outward inconsistencies — i.e. nodes in the sets’ intersection:
ΨAp = ΨIp ∩ ΨOp

(8)

As mentioned, these categories rely on the direction of the network. In cases
where there is no direction, there will be no minimum-length divergence between
paths of a round trip, but yet the inconsistencies can be tracked by calculating
the difference between the perimeter set VEp and the network set VNp of p. To
provide further discussion, hereinafter we are considering just directed networks.

2.4

Tracking distance-based inconsistencies

In this section, we discuss Algorithm 1 that joins the concepts that we previously
introduced. The aim of such algorithm is to track distance-based inconsistencies
in distance-weighted directed networks by using a set P of |P| of points of interest.
Notice that, despite the definition of inconsistency is segmented into three types
(see Section 2.3), the algorithm considers a single inconsistency type at a time.
The algorithm starts by filling a set of empty sets, each one reserved to store
the inconsistencies of a single point of interest (see lines 1 to 3). Subsequently, we
use pE and pN to store, respectively, the inline-closest and network-closest points
of interest to a node v ∈ V (see lines 5 and 6). We used the external functions
inline closest and network closest (see lines 8 and 9) to extract the closest
point of interest to the node v; they implement, respectively, Equation 2 and 4.
Following, we perform a test to check whether a node is an inconsistency or not;
thus, if the inline-closest point pE and the network-closest point pN are not the
same (see line 11) then v is an inconsistency of pE (see line 12). Finally, a set of
the inconsistencies of |P| points of interest is returned as the result (see line 13).

1
2
3
4
5
6
7
8
9
10
11
12
13

Data: G =
 {V, E}, P ⊂ V, and c ∈ {I, O, A} — c is used to indicate the direction
Result: Ψcp , ∀p ∈ P — a set of inconsistencies for all points of interest p ∈ P
Ψc ← ∅
for each p ∈ P do
Ψcp ← ∅ // notice that Ψcp ⊂ Ψc , ∀p ∈ P, therefore |Ψc | = |P|
for each v ∈ V do
pE ← ∅
pN ← ∅
for each p̄ ∈ P do
pE ← inline closest(v, pE , p̄ )
pN ← network closest(v, pN , p̄ , c)
if pE 6=∅ andpN 6= ∅ then
if pE − pN 6= ∅ then
ΨcpE ← ΨcpE ∪ {v} // v should be closer to pE than to pN
return Ψc

Algorithm 1: An algorithm to track distance-based inconsistencies in
cities modeled as networks. We use pE and pN to refer to the closest points
of interest to a node v considering, respectively, the inline and the network
distances; other methods are related to the ones of Section 2.2.
Given a graph G = {V, E}, a set P of |P| points of interest, and an inconsistent
node i; such node is known to be an inconsistency to one and only one p ∈ P.
∴ Ψcp and Ψcp̄ — ∀p ∈ P, ∀p̄ ∈ P, p 6= p̄, c ∈ {I, O, A} — are mutually disjoint.
Consequently, it is possible to derive two other sets from a point of interest p:
(i) the inconsistency set Ψcp ; and (ii) the set of consistent nodes Ψ̄cp = VEp − Ψcp ,
such that Ψ̄cp ∩ Ψcp = ∅. The consistent nodes are fundamental to the process of

suggesting locations to points of interest because they provide a smaller average
distance to the nodes in their perimeter, different than an inconsistent node.
2.5

Reducing distance-based inconsistencies

In this section, we introduce Algorithm 2, which was designed to suggest changes
in the location of points of interest to improve their access through the streets
of a city. The task of finding a perfect location for a point of interest might
demand the test of all possibilities through an exhaustive search. Consequently,
our algorithm has a greedy approach that uses information about centrality
metrics to guide the placement of a point of interest. Centrality is not only an
adequate technique to quantify the importance of a node but also it is capable
to indicate central locations that are equally accessible to all nodes of a network.
Along these lines, we decided to adopt Straightness Centrality [9] as the
centrality metric of Algorithm 2 because it analyzes the nodes of a network by
joining both inline and network distances. It is noteworthy that any distancebased centrality metric could be employed, as well as multiple metrics together;
however, different metrics tend to provide dubious or bad choices for a relocation.
Our algorithm starts by initializing auxiliary variables (see line 1) and by
tracking the inconsistent nodes in the original version of the network (see line 2).
In line 4, it starts looping until all points of interest have been replaced or until
there are no more inconsistencies to be reduced from the original network. After
that, it tries to change one point of interest at a time (see line 7). The candidates
to host a point of interest pertains to the induced subgraph GEp of consistent nodes
(see line 8). By using the induced subgraph the algorithm searches for the node
that has the highest centrality value among all the other ones (see line 9).
The algorithm continues by testing the highest central node as the new
location to the point of interest; such that, it temporally replaces the node (see
line 10) and then it collects information about the inconsistencies of this network
configuration (see line 11). Following, it tests whether the new configuration
causes fewer inconsistencies then the previous one (see line 12) before marking
the node for relocation (see lines 13 to 15). In a greedy fashion, it first selects
the point of interest that by being replaced will lead to the highest elimination
of inconsistencies. After choosing the one to be replaced, we perform integrity
tests, we mark the node as relocated, and then we remove it (see lines 16 to 19).
The algorithm ends when there are no more profitable changes (see line 21).
It is noteworthy to mention that each point of interest can be moved only once;
this is due to the greedy nature of the algorithm. Otherwise, it would run until
there are no more inconsistencies in the network at a prohibitive computational
cost. The output of the algorithm is a set R of new locations (see line 22); each
element r ∈ R is an ordered pair r = oldp , newp that denotes the current
(oldp ) node where a point of interest is and a better node (newp ) for placing it.
Algorithm 2 runs in O(|V||P|3 ) in the average case, where |P| is the number
of points of interest and |V| is the number of nodes, |P|  |V|. Besides that, the
algorithm was designed to be straightly parallelized; and, moreover, in our tests,
it took less than a minute to compute a whole city with 200,000 inhabitants.

Correctness of the algorithm formulation
In this section, we demonstrate that Algorithm 2 is finite and it never increases
the number of inconsistencies of a city, as required by the problem formulation.
Theorem 1. We hypothesize that Algorithm 2 provides a set of central and
consistent nodes that can replace specific points of interest in a city because
replacing them will never increase the total number of inconsistencies.
Proof. Hereinafter, aiming to prove Theorem 1 by reduction to absurdity, we are
supposing that the use of Algorithm 2 can increase the number of inconsistencies.
Bearing in mind that the type of the inconsistency has no effect on such proof, we
will follow by proving the algorithm using Inward Inconsistency (see Section 2.3).
Consider the existence of a city mapped as a complex network G = {V, E} and
a set P of |P| points of interest located in this same city. We start by finding the
perimeter set of p (VEp ) for each p ∈ P, which is given by Equation 1. Subsequently,
we proceed with gathering the network set of p (VNp ) that is defined by Equation 3.
Following, we detect a consistent node p̄ that is the most central by an
arbitrary centrality metric. The most central node is the one that has the highest

1
2
3
4
5
6
7
8
9
10
11
12

Data: G = {V, E}, P ⊂ V, and c ∈ {I, O, A} — c is used to indicate the direction
Result: R — set of suggested positions for points of interest
R ← ∅ P̄ ← ∅ P̃ ← ∅
Ψc ← algorithm 1(G, P, c)
Φc ← Ψc // copy of the original set
P

P|P|
|P|
c
c
while |P| − |P̄| > 0 and
i=1 |Ψi | ≥
i=1 |Φi | do
oldp ← ∅
newp ← ∅
for each p ∈ (P −P̄) do
GEp ← G VEp − Ψcp // induced subgraph of consistent nodes
E
p̄ ← extract central(G
p)


P ← (P − P̄) ∪ P̃ − {p} ∪ {p̄}
Ωc ← algorithm 1 (G, P, c)
P

P|P|
|P|
c
c
if
i=1 |Φi | >
i=1 |Ωi | then
Φc ← Ωc // new lowest number of inconsistencies
oldp ← p
newp ← p̄

13
14
15
16
17
18
19
20
21
22

if oldp 6= ∅ and newp 6= ∅ then
R ← R ∪ {oldp , newp } // oldp was moved to newp
P̄ ← P̄ ∪ {oldp } // old location
P̃ ← P̃ ∪ {newp } // new location
else
break // there are no more enhancements to be made
return R

Algorithm 2: An algorithm that uses the contributions of Algorithm 1 to
reduce distance-based inconsistencies of cities shaped as networks.

centrality when compared to the other nodes, potentially being a better place
for positioning a point of interest in a city. We follow by replacing p by the most
central node p̄ in its perimeter. Then, we calculate the updated perimeter (VEp̄ )
and network (VNp̄ ) sets, both of p̄. Notice that p 6= p̄, thus VEp 6= VEp̄ and VNp 6= VNp̄ .
At this point, there are two pairs of answers, one pair for p and the other one
for p̄, as follows: VEp , VNp and VEp̄ , VNp̄ . The algorithm we proposed will replace
p by p̄ following Equation 9, which corresponds to a clause saying that the sets
computed from p̄ will be used just if they provide fewer inconsistencies than the
original set; otherwise, it will keep the original one without making any changes.
(
VEp − VNp , VEp − VNp ≤ VEp̄ − VNp̄
(9)
ΨIp =
VEp̄ − VNp̄ , otherwise
The algorithm ceases when all the points of interest are changed at least once
or when no change will result in inconsistency elimination (see Section 2.5);
as such, the algorithm is guaranteed to be finite. Therefore, by reduction to
absurdity, it is an absurdum to suppose that the number of inconsistencies
increases due to the use of Algorithm 2 because the algorithm provides a set with
less or equal inconsistencies than the original set — as defined by Equation 10.
∴ ΨIp ≤ VEp − VNp

3

(10)

Results and Discussions

The tool-set we proposed was validated over the Brazilian city of Sao Carlos.
Such city was instantiated as a complex network through a digital map from
OpenStreetMap4 . We considered streets as edges and their crossings as nodes;
this way, we preserved the georeferenced attributes of the city that are necessary
to the distance computation of our tool-set. The resulting network is planar and
it can be represented in two dimensions, in which edges intersect only at nodes.
3.1

Assessing inconsistency recovery

In this section, we analyze the inconsistent nodes found in the city of Sao Carlos
regarding the location of hospitals, police stations, and public schools, which are
our points of interest; such public services are known to be affected respectively
by inward, outward, and absolute inconsistencies as described in Section 2.3. It
is noteworthy that each set of points of interest are independent, as such, the
inconsistencies of one set of points have no relationship with the ones of others.
The inconsistent nodes we tracked are in Table 1, which suggest that their
occurrence is connected to the number of points of interest. In fact, they
appear whenever different perimeters meet; as a consequence, there is no way to
eradicate them without altering the network topology by changing the streets’
direction or creating new streets. In addition, more points of interest mean more
4

www.openstreetmap.org

nth POI

Original City
Hospitals Police Stations

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
Total

#
013
002
012
019
030
049
145
039
012
043
072
095
028
—
—
—
559

%
02.3%
00.3%
02.1%
03.4%
05.3%
08.7%
25.9%
06.9%
02.1%
07.6%
12.8%
16.9%
05.0%
—
—
—
100%

#
032
004
086
029
191
—
—
—
—
—
—
—
—
—
—
—
342

%
09.3%
01.1%
25.1%
08.4%
55.8%
—
—
—
—
—
—
—
—
—
—
—
100%

Enhanced City
Schools
#
015
077
043
071
114
003
008
015
078
051
038
015
056
008
060
011
663

%
02.2%
11.6%
06.4%
10.7%
17.1%
00.4%
01.2%
02.2%
11.7%
07.6%
05.7%
02.2%
08.4%
01.2%
09.0%
01.6%
100%

Hospitals Police Stations
#
14
02
18
04
87
51
26
22
31
63
45
17
19
—
—
—
399

%
03.5%
00.5%
04.5%
01.0%
21.8%
12.7%
06.5%
05.5%
07.7%
15.7%
11.2%
04.2%
04.7%
—
—
—
100%

#
30
48
96
32
13
—
—
—
—
—
—
—
—
—
—
—
219

%
13.7%
21.9%
43.8%
14.6%
05.9%
—
—
—
—
—
—
—
—
—
—
—
100%

Schools
#
19
13
37
58
57
01
01
18
77
48
41
11
10
16
51
26
484

nth POI

boundaries, what tends to increase their number. Hence, the challenge is to find
locations to points of interest that reduce, rather than eradicate, inconsistencies.
We used Algorithm 2 so to reduce the inconsistencies from Sao Carlos (see
Table 1). The algorithm suggested relocating 6 hospitals, 2 police stations, and
9 public schools; such configuration, was able to reduce 160 inconsistencies from
the hospitals (from 559 to 399), 123 inconsistencies from the police stations (from
342 to 219), and 179 inconsistencies from the public schools (from 663 to 484).
Notice that the inconsistencies of some points of interest raised in number from
the original to the enhanced city, which is a setback of our approach. However,
as we have already proved, the total number of inconsistencies is always smaller.

%
03.9% 01
02.6% 02
07.6% 03
11.9% 04
11.7% 05
00.2% 06
00.2% 07
03.7% 08
15.9% 09
09.9% 10
08.4% 11
02.2% 12
02.0% 13
03.3% 14
10.5% 15
05.3% 16
100% Total

Table 1: Analysis of the inconsistencies of the city of Sao Carlos, in which we
considered police stations, hospitals, and public schools as points of interest; we
use # to refer to the total number of inconsistencies and % to their percentage.

3.2

Supporting the designing of urban structures

Our tool-set is not only to be used in the automatic recovery of inconsistencies,
but also to assist human-made urban-planning decisions. This is the case, for
instance, when a specialist designs a city by having knowledge of the citizens’
needs. In this case, Algorithms 1 and 2 can aid the process by analyzing and
recommending distance-efficiently locations that are feasible to points of interest.
This section introduces two hypothetical case studies that depict our toolset in practice. Both of them were conducted considering a subset of hospitals
and public schools of the city of Sao Carlos (see Section 3.1). Nonetheless, our
tool-set is extendable to any point of interest since it is equivalent to all of them.

Both case studies follow as in Figure 1, in which we start by finding a point
of interest, next we try to solve the problem by ourselves, and then we use the
algorithms to improve our results; all steps are guided under the light of the
nodes’ straightness centrality . Furthermore, all case studies are represented
by the induced subgraph of the point of interest being analyzed and, although
we have illustrated the inconsistencies in Figure 1, in the case studies they are
not visible because they do not provide visual information to the other images.
Nodes Legend
Highest Centrality

Better Position
Lowest Centrality
Inconsistency

orit

Alg
s
hm

Point of Interest
Fig. 1: Illustration of the process of designing urban structures under the light
of centrality metrics. This process starts by identifying nodes that are of interest,
then it follows by tracking their inconsistencies, and it ends by suggesting new
locations — that reduce the number of inconsistencies — to place these nodes.

Case Study 1: Creating a new hospital to reduce demand
From the set of hospitals of the city of Sao Carlos, we identified one that, when
compared to another hospital in the city, has excessive nodes in its perimeter
(see Figure 2a). There is no specific explanation of the hospital’s location and,
for instance, we can think that the city may have grown after the hospital has
been built or the planners did not take the surroundings of the hospital into
account. One thing is for sure, an extensive area with an ill-positioned point of
interest will deprive the street access of the nodes; in this case, when points of
interest are healthcare facilities, time-critical activities, as the transportation of

Perimeter 1

Perimeter 1

Possibility 2

Possibility 1

Hospital
Perimeter 2

(a) Original City

Hospital
Perimeter 2

(b) Enhanced City

Fig. 2: Illustration of the assisted urban planning task from the first case study,
in which the point of interest is a hospital and the color of the nodes denotes their
centrality — the darker, the higher. Figure 2a shows a hospital’s perimeter that is
too large causing lack of access. We placed a new hospital in an eye-based central
location in that same area to solve this issue. Afterwards, we used the algorithm
to reduce inconsistencies, which suggested relocating the new hospital to a more
central location that reduces the hospital’s inconsistencies; as in Figure 2b.
patients in a critical state, can be jeopardized by lack of street access. Hence,
the problem becomes where to build a hospital and how to avoid inconsistencies.
First, we tried to solve the problem manually by an eye-based analysis of
a location that could provide equal nodes to the perimeters of both hospitals.
Figure 2a shows a possible place to the new hospital as well as the resulting
perimeter of both of them, which are defined by a line that cuts the image in
half. After that, we inserted the proposed location in the set of hospitals and
we used Algorithm 1 to track the inconsistencies of the resulting configuration.
Such configuration lead us to 615 inconsistencies, which is a bigger value than the
original city. Thus, we succeeded in building a hospital that splits the perimeter
into two, but we failed in providing efficient access to both old and new hospital.
In a second approach, we analyzed the nodes’ centrality together with a
supporting visualization. We colored the nodes by their centrality, what allowed
us to notice that the selected location for the new hospital is a node with
low centrality. Then, we used Algorithm 2 to suggest a better place for the
new hospital while keeping the location of the old one. Doing so, the city
inconsistencies were reduced from 615 to 352 (see Figure 2b), which positively
reflected in the mobility of this area by distributing the demand between both
hospitals. Thus, creating a new hospital in a specific location was able to reduce
almost half of the inconsistencies of the city without relocating the existing ones.

Case Study 2: Merging schools to centralize public resources
In a similar fashion, we identified two public schools that are adjacent and
support a short set of nodes. In this case, the proximity of the schools (see
Figure 3a) is a problem since none of them is used up to its capacity implying a
waste of public resources. In a first approach, by using Algorithm 2 to relocate
them, the number of inconsistencies was reduced from 663 to 635.

(a) Original City

(b) Enhanced City

Fig. 3: Illustration of the assisted urban planning task from the second case
study, in which the points of interest are public schools and the color of the
nodes denotes their centrality — the darker, the higher. In this case study, we
treated a problem related to the waste of resources that was caused by having two
schools near each other; Figure 3a shows the problematic area, which is small,
increasing the drawbacks related to access. By replacing both schools with a
single one we achieved a better coverage of nodes, as depicted in Figure 3b.
Considering the size of the perimeter of both schools, we decided to remove
one school to improve the utility of the one that remained. By centralizing the
schools in a single node, we can reduce inconsistencies because there will be fewer
perimeters bordering each other; hence, the inconsistencies, located whenever
two of them meet, will be naturally decreased. To further enhance this process,
we used the color-coded centrality metric to choose a candidate to be the new
sole school. Afterward, we used Algorithm 2 to provide a better location (see
Figure 3b), which reduced the total number of inconsistencies from 635 to 445.
3.3

Discussions on results generalization

For a concise results presentation, we have assumed: (i) that any displacement
is through cities’ streets; and, (ii) a city with a uniform population distribution.
However, our tool-set holds for scenarios where these assumptions are not true.
We can use weights in accordance with the type of the displacement rather
than using streets distance. This is because our tool-set uses a general concept

of weight and when providing additional information such weight can assume
any quantitative value — i.e. travel time, edge capacity, route cost, and so on.
About the population distribution, it is possible, for instance, to use a normal
distribution peaked at the center of the city, multimodal distributions, or census
data. This information can aid in the analysis of urban agglomerations if it is
used to assign values to sets of nodes corresponding to the population density
of the area that they belong to. Nevertheless, the set of inconsistencies would
depend on the analysis of a specialist rather than being a self-explanatory result.
Also, despite being central to our problem formulation, the viability of
redesigning a city is not suited for most cases. Furthermore, changing the
topology of the network will alter the centrality of its elements, which will modify
regions that attract vehicles and people. Our tool-set is not only to be used in
redesigning a city but also on the initial design when all possibilities are open.
Finally, our proposal has open problems that support further studies: (1) the
tool-set to track inconsistencies is categorical, then further algebra can aid in
identifying the severity of a network inconsistency in a continuous, rather than
binary, manner; (2) for simplicity’s sake, we assumed the origin and destination
of all paths as nodes of the network; such nodes are street intersections, which
might not be real-world points of interest, requiring the addition of new nodes.

4

Conclusion

This paper was instantiated as a set of mathematical formalisms and algorithms
to track and reduce distance-based inconsistencies improving access to/from
points of interest in a city. Beyond the mathematical formulation, we provided a
proof of concept and case studies, all of which indicate that our tool-set is able to
suggest better placements for points of interest at the same time that it improves
the access to the majority of the nodes of a city by reducing its inconsistencies.
More specifically, our contributions are in the definition of a concept based
on intrinsic problems to urban structures that are caused by the misallocation of
points of interest in cities; also, in two algorithms that were devised to track and
reduce inconsistent nodes in complex networks; and, finally, in a case study, in
which we show how our tool-set and algorithms can aid planners and designers.
In summary, our methods were proved empirically and formally, granting
potential for prompt contribution and for opening new research questions.
In addition, as a future work, we shall embrace link prediction methods for
suggesting relocations in the network topology, i.e. proposing variations in the
flow’s direction, in the task of looking for a better topological setting for a city.

Acknowledgement
We would like to thank the Brazilian agencies CNPq (167967/2017-7), FAPESP
(2016/17078-0 and 2017/08376-0) and CAPES that fully supported this research.

Bibliography

[1] Boccaletti, S; Latora, V; Moreno, Y; Chavez, M; Hwang, D: Complex networks:
Structure and dynamics. Physics Reports 424(4-5) (feb 2006) 175–308
[2] Porta, S; Latora, V; Wang, F; Strano, E; Cardillo, A; Scellato, S; Iacoviello, V;
Messora, R: Street Centrality and Densities of Retail and Services in Bologna,
Italy. Environment and Planning B: Planning and Design 36(3) (2009) 450–465
[3] Masucci, A P; Stanilov, K; Batty, M: Limited Urban Growth: London’s Street
Network Dynamics since the 18th Century. PLoS ONE 8(8) (aug 2013)
[4] Kaczynski, A T; Koohsari, M J; Stanis, S A W; Bergstrom, R; Sugiyama, T:
Association of Street Connectivity and Road Traffic Speed With Park Usage and
Park-Based Physical Activity. Am J of Health Promot 28(3) (jan 2014) 197–203
[5] Sopan, A; Rey, P J; Shneiderman, B: The Dynamics of Web-Based Community
Safety Groups: Lessons Learned from the Nation of Neighbors. IEEE Signal
Processing Magazine 30(6) (nov 2013) 157–162
[6] Corcoran, P; Jilani, M; Mooney, P; Bertolotto, M: Inferring semantics from
geometry. In: Proceedings of the 23rd SIGSPATIAL International Conference on
Advances in Geographic Information Systems - GIS’15, ACM (2015)
[7] Barthélemy, M; Flammini, A: Modeling Urban Street Patterns. Physical Review
Letters 100(13) (apr 2008)
[8] Zhong, C; Arisona, S M; Huang, X; Batty, M; Schmitt, G: Detecting the dynamics
of urban structure through spatial network analysis. International Journal of
Geographical Information Science 28(11) (may 2014) 2178–2199
[9] Crucitti, P; Latora, V; Porta, S: Centrality measures in spatial networks of urban
streets. Phys Rev E 73(3) (mar 2006)
[10] Costa, L F; Travençolo, B A N; Viana, M P; Strano, E: On the efficiency of
transportation systems in large cities. EPL (Europhysics Letters) 91(1) (jul 2010)
[11] Strano, E; Nicosia, V; Latora, V; Porta, S; Barthélemy, M: Elementary processes
governing the evolution of road networks. Scientific Reports 2 (mar 2012)
[12] Spadon, G; Gimenes, G; Rodrigues-Jr, J F: Identifying Urban Inconsistencies via
Street Networks. Volume 108; Elsevier BV (2017) 18 – 27 International Conference
on Computational Science, ICCS 2017, 12-14 June 2017, Zurich, Switzerland.
[13] Li, X; Parrott, L: An improved genetic algorithm for spatial optimization of multiobjective and multi-site land use allocation. Comput, Environment and Urban
Systems 59 (2016) 184–194
[14] Viana, M P; Costa, L F: Fast long-range connections in transportation networks.
Physics Letters A 375(15) (apr 2011) 1626–1629
[15] Travençolo, B; Costa, L F: Accessibility in complex networks. Physics Letters,
Section A: General, Atomic and Solid State Physics 373(1) (dec 2008) 89–95
[16] Crucitti, P; Latora, V; Porta, S: Centrality in networks of urban streets. Chaos:
An Interdisciplinary Journal of Nonlinear Science 16(1) (mar 2006) 015113
[17] Porta, S; Crucitti, P; Latora, V: The network analysis of urban streets: A dual
approach. Physica A 369(2) (sep 2006) 853–866
[18] Cardillo, A; Scellato, S; Latora, V; Porta, S: Structural properties of planar graphs
of urban street patterns. Phys Rev E 73(6) (jun 2006)

