Gatekeeping

Betweenness Centrality scores a node by the shortest paths running through it.

The graph below reuses the two triangles from the Articulation lesson.

Alice and Dmitri sit on every shortest path between the two triangles.

For example, Mehmet, Mark and Dmitri cannot reach Cesar or Bridget unless they travel through Alice. Notice also, Mehmet and Mark must travel through Dmitri to reach Alice.

The same is true in reverse, from Bridget and Cesar.

We can therefore assign Alice and Dmitri with high betweenness scores — every shortest path between any two nodes must travel through Alice and Dmitri.

That is functionally how the algorithm works. However, you can look at it a different way.

Both Alice and Dmitri are chokepoints or gatekeepers in the network.

If Mark wants to send out a message, and have it reach anyone on the Alice side, it must travel through Alice. If Alice decides not to pass it on, it won't go further than her.

The previous explanation correctly asserts that a node can be a gatekeeper. However, it risks implying that all gatekeepers must be chokepoints. This is not true.

Imagine a graph of a Roman Emperor's familial and political circle.

In this graph, there are no chokepoints, per se. Octavia speaks to Livia and Julia directly, and reaches everyone else only by passing through Livia first.

Agrippa can get a message to Julia through Maecenas, Livia and Octavia — several hops away, and every one of them indirect.

However, the shortest path from any one node to most other nodes goes through Augustus in almost every case.

Augustus is not a chokepoint, but he is on the shortest path for almost every message sent through the graph between other nodes. In this case, he too has high betweenness.

In the Explore the graph lesson you ran this query for 170 and 178, then for 1607 and 1802. Both routes ran from nodes with single relationshipsiFull definition for relationship (opens in a new tab)A named, directed connection between two nodes. Every relationship has a type, a start node and an end node. and through nodes with hundreds of relationships.

Run it again now.

MATCH path = SHORTEST 1
  (:Person {id: '170'})-[:MESSAGED]-+(:Person {id: '178'}) // (1)
RETURN path

Double-click the nodes in the chain to see the full scope of their relationships. Try to guess which of these nodes will have the highest betweenness.

Betweenness Centrality takes every pair of nodes in the graph and counts how many of the shortest routes between them pass through each node.

Run it now on the directed graph.

CALL gds.betweenness.write( // (1)
  'directed', // (2)
  { writeProperty: 'betweenness' } // (3)
)
YIELD nodePropertiesWritten // (4)
RETURN nodePropertiesWritten

Your output should look like this:

Every (:Person) node now carries a betweenness score.

Run the following query to rank people by their betweenness scores.

MATCH (p:Person)
RETURN p.id AS person,
       toInteger(p.betweenness) AS betweenness,
       COUNT { (p)-[:MESSAGED]->(:Person) } AS messages
ORDER BY betweenness DESC
LIMIT 6

Your output should look something like this:

Person 32 holds the highest at 161,047, having sent 457 messages.

Person 9 sat in the middle of the first route you traced, and sent 1,091 messages. On routes that follow the direction of each message, 9 is sixth with 97,318.

Notice here how the betweenness score is not predicted by how many messages someone sent. Person 32 sent many fewer messages than others in this list, but still comes out on top.

The following query returns a graph of Person 32 and Person 1624 including their local neighbourhoods. Run it now, and examine the graph.

MATCH path = (:Person {id: '32'})-[:MESSAGED]-(:Person)
RETURN path
UNION
MATCH path = (:Person {id: '1624'})-[:MESSAGED]-(:Person)
RETURN path

The query should return a relatively large visualization of both nodes' local networks, including some shared nodes.

Person 1624 sent 640 messages. Person 32 sent approximately one-third fewer messages overall.

Person 1624's betweenness score still sits well below Person 32's.

To see what Betweenness Centrality is seeing, take a closer look at the local graph structure of each node.

You should notice that, while Person 1624 sent more messages, their broader network is also more insular, with lots of repeat messages to the same people, and few of them leaving the locale.

Person 32 sends fewer messages, but to more people. Each new node in that network offers another chance for a shortest path between any pair to include Person 32.

Betweenness is useful for analyzing the low-betweenness sections of your graphs, too.

Run this to count the people at zero.

MATCH (p:Person)
RETURN sum(CASE WHEN p.betweenness = 0 THEN 1 ELSE 0 END) AS zero,
       sum(CASE WHEN p.betweenness > 0 THEN 1 ELSE 0 END) AS nonzero

Your output should look like this:

670 people sit on nobody's shortest route. 1,229 people sit on at least one.

As with all algorithms, the meaning of a Betweenness Centrality result will change based on the analyzed graph.

For instance, had you run it on the undirected projection, a route could also follow a message backwards. Person 9 would have risen from 97,318 to 129,080, and Person 32 would have fallen from 161,047 to 107,236.

Similarly, a graph that modelled each message as its own node would put every pair of people two steps apart, and every route between them would run through a message. In such a model, message nodes would likely take a larger share of top-band results.

Later, you will learn more about the nuances of Betweenness Centrality in its dedicated lab.