Remarks
Betweenness centrality is a measure for how often a node/edge lies on a shortest path between each pair of nodes in the graph. Removing a central node/edge will cause many shortest paths to change.
The centrality can be computed for directed and undirected graphs.
weights can be assigned to each edge. If no weights are provided, then all edges have uniform weight.
Other Centrality Measures
yFiles for HTML supports a number of other centrality measures:
- GraphCentrality, ClosenessCentrality – emphasize nodes that have short paths to other nodes
- DegreeCentrality – emphasizes nodes with many edges
- WeightCentrality – emphasizes nodes with highly-weighted edges
- EigenvectorCentrality – computes the influence a node has on a network. The centrality value is higher if more nodes are connected to that node
- PageRank – computes page rank values for all nodes based on their attached edges
Complexity
- O(|V| ⋅ |E|) for unweighted graphs
- O(|V| ⋅ (|E| + |V|) ⋅ log |V|) for weighted graphs
Examples
const result = new BetweennessCentrality({
directed: true,
// Use the geometric edge length as weight
weights: (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength(),
}).run(graph)
// add edge labels for centrality values
result.normalizedEdgeCentrality.forEach(({ key, value }) => {
const edge = key
const centrality = value
graph.addLabel(edge, String(centrality))
})
// add node labels for centrality values
// and adjust node size according to centrality
result.normalizedNodeCentrality.forEach(({ key, value }) => {
const node = key
const centrality = value
graph.addLabel(key, String(value))
graph.setNodeLayout(
node,
new Rect(node.layout.center, new Size(centrality, centrality)),
)
})See Also
Developer's Guide
API
- nodeEdgeBetweenness, nodeBetweenness, edgeBetweenness
Members
Constructors
Properties
true.Property Value
true if the graph should be considered as directed, false otherwise.Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
If nothing is set, all edges of the graph will be processed.
If only the excludes are set, all edges in the graph except those provided in the excludes are processed.
Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// configure the algorithm
const algorithm = new BetweennessCentrality({
directed: true,
weights: (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength(),
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.NONE,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add edge labels for centrality values
result.normalizedEdgeCentrality.forEach((entry) =>
graph.addLabel(entry.key, `${entry.value}`),
)Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.
If nothing is set, all nodes of the graph will be processed.
If only the excludes are set, all nodes in the graph except those provided in the excludes are processed.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// configure the algorithm
const algorithm = new BetweennessCentrality({
directed: true,
weights: (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength(),
subgraphNodes: {
// only consider elliptical nodes in the graph
includes: (node: INode): boolean =>
node.style instanceof ShapeNodeStyle &&
node.style.shape === ShapeNodeShape.ELLIPSE,
// but ignore the first node, regardless of its shape
excludes: graph.nodes.first()!,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add edge labels for centrality values
result.normalizedEdgeCentrality.forEach((entry) =>
graph.addLabel(entry.key, `${entry.value}`),
)algorithm.subgraphNodes = graphComponent.selection.nodesalgorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)algorithm.subgraphNodes = graphComponent.selection.nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)Gets or sets a mapping for edge weights.
Betweenness centrality computes shortest paths throughout the graph. Edge weights influence the computed length of those paths and thus the centrality measure. If no weights are provided, all edges have the same uniform weight of 1 and the number of edges is effectively the shortest path length.
Edge weights for betweenness centrality must be finite and positive. Negative weights, weights too close to 0, and missing weights are all treated as a weight of 1.
Methods
Computes the betweenness centrality for each node and edge of a given graph.
Parameters
- graph: IGraph
- The input graph to run the algorithm on.
Return Value
- BetweennessCentralityResult
- A BetweennessCentralityResult from which the calculated centrality values can be obtained.
Throws
- Exception ({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.
Complexity
- O(|V| ⋅ |E|) for unweighted graphs
- O(|V| ⋅ (|E| + |V|) ⋅ log |V|) for weighted graphs