networks

Compute network centralities. There are three network centrality methods available depending on whether you’re using a node-based or segment-based approach, with the former available in both shortest and simplest (angular) variants.

These methods wrap the underlying rust optimised functions for computing centralities. Multiple classes of measures and distances are computed simultaneously to reduce the amount of time required for multi-variable and multi-scalar strategies.

See the accompanying paper on arXiv for additional information about methods for computing centrality measures.

The reasons for picking one approach over another are varied:

  • Node based centralities compute the measures relative to each reachable node within the threshold distances. For this reason, they can be susceptible to distortions caused by messy graph topologies such redundant and varied concentrations of degree=2 nodes (e.g. to describe roadway geometry) or needlessly complex representations of street intersections. In these cases, the network should first be cleaned using methods such as those available in the graph module (see the graph cleaning guide for examples). If a network topology has varied intensities of nodes but the street segments are less spurious, then segmentised methods can be preferable because they are based on segment distances: segment aggregations remain the same regardless of the number of intervening nodes, however, are not immune from situations such as needlessly complex representations of roadway intersections or a proliferation of walking paths in greenspaces;
  • Node-based harmonic centrality can be problematic on graphs where nodes are erroneously placed too close together or where impedances otherwise approach zero, as may be the case for simplest-path measures or small distance thesholds. This happens because the outcome of the division step can balloon towards ∞\infty once impedances decrease below 1.
  • Note that cityseer’s implementation of simplest (angular) measures work on both primal and dual graphs (node only).
  • Measures should only be directly compared on the same topology because different topologies can otherwise affect the expression of a measure. Accordingly, measures computed on dual graphs cannot be compared to measures computed on primal graphs because this does not account for the impact of differing topologies. Dual graph representations can have substantially greater numbers of nodes and edges for the same underlying street network; for example, a four-way intersection consisting of one node with four edges translates to four nodes and six edges on the dual. This effect is amplified for denser regions of the network.
  • Segmentised versions of centrality measures should not be computed on dual graph topologies because street segment lengths would be duplicated for each permutation of dual edge spanning street intersections. By way of example, the contribution of a single edge segment at a four-way intersection would be duplicated three times.
  • The usual formulations of closeness or normalised closeness are discouraged because these do not behave suitably for localised graphs. Harmonic closeness or Hillier normalisation (which resembles a simplified form of Improved Closeness Centrality proposed by Wasserman and Faust) should be used instead.
  • Network decomposition can be a useful strategy when working at small distance thresholds, and confers advantages such as more regularly spaced snapshots and fewer artefacts at small distance thresholds where street edges intersect distance thresholds. However, the regular spacing of the decomposed segments will introduce spikes in the distributions of node-based centrality measures when working at very small distance thresholds. Segmentised versions may therefore be preferable when working at small thresholds on decomposed networks.

node_centrality_shortest

node_centrality_shortest
(
network_structure : NetworkStructure
nodes_gdf : geopandas.geodataframe.GeoDataFrame
distances : list[int] | None = None
betas : list[float] | None = None
compute_closeness : bool | None = True
compute_betweenness : bool | None = True
min_threshold_wt : float = 0.01831563888873418
jitter_scale : float = 0.0
)->[ GeoDataFrame ]

Compute node-based network centrality using the shortest path heuristic.

Node weights are taken into account when computing centralities. These would typically be initialised at 1 unless manually specified.

Parameters

network_structure
None

A rustalgos.NetworkStructure. Best generated with the io.network_structure_from_nx method.

nodes_gdf
None

A GeoDataFrame representing nodes. Best generated with the io.network_structure_from_nx method. The outputs of calculations will be written to this GeoDataFrame, which is then returned from the method.

distances
list[int]

Distances corresponding to the local dmaxd_{max} thresholds to be used for calculations. The β\beta parameters (for distance-weighted metrics) will be determined implicitly. If the distances parameter is not provided, then the beta parameter must be provided instead.

betas
list[float]

A β\beta, or array of β\beta to be used for the exponential decay function for weighted metrics. The distance parameters for unweighted metrics will be determined implicitly. If the betas parameter is not provided, then the distance parameter must be provided instead.

compute_closeness
bool

Compute closeness centralities. True by default.

compute_betweenness
bool

Compute betweenness centralities. True by default.

min_threshold_wt
float

The default min_threshold_wt parameter can be overridden to generate custom mappings between the distance and beta parameters. See rustalgos.distances_from_beta for more information.

jitter_scale
float

