C

KMeansClustering

Show Usages
Partitions the graph into clusters using k-means clustering.
Inheritance Hierarchy

Remarks

The nodes of the graph will be partitioned into k clusters, based on their positions such that their distance to the cluster's mean (centroid) is minimized.

Other Clustering Algorithms

yFiles for HTML supports a number of other clustering algorithms:

Complexity

O(|V| ⋅ k ⋅ I) where k is the and I the

Examples

Calculating the k-means clusters of a graph
// prepare the k-means clustering algorithm
const algorithm = new KMeansClustering()
// 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

kMeansClustering

Members

No filters for this type

Constructors

KMeansClustering

()

Parameters

Properties

centroids

: IEnumerable<Point>
Gets or sets the initial centroids.
If the number of initial centroids is smaller than k or if no centroids are given, random initial centroids will be assigned for all clusters.
conversionfinal

k

: number
Gets or sets the number of clusters.
Default is 1.
If the number of given centroids is smaller than k or if no centroids are given, random initial centroids will be assigned for all clusters.
final

maximumIterations

: number
Gets or sets the maximum number of iterations performed by the algorithm for convergence.
Default is 100.
final

metric

: KMeansDistanceMetric
Gets or sets a metric to determine the distance between nodes and between nodes and centroids.
Default is EUCLIDEAN.
conversionfinal

subgraphEdges

: ItemCollection<IEdge>
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.

The edges provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Calculating the k-means clusters on a subset of the graph
// prepare the k-means clustering algorithm
const algorithm = new KMeansClustering({
  // 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)!)
}

subgraphNodes

: ItemCollection<INode>
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.

The nodes provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Calculating the k-means clusters on a subset of the graph
// prepare the k-means clustering algorithm
const algorithm = new KMeansClustering({
  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)!)
}

Methods

run

(graph: IGraph): KMeansClusteringResult
Partitions the graph into clusters using k-means clustering.
If the number of given centroids is smaller than k or if no centroids are given, random initial centroids will be assigned for all clusters.
The result obtained from this algorithm is a snapshot which is no longer valid once the graph has changed, e.g. by adding or removing nodes or edges.
final

Parameters

graph: IGraph
The input graph to run the algorithm on.

Return Value

KMeansClusteringResult
The resulting (non-empty) 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| ⋅ k ⋅ I) where k is the and I the