SpatialMeasures v.0.2

Continuous average Straightness for spatial graphs

• Copyright 2016-18 Vincent Labatut

SpatialMeasures is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation. For source availability and license information see licence.txt

• Lab site: http://lia.univ-avignon.fr/
• GitHub repo: https://github.com/CompNet/SpatialMeasures
• Contact: Vincent Labatut vincent.labatut@univ-avignon.fr

---

Description

This set of R scripts was designed to process several variants of the Straightness (aka. Directness and probably other names): the ratio of the Euclidean to the graph distance. It is a measure designed to study spatial graphs, i.e. graphs embedded in an Euclidean space (nodes have spatial positions, links have spatial length, etc.).

First, this toolbox can process the Straightness using the traditional approach, i.e. considering only paths connecting two nodes. It can process the Straightness between two specific nodes, or the Straightness averaged over certain pairs of nodes in the graph (including all pairs).

Second, this toolbox can also compute the average Straightness through a continuous approach (by opposition to the discrete traditional approach), and incidentally this is the point of the article [L'18]. The Straightness is generalized to deal with point-to-point paths, i.e. paths connecting a location on a link to another such position (by opposition to nodes, which are necessarily located on the ends of links). Based on this, we can average the Straightness by integration over the link. This allows deriving the following continuous average variants:

• Average Straightness between a point and an link (or rather: all the points on this link);
• Average Straightness between a point and the rest of the graph (or rather: all the points constituting this graph);
• Average Straightness between two links (or rather: all pairs of points located on these links, each point being on a different one);
• Average Straightness between a link and the rest of the graph (or rather: all the points located on the link on one side, and all the points constituting the graph on the other side);
• Average Straightness over the graph (or rather: between all the pairs of points constituting the graph).

Besides the functions used to process the average measures themselves, the scripts also allow to replicate the different experiments conducted in the article [L'18].

If you use this software, please cite reference [L'18]:

@Article{Labatut2016,
  author     = {Labatut, Vincent},
  title      = {Continuous Average Straightness in Spatial Graphs},
  journal    = {Journal of Complex Networks},
  year       = {2018},
  volume     = {6},
  number     = {2},
  pages      = {269-296},
  doi        = {10.1093/comnet/cnx033},
}

Data

Most of the data is generated randomly and recorded in the data folder (see the Organization section for more details).

We also experiment on a few real-world networks. These are all road networks retrieved from OpenStreetMap, using the script src/misc/extraction.R. These networks are available on Zenodo, as explained in the Installation section.

Organization

Here are the folders composing the project:

• Folder src: contains the source code (R scripts).
  • Folder evaluation: scripts used to evaluate the time and memory usage (see [L'18]).
  • Folder figures: scripts used to produce some of the figures presented in the article, and process certain of their properties.
  • Folder misc: scripts used for extracting, generating, modifying and plotting the graphs.
  • Folder straightness: scripts used to process the discrete and continuous average variants of the average Straightness.
  • Script main.R: shows an example of how to process the Straightness on your own graphs through this toolkit.
• Folder data: contains the files used and generated by our scripts.
  • Folder figures: files produced by the scripts in src/figures, corresponding to graph representations appearing in the paper.
  • Folder eval: files related to the evaluation of the time processing and memory usage needed when processing the average Straightness.
  • Folder urban: plots and data generated when processing the Straightness of real-world road networks.

Installation

1. Install the R language
2. Install the following R packages:
   • geometry: required (tested with version 0.3.6).
   • igraph: required (tested with version 1.0.1).
   • plotrix: required (tested with version 3.5-11).
   • osmar: only if you want to extract new road networks via the src/misc/extraction.R script (tested with version 1.1-7)
   • splancs: only if you want to generate spiderweb-like networks via the src/figures/regular.R script (tested with version 2.01-39)
3. Download this project from GitHub and unzip the archive.
4. If you want to apply the scripts on the real-world road networks from the article [L'18], download the graph archive from Zenodo and unzip it so that it overwrites the data/urban folder.

Use

In order to replicate the experiments from the article, perform the following operations:

1. Open the R console.
2. Set the current projetct directory as the working directory, using setwd("my/path/to/the/project/SpatialMeasures").
3. Run one of the following scripts:
   • src/figures/regular.R, src/figures/random.R or src/figures/urban.R to generate the graph figures from the article [L'18].
   • src/evaluation/time.R, src/evaluation/memory.R or src/evaluation/urban.R to produce the plots/tables related to performance.
   • src/evaluation/urban.R

If you just want to apply the measures to your own graph, then you need to use the following functions, as shown in src/main.R:

• mean.straightness.nodes.link(g, u, e): average Straightness between node u and link e.
• mean.straightness.nodes.graph(g, u): average Straightness between node u and the rest of graph g.
• mean.straightness.link.link(g, e1, e2): average Straightness between links e1 and e2.
• mean.straightness.links.graph(g, e): average Straightness between link e and the rest of graph g.
• mean.straightness.graph(g): average Straightness between each pair of points constituting graph g.

Note the specified graph must be an igraph object, and its nodes must be described by their position in a 2D space. For this purpose, the graph must contain two nodal attributes called x and y. See the igraph documentation to know how to define such attributes.

Also, note you only need the R script src/straightness/continuous.R to process the variants of the continuous average straightness on your graphs. The rest of the scripts is just there for plotting, testing, evaluating, comparing, etc. You need to uncomment the function get.dist in continuous.R, if you want to use it in a standalone way, though.

Extension

You may want to apply the approach described in our paper to average other spatial measures. You would need either to process analytically the integral on the considered measure, as described for the first integration of the Straightness in the article. Alternatively, you may use numerical integration, as described for the second integration of the Straightness in the article. In any case, you can use the functional decomposition from continuous.R, but you will have to adapt most of it to the processing of your specific measure (i.e. our source code is not generic).

Dependencies

• igraph package: used to build and handle graphs.
• geometry package: used to triangulate and generate planar random graphs.
• plotrix package: used to generate certain plots.
• osmar package: used to extract real-world road networks.
• splancs: used when generating spiderweb-like networks.

To-do List

• Check if tolerance is now actually needed (after dealing with the specific cases).

References

• [L'18] V. Labatut. Continuous Average Straightness in Spatial Graphs, Journal of Complex Networks, 6(2):269-296, 2018. doi: 10.1093/comnet/cnx033 - ⟨hal-01571212⟩