Remarks
Betweenness centrality is a measure for how often a node lies on a shortest path between each pair of nodes in the graph.
In each iteration the edge with the highest betweenness centrality is removed from the graph. The method stops if there are no more edges to remove or if the requested maximum number of clusters is found. The clustering with the best quality reached during the process is returned.
The algorithm includes several heuristic speed-up techniques available through the qualityTimeRatio. For the highest quality setting, it is used almost unmodified. The fast betweenness approximation of Brandes and Pich (Centrality Estimation in Large Networks) is employed for values around 0.5. Typically, this results in a tiny decrease in quality but a large speed-up and is the recommended setting. To achieve the lowest running time, a local betweenness calculation is used (Gregory: Local Betweenness for Finding Communities in Networks).
Other Clustering Algorithms
yFiles for HTML supports a number of other clustering algorithms:
- KMeansClustering – partitions the graph into clusters based on the distance between nodes and the cluster midpoints.
- HierarchicalClustering – partitions the graph into clusters by merging smaller clusters based on their distance.
- BiconnectedComponentClustering – partitions the graph into clusters based on its biconnected components.
- LouvainModularityClustering – partitions the graph into clusters by applying the Louvain modularity method.
- LabelPropagationClustering – partitions the graph into clusters by applying a label propagation algorithm.
Complexity
- O(|V| ⋅ |E|²) for unweighted graphs or when
is less than 1 - O(|E| ⋅ |V| ⋅ (|E| + |V|) ⋅ log |V|) for weighted graphs
Examples
// prepare the edge betweenness clustering algorithm
const algorithm = new EdgeBetweennessClustering()
// run the algorithm
const result = algorithm.run(graph)
// highlight the nodes of the clusters with different styles
for (const node of graph.nodes) {
const componentId = result.nodeClusterIds.get(node)!
graph.setStyle(node, clusterStyles.get(componentId)!)
}See Also
Developer's Guide
API
- edgeBetweennessClustering, edgeBetweennessClustering
Members
Constructors
Properties
true.1 and the graph is considered undirected.Property Value
true if the graph should be considered as directed, false otherwise.A negative value will not limit the number of clusters.
Despite the value of this setting, the number of clusters is always at least the number of connected components in the graph.
Default is -1 meaning that there is no limit for the number of clusters.
See Also
Developer's Guide
A negative value (or 0) will not constrain the minimum number of clusters.
Default is 0.
This must be a value between 0.0 (low quality, faster) and 1.0 (high quality, slower). For large graphs the recommended value is 0.5.
Default is 1.
Property Value
0 (low quality, fast) and 1 (high quality, slow). For large graphs the recommended value is 0.5.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 that 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
// prepare the edge betweenness clustering algorithm
const algorithm = new EdgeBetweennessClustering({
// 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)
// highlight the nodes of the clusters with different styles
for (const node of graph.nodes) {
const componentId = result.nodeClusterIds.get(node)!
graph.setStyle(node, clusterStyles.get(componentId)!)
}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
// prepare the edge betweenness clustering algorithm
const algorithm = new EdgeBetweennessClustering({
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)
// highlight the nodes of the clusters with different styles
for (const node of graph.nodes) {
const componentId = result.nodeClusterIds.get(node)!
graph.setStyle(node, clusterStyles.get(componentId)!)
}Gets or sets a mapping for edge weights.
Edge weights influence the importance of certain edges. If no weights are provided at all, all edges have the same uniform weight of 1.
Edge weights for edge betweenness clustering must be finite and positive.
1, as the heuristics assume uniform weights.Methods
Partitions the graph into groups using edge betweenness centrality.
Parameters
- graph: IGraph
- The input graph to run the algorithm on.
Return Value
- EdgeBetweennessClusteringResult
- A EdgeBetweennessClusteringResult containing the computed clusters.
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 or when
is less than 1 - O(|E| ⋅ |V| ⋅ (|E| + |V|) ⋅ log |V|) for weighted graphs