Partitions the graph into clusters using edge betweenness centrality, as proposed by Girvan and Newman.
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
@PRODUCT@ 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.
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)!)
}Type Details
- yFiles module
- view-layout-bridge
See Also
Constructors
Parameters
A map of options to pass to the method.
- directed - boolean
- A value indicating whether edge direction should be considered. This option sets the directed property on the created object.
- minimumClusterCount - number
- The minimum number of clusters that will be returned. This option sets the minimumClusterCount property on the created object.
- maximumClusterCount - number
- The maximum number of clusters that will be returned. This option sets the maximumClusterCount property on the created object.
- weights - ItemMapping<IEdge,number>
- A mapping for edge weights. This option either sets the value directly or recursively sets properties to the instance of the weights property on the created object.
- qualityTimeRatio - number
- A desired quality value for the result. This option sets the qualityTimeRatio property on the created object.
- subgraphNodes - ItemCollection<INode>
- The collection of nodes which define a subset of the graph for the algorithms to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphNodes property on the created object.
- subgraphEdges - ItemCollection<IEdge>
- The collection of edges which define a subset of the graph for the algorithms to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphEdges property on the created object.
Properties
Gets or sets a value indicating whether edge direction should be considered.
Remarks
true.Property Value
true if the graph should be considered as directed, false otherwise.1 and the graph is considered undirected.Gets or sets the maximum number of clusters that will be returned.
Remarks
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.
Gets or sets a desired quality value for the result.
Remarks
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.
Remarks
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.
Remarks
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.
Remarks
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.
Complexity
- O(|V| ⋅ |E|²) for unweighted graphs or when
is less than 1 - O(|E| ⋅ |V| ⋅ (|E| + |V|) ⋅ log |V|) for weighted graphs
Parameters
A map of options to pass to the method.
- graph - IGraph
- The input graph to run the algorithm on.
Returns
- ↪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.