Centrality Measures
For the elements of a graph the notion of importance of a single node or edge within the graph structure can be expressed using so-called centrality measures. A centrality measure is a function that yields a double value for each node or each edge. This value directly denotes the graph element’s importance, i.e., the higher the value, the more important the element.
The classes DegreeCentrality, WeightCentrality, ClosenessCentrality, GraphCentrality, PageRank and EigenvectorCentrality provides a variety of such centrality measures only for nodes while BetweennessCentrality calculates measures for both nodes and edges. Most of these algorithms also optionally take edge weights into account.
Node betweenness centrality depicts a graph with node centrality values at the upper-right corner of the nodes. The numbers at the edges denote weights that are associated with an edge.
The centrality algorithms can be configured to either ignore or respect edge direction when computing centrality indices. DegreeCentrality and WeightCentrality can even be configured to only consider incoming edges.
The DegreeCentralityResult classes returned by the algorithms not only provide the centrality value for each node but also the minimum and maximum centrality assigned to a node, and a normalized centrality that lies in the interval [0, 1].
Computing centrality indices shows the code to prepare and run the betweenness centrality algorithm on the graph depicted in Node betweenness centrality ignoring edge directions but using some edge weights.
// configure the betweenness algorithm
const betweennessCentrality = new BetweennessCentrality({
directed: false,
weights: (edge) => getEdgeWeight(edge)
})
// calculate the centrality values
const betweennessCentralityResult = betweennessCentrality.run(graph)
// add a label to each node that shows its normalized centrality
betweennessCentralityResult.normalizedNodeCentrality.forEach((entry, centrality) => {
graph.addLabel(entry.key, centrality.toString(), ExteriorLabelModel.NORTH_EAST)
})
Closeness Centrality
Closeness centrality is defined as the reciprocal of the sum of the shortest path distances of a node to all other nodes in the graph. Therefore, a node with high closeness centrality has short distances to all other nodes of a graph. The algorithm ClosenessCentrality supports both directed and undirected edges and optional edge weights.
Degree Centrality
The degree centrality is determined using the degree (the number incoming and outgoing edges) to determine the centrality value for each node. The algorithm DegreeCentrality optionally can be restricted to incoming or outgoing edges.
Graph Centrality
Graph centrality is defined as the reciprocal of the maximum of all shortest path distances from a node to all other nodes in the graph. Nodes with high graph centrality have short distances to all other nodes in the graph. The algorithm GraphCentrality supports both directed and undirected edges and optional edge weights.
Node Edge Betweeness Centrality
Betweenness centrality is a measure for how often a node or edge lies on a shortest path between each pair of nodes in the graph. The algorithm BetweennessCentrality supports both directed and undirected edges and optional edge weights.
Weight Centrality
Weight centrality measures the weight associated with incoming, outgoing, or all edges of a node. When no weights are associated with edges, weight centrality becomes the same as degree centrality. The algorithm WeightCentrality optionally can be restricted to incoming or outgoing edges. It also supports edge weights.
PageRank
The Page Rank algorithm computes page rank values for all nodes based on their attached edges. The algorithm starts by initializing the rank value for each node. After that it uses multiple iterations to propagate the rank of a node to its successors. The algorithm PageRank supports both directed and undirected edges and optional edge weights.
Eigenvector Centrality
Eigenvector centrality is a measure of the influence a node has on a network: The more nodes point to a node the higher is that node’s centrality. The EigenvectorCentrality algorithm computes the centrality for each node of a given undirected, unweighted graph.