Skip to content

Betweenness and Closeness Centrality

Betweenness centrality measures how often a node lies on the shortest path between two other nodes. A high score marks a node that connects parts of the graph, such as a bridge between two teams or a gateway between two clusters of accounts.

Closeness centrality measures how close a node is to every other node. A high score marks a node that reaches the rest of the selected graph in few steps.

Both procedures score only the nodes and relationships the caller can read. Under row-level security they use the same data a MATCH query sees.

Version requirement

Betweenness and closeness centrality from Cypher are available in PuppyGraph 1.20.0 and later.

Syntax

Call the procedure with one argument map:

CALL algo.centrality.betweenness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS']
})
YIELD vertexId, score
RETURN vertexId, score
CALL algo.centrality.closeness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS']
})
YIELD vertexId, score
RETURN vertexId, score

The values in the map can be literals or query parameters, such as $labels. List only the columns you need after YIELD. A call without YIELD returns vertexId and score, and YIELD score AS centrality renames a column.

An unknown argument name, an argument of the wrong type, or a missing labels or relationshipTypes is refused with a message that names the argument.

Note

In PuppyGraph 1.20.0, a MATCH that follows a CALL ... YIELD needs a WITH between them. The join example below uses WITH for that reason.

Sample graph

The examples on this page use the following graph. Each example is a complete query that runs as written once the graph is modeled with the Person node label and the KNOWS relationship type, using the properties in the tables below.

id name
a Alice
b Bob
c Carol
d Dave
id from to weight
k1 a a 1.0
k2 a b 2.0
k3 b a 1.0
k4 b c 1.0
k5 c d 3.0
k6 d b 1.0

The relationships include a self-loop and several cycles. Node IDs use the form Person[a], the value id(p) returns. Relationship IDs use the form KNOWS[k1], the value id(r) returns.

Parameters

Name Type Default Meaning
labels list of strings required Node labels to score.
relationshipTypes list of strings required Relationship types to follow.
relationshipWeightProperty string no weight Property that holds the distance of each relationship. Without it, every relationship counts as 1.
undirected boolean false Follow every relationship in both directions.
normalize boolean true Scale the score. See Scoring.
excludeNodeIds list of strings [] Node IDs to leave out, such as Person[c].
excludeRelationshipIds list of strings [] Relationship IDs to leave out, such as KNOWS[k6].

labels and relationshipTypes must be non-empty lists. The two exclusion lists take the IDs that id(n) and id(r) return. A null or negative value in the weight property is refused, and a null value for any argument is refused.

Output

Column Type Meaning
vertexId string The ID of the node, such as Person[b].
score double The centrality score of the node.

Each call returns one row per node in the selected subgraph, including nodes whose score is 0.

Scoring

With normalize: true, the score is rescaled so it is comparable across graphs of different sizes. Betweenness is divided by the number of pairs of other nodes: ordered pairs for a directed call, or unordered pairs when undirected: true. A score of 1 means every shortest path between two other nodes passes through the node. For closeness, the number of nodes minus one is divided by the total distance, so a score of 1 means the average distance to the other nodes is 1: relationships for an unweighted call, and total weight when relationshipWeightProperty is set.

For closeness, a node that cannot reach every other selected node scores 0, with either normalization setting.

With normalize: false, you get the raw values. Betweenness adds, for every pair of other nodes, the fraction of shortest paths between them that pass through the node, so the value can be fractional when shortest paths tie. Closeness is 1 divided by the total distance.

relationshipWeightProperty turns each relationship into a distance. The algorithms choose paths with the smallest total weight instead of the fewest relationships. Negative weights are not accepted.

undirected: true lets every relationship be followed in either direction when paths and distances are computed. A relationship d -> b then also carries traffic from b to d, which changes both which paths exist and how long they are.

Selecting the subgraph