The scale of random jitter to add to shortest path calculations, useful for situations with highly rectilinear grids or for smoothing metrics on messy network representations. A random sample is drawn from a range of zero to one and is then multiplied by the specified jitter_scale. This random value is added to the shortest path calculations to provide random variation to the paths traced through the network. When working with shortest paths in metres, the random value represents distance in metres. When using a simplest path heuristic, the jitter will represent angular change in degrees.

Returns

nodes_gdf
GeoDataFrame

The input node_gdf parameter is returned with additional columns populated with the calcualted metrics.

Notes

The following keys use the shortest-path heuristic:

keyformulanotes
density∑j≠in1\sum_{j\neq{i}}^{n}1A summation of nodes.
harmonic∑j≠in1d(i,j)\sum_{j\neq{i}}^{n}\frac{1}{d_{(i,j)}}Harmonic closeness is an appropriate form of closeness centrality for localised implementations constrained by the threshold dmaxd_{max}.
hillier(n−1)2∑j≠ind(i,j)\frac{(n-1)^2}{\sum_{j \neq i}^{n} d_{(i,j)}}The square of node density divided by farness. This is also a simplified form of Improved Closeness Centrality.
beta∑j≠inexp⁡(−β⋅d[i,j])\sum_{j\neq{i}}^{n} \\ \exp(-\beta\cdot d[i,j])Also known as the gravity index. This is a spatial impedance metric differentiated from other closeness centralities by the use of an explicit β\beta parameter, which can be used to model the decay in walking tolerance as distances increase.
cycles∑j≠ij=cyclen1\sum_{j\neq{i}j=cycle}^{n}1A summation of network cycles.
farness∑j≠ind(i,j)\sum_{j\neq{i}}^{n}d_{(i,j)}A summation of distances in metres.
betweenness∑j≠in∑k≠j≠in1\sum_{j\neq{i}}^{n}\sum_{k\neq{j}\neq{i}}^{n}1Betweenness centrality summing all shortest-paths traversing each node ii.
betweenness_beta∑j≠in∑k≠j≠inexp⁡(−β⋅d[j,k])\sum_{j\neq{i}}^{n}\sum_{k\neq{j}\neq{i}}^{n} \\ \exp(-\beta\cdot d[j,k])Applies a spatial impedance decay function to betweenness centrality. dd represents the full distance from any jj to kk node pair passing through node ii.

node_centrality_simplest

node_centrality_simplest
(
network_structure : NetworkStructure
nodes_gdf : geopandas.geodataframe.GeoDataFrame
distances : list[int] | None = None
betas : list[float] | None = None
compute_closeness : bool | None = True
compute_betweenness : bool | None = True
min_threshold_wt : float = 0.01831563888873418
angular_scaling_unit : float = 90
farness_scaling_offset : float = 1
jitter_scale : float = 0.0
)->[ GeoDataFrame ]

Compute node-based network centrality using the simplest path (angular) heuristic.

Node weights are taken into account when computing centralities. These would typically be initialised at 1 unless manually specified.

Parameters

network_structure
None

A rustalgos.NetworkStructure. Best generated with the io.network_structure_from_nx method.

nodes_gdf
None

A GeoDataFrame representing nodes. Best generated with the io.network_structure_from_nx method. The outputs of calculations will be written to this GeoDataFrame, which is then returned from the method.

distances
list[int]

Distances corresponding to the local dmaxd_{max} thresholds to be used for calculations. The β\beta parameters (for distance-weighted metrics) will be determined implicitly. If the distances parameter is not provided, then the beta parameter must be provided instead.

betas
list[float]

A β\beta, or array of β\beta to be used for the exponential decay function for weighted metrics. The distance parameters for unweighted metrics will be determined implicitly. If the betas parameter is not provided, then the distance parameter must be provided instead.

compute_closeness
bool

Compute closeness centralities. True by default.

compute_betweenness
bool

Compute betweenness centralities. True by default.

min_threshold_wt
float

The default min_threshold_wt parameter can be overridden to generate custom mappings between the distance and beta parameters. See rustalgos.distances_from_beta for more information.

angular_scaling_unit
float

The number by which to divide angular distances for scaling. 90 by default. For example, if the cumulative angular distance for a given route is 180 then this will be scaled per 180 / 90 = 2.

farness_scaling_offset
float

A number by which to offset the scaled angular distance for computing farness. 1 by default. For example, if the scaled angular distance is 2, then an offset of 1 will be applied as 1 + 2 = 3. This offset is only applied when calculating farness. Harmonic closeness always uses an offset of 1 to prevent division by zero.

jitter_scale
float

The scale of random jitter to add to shortest path calculations, useful for situations with highly rectilinear grids or for smoothing metrics on messy network representations. A random sample is drawn from a range of zero to one and is then multiplied by the specified jitter_scale. This random value is added to the shortest path calculations to provide random variation to the paths traced through the network. When working with shortest paths in metres, the random value represents distance in metres. When using a simplest path heuristic, the jitter will represent angular change in degrees.

