graph-lakehouse

Centrality Algorithms

Centrality algorithms identify important nodes in a graph:

PageRank: Ranks the nodes in a graph by their relative importance or influence. Google uses PageRank to rank websites in their search engine results.
Betweenness Centrality: Detects the amount of influence a vertex has over the flow of information in a graph.

PageRank

The PageRank algorithm ranks the nodes in a graph by their relative importance or influence. PageRank determines each node's ranking by identifying the number of links to the node, the outbound links from the node, and the quality of the links. The quality of a link is determined by the importance (PageRank) of the connected nodes. For labeled property graphs, the PageRank algorithm accepts an edge property that can be considered a relationship weight to factor into the PageRank calculation.

Syntax

The PageRank algorithm is available in the graphalgo extension library (http://cambridgesemantics.com/anzograph/graphalgo#page_rank) and is implemented as a procedure. To incorporate the PageRank algorithm in a query, use the following syntax in the FROM clause. The arguments that are links are described below.

SELECT triple_patterns_and_expressions

The FROM clause lists the URI for the page_rank alogrithm and

includes in parentheses the input parameters for the algorithm.

FROM http://cambridgesemantics.com/anzograph/graphalgo#page\_rank ( <graph_URI>, <edge_URI>, [ <weighted_property>, ] [ damping_factor, ] [ max_iterations, ] [ error_tolerance, ] [ normalized ] ) WHERE { ... }

Argument	Range	Description
graph_URI	URI	The URI of the target graph.
edge_URI	URI	The URI of the edge that connects the nodes to rank.
weighted_property	URI	Optional argument that defines the URI of the relationship property on the edge_URI that contains values to be factored in as a weight when calculating the importance of the nodes. When this property is omitted, page_rank is unweighted.
damping_factor	0.0 - 1.0	Optional argument that represents the edge traversal probability. The damping factor is an estimate of the probability that a user will stay on the page rather than follow the link (edge). The damping_factor value is subtracted from 1.0 in the calculation. The default value is `0.85`.
max_iterations	1 - 100	Optional argument that specifies the maximum number of times to iterate through the graph to adjust approximate PageRank values. The default value is `40`.
error_tolerance	0.0 - 0.1	Optional argument that specifies the error tolerance to use. If the sum of the error values for all nodes is below this tolerance value, PageRank iterations are stopped. The default value is `1e-8`.
normalized	boolean	Optional argument that controls whether to produce PageRank values that are between 0 and 1. The default value is `false`.

Examples

The example below uses the unweighted PageRank algorithm to find the 10 most connected airports. The edge to operate on is defined as the hasRouteTo URI, which links the airport nodes.

SELECT ?airport ?rank FROM http://cambridgesemantics.com/anzograph/graphalgo#page\_rank( http://anzograph.com/airline\_flight\_network, http://anzograph.com/flights/hasRouteTo ) WHERE { ?airport ?p ?rank . } ORDER BY desc(?rank) LIMIT 10

The results show that ORD (Chicago O'Hare) has the highest PageRank. It has the highest number of links to other airports.

airport | rank -----------------------------------------+--------- http://anzograph.com/flights/Airport/ORD | 13.4122 http://anzograph.com/flights/Airport/DFW | 13.1632 http://anzograph.com/flights/Airport/ATL | 12.8073 http://anzograph.com/flights/Airport/DEN | 10.3813 http://anzograph.com/flights/Airport/IAH | 8.38149 http://anzograph.com/flights/Airport/SLC | 6.90182 http://anzograph.com/flights/Airport/MSP | 6.24396 http://anzograph.com/flights/Airport/SFO | 5.50728 http://anzograph.com/flights/Airport/PHX | 5.27483 http://anzograph.com/flights/Airport/LAX | 5.24546 10 rows

By including the edge property, <http://anzograph.com/flights/distanceMiles>, the example below uses the weighted PageRank algorithm to find the 10 most connected airports where distance between the airports is factored into the calculation.

SELECT ?airport ?rank FROM http://cambridgesemantics.com/anzograph/graphalgo#page\_rank( http://anzograph.com/airline\_flight\_network, http://anzograph.com/flights/hasRouteTo, http://anzograph.com/flights/distanceMiles ) WHERE { ?airport ?p ?rank . } ORDER BY desc(?rank) LIMIT 10

airport | rank -----------------------------------------+-------- http://anzograph.com/flights/Airport/ORD | 2.445 http://anzograph.com/flights/Airport/ATL | 1.935 http://anzograph.com/flights/Airport/DFW | 1.68 http://anzograph.com/flights/Airport/SLC | 1.17 http://anzograph.com/flights/Airport/MSP | 0.915 http://anzograph.com/flights/Airport/DTW | 0.66 http://anzograph.com/flights/Airport/SFO | 0.66 http://anzograph.com/flights/Airport/FLL | 0.5325 http://anzograph.com/flights/Airport/ANC | 0.5325 http://anzograph.com/flights/Airport/DEN | 0.5325 10 rows

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.

Syntax

To incorporate the Betweenness Centrality algorithm in a query, include the following SERVICE call in the WHERE clause.

SERVICE csi:betweenness { [] csi:[binding-vertex](#betweenness-binding-vertex)\ ?binding_vertex_variable ; csi:[binding-centrality](#betweenness-binding-centrality)\ ?centrality_variable ; csi:[edge-label](#betweenness-edge-label)\ <edge_uri> . }

Argument	Range	Description
binding-vertex	variable	Required argument that defines the name to use for the result column that lists the source nodes (vertices).
binding-centrality	variable	Required argument that defines the name to use for the result column that lists the computed centrality score.
edge-label	URI	Required argument 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.

Example

The example below uses the Betweenness Centrality algorithm to find the 10 airports with the highest 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

Source: https://docs.sw.siemens.com/documentation/external/PL20260518131381558/en-US/html/graphalgo-centrality.htm · retrieved 2026-08-23