Betweenness Centrality

Betweenness centrality is a measure of the amount of influence a vertex has over the flow of information in a graph. The amount of influence is determined by the number of shortest paths that pass through a vertex. The Betweenness Centrality algorithm computes the shortest path between each pair of vertices in a graph and assigns a score to each vertex based on the number of shortest paths that intersect it. Vertices that frequently lie on the shortest paths between other nodes have higher betweenness centrality scores.

Betweenness Centrality Syntax

Graph algorithms are accessed from an internal SPARQL service endpoint. To incorporate the Betweenness Centrality algorithm in a query, include a SERVICE statement in the WHERE clause. The service call specifies the name of the algorithm and defines the required and optional property values for that algorithm.

Use the following syntax to find the betweenness centraily for nodes in a graph. The table below describes each property.

SERVICE <csi:betweenness> {
  [] <csi:binding-vertex>          ?binding_vertex_variable_name ;
     <csi:binding-centrality>      ?centrality_variable_name ;
     <csi:edge-label>              <edge_uri> .
}
Property Description Range & Default Value
<csi:binding-vertex> Required property that defines the name to use for the result column that lists the nodes that are reachable by the source-vertex. Range: Must be a variable name
Default: none
<csi:binding-centrality> Required property that defines the name to use for the result column that lists the computed centrality score. Range: Must be a variable name
Default: none
<csi:edge-label> Required property that lists the edge URI that defines the graph to operate on. The graph is the set of vertices that are connected by this URI. Range: Must be a URI
Default: none

Betweenness Centrality Examples

The examples below are run against a sample flight network data set, which contains data about flights, airlines, and airport locations. For instructions on downloading the sample data and loading it to AnzoGraph so that you can run the example queries, see Sample Data for Graph Algorithm Examples.

The example below uses the Betweenness Centrality algorithm to find the 10 airports with the highest betweenness centrality. The edge to operate on is defined as the hasRouteTo URI, which links the airport vertices.

prefix : <http://anzograph.com/data#>
prefix fl: <http://anzograph.com/flights/>
prefix owl: <http://www.w3.org/2002/07/owl#>
prefix skos:    <http://www.w3.org/2004/02/skos/core#>

SELECT *
FROM <http://anzograph.com/airline_flight_network>
WHERE
  { 
    SERVICE <csi:betweenness> 
    {
        [] <csi:binding-vertex> ?airport ;
           <csi:binding-centrality> ?centrality ;
           <csi:edge-label> <http://anzograph.com/flights/hasRouteTo> .
    }
}
ORDER BY desc(?centrality)
LIMIT 10
airport                                  | centrality
-----------------------------------------+--------------
http://anzograph.com/flights/Airport/ORD | 18985.371039
http://anzograph.com/flights/Airport/DFW | 17718.273941
http://anzograph.com/flights/Airport/ATL | 16286.345255
http://anzograph.com/flights/Airport/DEN | 12421.967745
http://anzograph.com/flights/Airport/SLC |  8304.111011
http://anzograph.com/flights/Airport/MSP |  6835.823598
http://anzograph.com/flights/Airport/IAH |  6022.854234
http://anzograph.com/flights/Airport/SEA |  4895.147059
http://anzograph.com/flights/Airport/SFO |  4696.686488
http://anzograph.com/flights/Airport/DTW |  3978.338284
10 rows
Related Topics