betweenness_centrality_online

# betweenness_centrality_online

In network studies, centrality analysis illuminates the significance of nodes, with betweenness centrality being one of the most important metrics. It determines the importance of a node based on how frequently it lies on the shortest paths between other nodes, signifying its influence on information flow within the network. Such nodes, possessing high betweenness, often act as gatekeepers in controlling the transmission of information.

While the concept of betweenness centrality revolves around shortest paths, defined by the fewest relationships or minimal cumulative relationship weight in weighted graphs, the calculation methodologies can vary. One notable method is described in the paper "A Faster Algorithm for Betweenness Centrality" (opens in a new tab)(Brandes, 2001). Additionally, the iCentral (opens in a new tab) algorithm by Jamour, Skiadopoulos, and Kalnis offers a dynamic solution tailored for graph streaming platforms like Memgraph. By pinpointing nodes with potentially altered centrality scores and incrementally updating them, iCentral optimizes computation. This efficiency translates to a time complexity of O(m′n′) and space complexity of O(m + n), making it apt for medium-scale graphs.

In essence, centrality analysis and tools like iCentral are instrumental in extracting value from complex networks, ensuring data remains current and reflective of real-time changes.

TraitValue
Module typealgorithm
ImplementationC++
Graph directionundirected
Edge weightsunweighted
Parallelismparallel

## Procedures

### `set()`

#### Input:

• `normalize: boolean (default=True)` ➡ If `True`, the betweenness values are normalized by `2/((n-1)(n-2))`, where `n` is the number of nodes in the graph.
• `threads: integer (default=Nº of concurrent threads supported by the implementation)` ➡ The number of threads used in calculating betweenness centrality.

#### Output:

• `node: Vertex` ➡ Graph vertex.
• `betweenness_centrality: float` ➡ Betweenness centrality score of the above vertex.

#### Usage:

``````CALL betweenness_centrality_online.set()
YIELD node, betweenness_centrality;``````

### `get()`

#### Input:

• `normalize: boolean (default=True)` ➡ If `True`, the betweenness values are normalized by `2/((n-1)(n-2))`, where `n` is the number of nodes in the graph.

#### Output:

• `node: Vertex` ➡ Graph vertex.
• `betweenness_centrality: float` ➡ Betweenness centrality score of the above vertex.

#### Usage:

``````CALL betweenness_centrality_online.get()
YIELD node, betweenness_centrality;``````

### `update()`

#### Input:

• `created_vertices: List[Vertex]` ➡ Vertices created in the latest graph update.
• `created_edges: List[Edge]` ➡ Edges created in the latest graph update.
• `updated_vertices: List[Vertex]` ➡ Vertices updated in the latest graph update.
• `updated_edges: List[Edge]` ➡ Edges updated in the latest graph update.
• `deleted_vertices: List[Vertex]` ➡ Vertices deleted in the latest graph update.
• `deleted_edges: List[Edge]` ➡ Edges deleted in the latest graph update.
• `normalize: boolean (default=True)` ➡ If `True`, the betweenness values are normalized by `2/((n-1)(n-2))`, where `n` is the number of nodes in the graph.
• `threads: integer (default=Nº of concurrent threads supported by the implementation)` ➡ The number of threads used in updating betweenness centrality.

#### Output:

• `node: Vertex` ➡ Graph vertex.
• `betweenness_centrality: float` ➡ Betweenness centrality score of the above vertex.

#### Usage:

As there is a total of four complex obligatory parameters, setting the parameters by hand might be cumbersome. The recommended use of this method is to call it within a trigger, making sure beforehand that all predefined variables are available:

``````CREATE TRIGGER sample_trigger BEFORE COMMIT
EXECUTE CALL betweenness_centrality_online.update(createdVertices, createdEdges, deletedVertices, deletedEdges, normalize, threads) YIELD *;``````

Communities calculated by `update()` are accessible by subsequently calling `get()`:

``````CALL betweenness_centrality_online.get()
YIELD node, betweenness_centrality;``````

## Example

### Database state

The database contains the following data: ### Create a trigger

The following query sets a trigger which will update the values upon creating new data or deleting existing data:

``````CREATE TRIGGER update_bc_trigger
BEFORE COMMIT EXECUTE
CALL betweenness_centrality_online.update(createdVertices, createdEdges, deletedVertices, deletedEdges)
YIELD *;``````

New data is added to the database:

``````MERGE (a: Node {id: 0}) MERGE (b: Node {id: 1}) CREATE (a)-[:RELATION]->(b);
MERGE (a: Node {id: 0}) MERGE (b: Node {id: 2}) CREATE (a)-[:RELATION]->(b);
MERGE (a: Node {id: 1}) MERGE (b: Node {id: 2}) CREATE (a)-[:RELATION]->(b);
MERGE (a: Node {id: 2}) MERGE (b: Node {id: 3}) CREATE (a)-[:RELATION]->(b);
MERGE (a: Node {id: 3}) MERGE (b: Node {id: 4}) CREATE (a)-[:RELATION]->(b);
MERGE (a: Node {id: 3}) MERGE (b: Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a: Node {id: 4}) MERGE (b: Node {id: 5}) CREATE (a)-[:RELATION]->(b);``````

As new data is added, the triggered `betweenness_centrality_online.update()` procedure recalculates the values.

### Get recalculated values

Return the values using the following query:

``````CALL betweenness_centrality_online.get(True)
YIELD node, betweenness_centrality
RETURN node.id AS node_id, betweenness_centrality
ORDER BY node_id;``````

Results:

``````┌─────────────────────────┬─────────────────────────┐
│ node_id                 │ betweenness_centrality  │
├─────────────────────────┼─────────────────────────┤
│ 0                       │ 0                       │
│ 1                       │ 0                       │
│ 2                       │ 0.6                     │
│ 3                       │ 0.6                     │
│ 4                       │ 0                       │
│ 5                       │ 0                       │
└─────────────────────────┴─────────────────────────┘``````