Returns

nodes_gdf
GeoDataFrame

The input node_gdf parameter is returned with additional columns populated with the calcualted metrics.

Notes

The following keys use the simplest-path heuristic:

keyformulanotes
density_ang∑j≠in1\sum_{j\neq{i}}^{n}1A summation of nodes.
harmonic_ang∑j≠in1d(i,j)\sum_{j\neq{i}}^{n}\frac{1}{d_{(i,j)}}Harmonic closeness is an appropriate form of closeness centrality for localised implementations constrained by the threshold dmaxd_{max}.
hillier_ang(n−1)2∑j≠ind(i,j)\frac{(n-1)^2}{\sum_{j \neq i}^{n} d_{(i,j)}}The square of node density divided by farness. This is also a simplified form of Improved Closeness Centrality.
farness_ang∑j≠ind(i,j)\sum_{j\neq{i}}^{n}d_{(i,j)}A summation of distances in metres.
betweenness_ang∑j≠in∑k≠j≠in1\sum_{j\neq{i}}^{n}\sum_{k\neq{j}\neq{i}}^{n}1Betweenness centrality summing all shortest-paths traversing each node ii.

The following keys use the simplest-path (shortest-angular-path) heuristic, and are available when the angular parameter is explicitly set to True:

segment_centrality

segment_centrality
(
network_structure : NetworkStructure
nodes_gdf : geopandas.geodataframe.GeoDataFrame
distances : list[int] | None = None
betas : list[float] | None = None
compute_closeness : bool | None = True
compute_betweenness : bool | None = True
min_threshold_wt : float = 0.01831563888873418
jitter_scale : float = 0.0
)->[ GeoDataFrame ]

Compute segment-based network centrality using the shortest path heuristic. > Simplest path heuristics introduce conceptual and practical complications and support is deprecated since v4.

For conceptual and practical reasons, segment based centralities are not weighted by node weights.

Parameters

network_structure
None

A rustalgos.NetworkStructure. Best generated with the io.network_structure_from_nx method.

nodes_gdf
None

A GeoDataFrame representing nodes. Best generated with the io.network_structure_from_nx method. The outputs of calculations will be written to this GeoDataFrame, which is then returned from the method.

distances
list[int]

Distances corresponding to the local dmaxd_{max} thresholds to be used for calculations. The β\beta parameters (for distance-weighted metrics) will be determined implicitly. If the distances parameter is not provided, then the beta parameter must be provided instead.

betas
list[float]

A β\beta, or array of β\beta to be used for the exponential decay function for weighted metrics. The distance parameters for unweighted metrics will be determined implicitly. If the betas parameter is not provided, then the distance parameter must be provided instead.

compute_closeness
bool

Compute closeness centralities. True by default.

compute_betweenness
bool

Compute betweenness centralities. True by default.

min_threshold_wt
float

The default min_threshold_wt parameter can be overridden to generate custom mappings between the distance and beta parameters. See rustalgos.distances_from_beta for more information.

jitter_scale
float

The scale of random jitter to add to shortest path calculations, useful for situations with highly rectilinear grids or for smoothing metrics on messy network representations. A random sample is drawn from a range of zero to one and is then multiplied by the specified jitter_scale. This random value is added to the shortest path calculations to provide random variation to the paths traced through the network. When working with shortest paths in metres, the random value represents distance in metres. When using a simplest path heuristic, the jitter will represent angular change in degrees.

Returns

nodes_gdf
GeoDataFrame

The input node_gdf parameter is returned with additional columns populated with the calcualted metrics.

Notes

Segment path centralities are available with the following keys:

keyformulanotes
seg_density∑(a,b)edgesdb−da\sum_{(a, b)}^{edges}d_{b} - d_{a}A summation of edge lengths.
seg_harmonic∑(a,b)edges∫abln⁡(b)−ln⁡(a)\sum_{(a, b)}^{edges}\int_{a}^{b}\ln(b) -\ln(a)A continuous form of harmonic closeness centrality applied to edge lengths.
seg_beta∑(a,b)edges∫abexp⁡(−β⋅b)−exp⁡(−β⋅a)−β\sum_{(a, b)}^{edges}\int_{a}^{b}\frac{\exp(-\beta\cdot b) -\exp(-\beta\cdot a)}{-\beta}A # pylint: disable=line-too-long continuous form of beta-weighted (gravity index) centrality applied to edge lengths.
seg_betweennessA continuous form of betweenness: Resembles segment_beta applied to edges situated on shortest paths between all nodes jj and kk passing through ii.