The basic purpose of a map is to trace shortest paths between two locations in a city. However, this is not always what a user needs. Consider a tourist in an unknown city, he/she might want to trace routes to visit multiple landmarks while passing through the main streets of the city, possibly more than once through the same street. Such functionality is not yet available in online map services, which are prone to provide shortest paths that connect all landmarks. Rather, is of common interest a tour that puts together the most central streets (topologically speaking), minimizes the trajectory and, at the same time, passes through such landmarks. To cope with this problem, it is possible to investigate techniques of Center-Piece Subgraph, Absorbing Random Walk Centrality and Spanning Edge-Betweenness; such techniques can be used to nd induced subgraphs that optimize centrality measures for a set of referential nodes or edges, i.e. landmarks or streets. The results shall be in the form of optimized algorithms, and how to integrate them into online systems. Studies in this line can succeed if they can guarantee timely scalability at the same time that they provide algorithms that produce tours (1) considering all the known destinations; (2) including the main streets of a city; and, (3) ensuring the shortest routes.
Digital maps are becoming available to everyone, anywhere, through computers, smartphones, car assistants, and electronic devices in general. The most common use of such maps is to trace routes, or shortest paths, among di erent locations. However, this basic use is not always what one needs. In the case of a tourist visiting an unknown city, for instance, the user is not looking for the fastest and/or shortest path. Rather, he/she is looking for a tour that visits multiple landmarks (i.e. points of interest) while passing, possibly more than once, through the main streets of the city. That is, the user not only has several destinations, he/she desires a route that favors hotspots of the city in what is usually called city-tour. For instance, imagine a tourist is on the east side of the Central Park in New York and wants to go all the way down to the World Trade Center; the fastest and shortest path is to go through the monotonous 7th avenue. For a tourist, di erently, the best pick might be to go through Broadway, despite its tra c and higher distance. The idea then is to nd the tour that puts together City-Tour the most central streets (topologically speaking), minimizes the trajectory and, at the same time, passes through points of interest. Di erently, current systems are more likely to provide the user with shortest paths that connect all the points of interest. In other cases, the user does not even have destinations to visit; he/she wants to cruise through the city, discovering it iteratively. Such functionalities are not yet available in online map services and can be explored through complex-network tools by using a methodological process similar to the one presented in Figure 1. 2
The goal is to use graph-processing techniques to compute touristic routes with,
or without, multiple destinations satisfying performance constraints. Given a
city, or a region of a city, such routes might come as the answer to two queries:
(1) to compute a multiple-destinations tour; or, (2) to compute a tour, even
if the set of destinations is empty. The second query might sound odd, but it
is not an unusual case, especially for explorers in unknown cities. Notice that,
such queries depend on the investigation of techniques based on random-walk
with restart [
Besides the aforementioned work, others touched the issue of processing digital
maps. Scellato et al. [
Nowadays, digital maps can be extracted from many di erent sources, but
some of them are not freely available. OpenStreetMap1 is a collaborative
street-mapping community and an open-source option for digital maps. Over
OpenStreetMap, it is possible to investigate techniques related to the questions
placed in Section 2. Such research questions can be explored by means of three
techniques, as follows:
Center-Piece Subgraph (CEPS). The Center-Piece Subgraph technique
summarizes a graph, producing an induced topology that connects a subset of
referential nodes provided as input. It follows by using random-walks with restart
and cost functions to measure the adequacy of the edges that will be part of the
resulting topology [
g(CP ) =
X j 2 nodes(CP ) r(Q; j) (1)
The goodness criterion minimizes the sum of weights to connect all the edges
in the subset while inducing a subgraph; however, it does not consider edge
properties, leading to a subgraph with semantics related to a route in a map.
The metric was not designed to provide a minimum set of edges, as necessary in
multiple-destination routes, but only with as many edges as desired by the user.
Example. Let us consider an unknown city represented as a graph G(V; E)
which has a couple of touristic attractions T and let T 0 be the subset of those
that he/she wants to visit or, alternatively, avoid. The idea then is to extract a
subgraph G0 that confers the user a reduced network in which he/she can travel
1 www.openstreetmap.org
back and forth to visit the desired destinations. The output of CEPS, in this
particular case, shall be a subgraph indicating the easiest and most interesting
way to travel from a source place ti to a target one ti+1, where f(ti; ti+1) 2 T 0g.
Absorbing Random Walk Centrality (ARwC). The Absorbing Random
Walk Centrality technique is capable of evaluating the centrality of a subgraph
considering a set of query nodes Q [
Spanning Edge-Betweenness (SEB). A Spanning Tree (ST) is a graph structure that contains all the nodes connected by a subset of non-cyclic edges. It can be produced with weighted or non-weighted edges. In the context of a map, an accurately computed ST (not necessarily the minimum) generates a Backbone representation of a city, which conforms to the problem of computing a tour without a set of destinations. To this end, SEB is a centrality metric computed by considering all the STs of a graph; it works by quantifying the number of times that each edge pertains to an ST. The result of this metric is a hierarchical formation of streets according to their importance.
SEB was rstly de ned over undirected and weighted graphs to improve the
analysis of phylogenetic trees [
G(e) =
G(e) (2) Example. Suppose that it is desired to detect the most common and interesting route that connects the nodes of an unknown city. That is, one wants not only the streets with the minimum length, but also wants those that, given the network topology, render better routes more frequently. This process can be achieved by using SEB whenever it is possible to infer weights to the set of network edges. 5
The results shall be in the form of optimized algorithms, and how to integrate them into online systems, including how to extract and prepare the network (maps are not necessarily represented as graphs), how to provide input to these algorithms, and how to interpret the outputs. The results shall be validated through extensive testing over a signi cant number of representative cities. Studies in this line can succeed if they can process queries over a map within seconds, and if the algorithms produce tours that (1) consider all the destinations (if known); (2) include the main streets of a city (higher centralities); and, (3) minimize the length of the paths (good routes). It is possible to verify those conditions in large scale by using brute-force algorithms or multi-objective optimization techniques; and, in small scales, by considering case studies of known cities and their tours. Research following these lines shall pave the way for future map processing, turning tours into a novel concept on electronic-trajectory computing. The results have the potential to be reported in international conferences and journals of Data Mining, Transportation Systems, and Physics. 6
The possibilities of research and investigation are not limited to the calculation of city-tours. It is possible, for instance, to analyze di erent sets of cities by extracting feature vectors that describe the complex-networks of their tours. This is because feature vectors can describe cities by detailing their topology and structural peculiarities, which would enable further analysis based on clustering detection, similarity search, multidimensional projection, and fractal analysis. All of which have the potential to enhance the understanding both about cities and tourist behaviors in the face of di erent types of landmarks that can be found in a given city. More speci cally, by investigating feature vectors through these tools, it is possible: (i) to analyze cities according to their similarities and di erences; (ii) to determine characteristics shared between cities or groups of cities; and, (iii) to disclose routing problems that are exclusive to peculiar cities. In fact, all these activities help in the designing of the urban space, they also help in its improvement and comprehension because similar cities might share the valuable characteristics; meanwhile, exceptional cities might indicate routing problems that can be further studied through a di erent set of tools.
We would like to thank the Brazilian agencies CNPq, FAPESP, and CAPES that fully supported this research.