Skip to main content

betweenness_centrality_online

docs-source

Abstract​

Betweenness centrality is among the most common metrics in graph analytics owing to its utility in identifying critical vertices of graphs. It is one of the tools in centrality analysis, a set of techniques for measuring the importance of nodes in networks.

The notion of Betweenness centrality is based on shortest paths: the shortest path between two nodes is the one consisting of the fewest edges, or in case of weighted graphs, the one with the smallest total edge weight. A node’s betweenness centrality is defined as the share of all shortest paths in the graph that run through it.

This query module delivers a fully dynamic betweenness centrality computation tool using the iCentral 1 algorithm by Jamour, Skiadopoulos and Kalnis. iCentral saves up on computation in two ways: it singles out the nodes whose centrality scores could have changed and then incrementally updates their scores, making use of previously calculated data structures where applicable.

This drives down the algorithm’s time complexity to O(mβ€²nβ€²) and space complexity to O(m + n), where m and n are the counts of edges and vertices in the graph, mβ€² is the number of edges in the biconnected component affected by the graph update, and nβ€² is the size of a subset of the nodes in the biconnected component. Consequently, the algorithm is suitable for mid-scale graphs.

Dynamic algorithms such as iCentral are especially suited for graph streaming solutions such as Memgraph. As updates arrive in a stream, the algorithm avoids redundant work by processing only the portion of the graph affected by the update.

1 Parallel Algorithm for Incremental Betweenness Centrality on Large Graphs (Jamour et al., 2017)

TraitValue
Module typealgorithm
ImplementationC++
Graph directionundirected
Edge weightsunweighted
Parallelismparallel

Procedures​

set(normalize, threads)​

Input:​

  • normalize: bool(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: int(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(normalize)​

Input:​

  • normalize: bool(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(created_vertices, created_edges, deleted_vertices, deleted_edges, normalize, threads)​

  • 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: bool(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: int(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​