documentationfor yFiles for HTML 2.6

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.

Node betweenness centrality
analysis centrality

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.

Computing centrality indices
// 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.

Closeness centrality

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.

Degree centrality

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.

Graph centrality

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.

Betweenness centrality

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.

Weight centrality

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.