# ST_GraphAnalysis

### Signatures

### Description

Uses Brande’s betweenness centrality algorithm to calculate closeness and betweenness centrality for vertices and betweenness centrality for edges.

Let \(d(s, t)\) denote the **distance** from \(s \in V\) to \(t \in
V\), i.e., the minimum length of all paths connecting \(s\) to
\(t\). We have \(d(s, s) = 0\) for all \(s \in V\).

Let \(\sigma_{st}\) denote the number of shortest paths from \(s \in V\) to \(t \in V\) and set \(\sigma_{ss}=1\) by convention. Let \(\sigma_{st}(v)\) denote the number of shortest paths from \(s\) to \(t\) containing \(v \in V\).

We have the following definitions for vertices:

Betweenness centrality for edges is defined similarly.

A high closeness centrality score indicates that a vertex can reach other vertices on relatively short paths; a high betweenness centrality score indicates that a vertex lies on a relatively high number of shortest paths.

##### All centrality scores are normalized.

But this normalization depends on the graph being connected.
Use `ST_ConnectedComponents`

to make sure you're calling `ST_GraphAnalysis`

on a
single (strongly) connected component.

##### A few caveats.

Results will not be accurate if the graph:

- contains "duplicate" edges (having the same source, destination and weight)
- is disconnected. If all closeness centrality scores are zero, this is why.

Though Brande's algorithm is much faster than a naïve approach, it still requires an augmented version of Dijkstra's algorithm to be run starting from each vertex. Thus, calculation times can be rather long for larger graphs.

##### Input parameters

Variable | Meaning |
---|---|

`INPUT_EDGES` |
Table containing integer columns `EDGE_ID` , `START_NODE` and `END_NODE` ; and optionally a weight column `w` (if the graph is weighted) and/or an edge orientation column `eo` (required if global orientation is not `undirected` ) |

`o` |
Global orientation string: `directed` , `reversed` or `undirected` |

`eo` |
Edge orientation column name indicating individual edge orientations: `1` (directed), `-1` (reversed) or `0` (undirected); required if global orientation is `directed` or `reversed` |

`w` |
Edge weights column name |

##### Screenshots

Closeness centrality of Nantes, France. Notice the limited traffic zone in the center.

Edge betweenness centrality of Nantes, France. Notice how the beltway and bridges really stand out.

The above screenshots were generated in OrbisGIS.

### Examples

##### Exercises

- Use
`ST_ShortestPathTree`

to calculate the shortest path trees for nodes 1 through 5. Then use the definition of node betweenness to calculate betweenness by hand and verify the results above. - Make use of
`ST_ShortestPath`

to write a script that calculates node betweenness automatically without using`ST_GraphAnalysis`

. Make sure you get the same results as above. - Repeat exercise 2 using
`ST_ShortestPathLength`

to verify node closeness.