labels and relationshipTypes decide which nodes and relationships are scored. Only nodes with one of the listed labels get a row, and only relationships with one of the listed types are followed. On a large graph, start with narrow lists rather than scoring every label and type.

excludeNodeIds and excludeRelationshipIds leave out a region you already know should not take part, such as a set of test accounts or a relationship that was voided. Excluded nodes get no row.

Node limit

A call scores at most 2,000 nodes, counted after the exclusion lists are applied. A selection that contains more is refused before scoring, with a message that asks you to narrow it with labels, relationshipTypes, excludeNodeIds or excludeRelationshipIds.

Memory for large graphs

A call holds the selected subgraph in memory while it scores, so the node limit alone does not make every graph cheap. Narrow labels and relationshipTypes first, and use the exclusion lists to remove regions that do not matter.

When the query does not run under row-level security, the engine's graph cache can keep a loaded subgraph in memory after the call returns. To stop it from retaining the graph, start PuppyGraph with GRAPH_FEATURES=feature.engine.enableGraphCache:false. To keep the cache but bound how long it holds a subgraph, set GRAPH_FEATURES=feature.engine.graphCacheExpireMinutes:<minutes> instead.

Examples

Unweighted betweenness

Bob lies on more shortest paths than any other node, because traffic from Alice's side of the graph to Carol and Dave passes through him.

CALL algo.centrality.betweenness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS']
})
YIELD vertexId, score
RETURN vertexId, score
ORDER BY score DESC, vertexId
vertexId score
Person[b] 0.8333333333333334
Person[c] 0.3333333333333333
Person[d] 0.3333333333333333
Person[a] 0.0

Unweighted closeness

Bob reaches the other three nodes in at most two relationships, so he has the highest closeness.

CALL algo.centrality.closeness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS']
})
YIELD vertexId, score
RETURN vertexId, score
ORDER BY score DESC, vertexId
vertexId score
Person[b] 0.75
Person[d] 0.6
Person[a] 0.5
Person[c] 0.5

Weighted closeness

With weight as the distance, Dave scores highest. Bob's route to Dave passes through Carol's relationship, which costs 3.0, while Dave reaches Bob in one step through k6.

CALL algo.centrality.closeness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS'],
  relationshipWeightProperty: 'weight'
})
YIELD vertexId, score
RETURN vertexId, score
ORDER BY score DESC, vertexId
vertexId score
Person[d] 0.6
Person[b] 0.5
Person[a] 0.2727272727272727
Person[c] 0.25

Undirected raw closeness

undirected: true lets Bob use k6 in the reverse direction, so every other node is one relationship away. normalize: false returns 1 divided by the total distance, which is 1/3 for Bob.

CALL algo.centrality.closeness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS'],
  undirected: true,
  normalize: false
})
YIELD vertexId, score
RETURN vertexId, score
ORDER BY score DESC, vertexId
vertexId score
Person[b] 0.3333333333333333
Person[c] 0.25
Person[d] 0.25
Person[a] 0.2

Join the scores back to node properties

Use WITH to carry the yielded columns into the following MATCH, then read properties from the matched node.

CALL algo.centrality.betweenness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS']
})
YIELD vertexId, score
WITH vertexId, score
MATCH (p:Person)
WHERE id(p) = vertexId
RETURN p.name AS name, score
ORDER BY score DESC, name
name score
Bob 0.8333333333333334
Carol 0.3333333333333333
Dave 0.3333333333333333
Alice 0.0

Leave out a relationship

Excluding k6 removes Dave's only outgoing relationship. The scores change because paths through that relationship no longer exist.

CALL algo.centrality.betweenness({
  labels: ['Person'],
  relationshipTypes: ['KNOWS'],
  excludeRelationshipIds: ['KNOWS[k6]']
})
YIELD vertexId, score
RETURN vertexId, score
ORDER BY score DESC, vertexId
vertexId score
Person[b] 0.3333333333333333
Person[c] 0.3333333333333333
Person[a] 0.0
Person[d] 0.0