Detects the communities in the specified input graph by applying a label propagation algorithm.
Remarks
This algorithm iteratively assigns a label to each node. The label of a node is set to the most frequent label among its neighbors. If there are multiple candidates the algorithm randomly chooses one of them. After applying the algorithm, all nodes with the same label belong to the same community.
The implementation is based on the description in: "Near linear time algorithm to detect community structures in large-scale networks" by U. N. Raghavan, R. Albert, and S. Kumara in Phys. Rev. E 76, 036106, 2007
For a given node and neighbor, the weight of the neighbors label is nodeWeight(neighbor) * edgeWeight((node, neighbor)). In addition, the overall weight of a specific label is the sum of such weights for all neighbors with matching label. The weights are specified in nodeWeights and edgeWeights, respectively. If no values are provided uniform weights of 1.0 are applied.
If no initialLabels are provided each node starts with a unique label. Otherwise, at the start of the algorithm, each node is associated with the label specified with initialLabels Negative values are ignored, i.e., at the start there may be nodes without label. This implies that there may be results, where some of the nodes are not associated with labels, too. Such nodes are not associated with any cluster.
If edgeDirectedness is specified, the algorithm only considers a subset of the neighbors when determining the label of a node. More precisely, it only considers the neighbors connected by edges to a node n for which
- the edge's directedness is greater than
0.0and the edge is incoming (i.e. n is the edge's target), - the edge's directedness is smaller than
0.0and the edge is outgoing (i.e. n is the edge's source), - or the edge's directedness is
0.0(i.e. the edge is considered to be undirected).
Other Clustering Algorithms
yFiles for HTML supports a number of other clustering algorithms:
- EdgeBetweennessClustering – partitions the graph into clusters based on edge-betweenness centrality.
- 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.
Examples
// prepare the label propagation algorithm
const algorithm = new LabelPropagationClustering({
edgeWeights: (edge) =>
edge.style instanceof PolylineEdgeStyle
? edge.style.stroke.thickness
: 0,
nodeWeights: (node) => node.layout.width
})
// 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))
}// prepare the label propagation algorithm
const algorithm = new LabelPropagationClustering({
edgeWeights: (edge) =>
edge.style instanceof PolylineEdgeStyle
? edge.style.stroke!.thickness
: 0,
nodeWeights: (node) => node.layout.width
})
// 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)!)
}const algorithm = new LabelPropagationClustering({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge) => edge.sourceNode === edge.targetNode
}
})const algorithm = new LabelPropagationClustering({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.sourceNode === edge.targetNode
}
})Type Details
- yfiles module
- view-layout-bridge
- yfiles-umd modules
- view-layout-bridge
- Legacy UMD name
- yfiles.analysis.LabelPropagationClustering
See Also
0.0 results in ignoring them.0.0).Constructors
Creates a new instance of this class.
Parameters
A map of options to pass to the method.
- initialLabels - ItemMapping<INode,number>
A mapping that stores the initial integer labels of each node. This option sets the initialLabels property on the created object.
- nodeWeights - ItemMapping<INode,number>
A mapping for node weights. This option sets the nodeWeights property on the created object.
- edgeWeights - ItemMapping<IEdge,number>
A mapping for edge weights. This option sets the edgeWeights property on the created object.
- edgeDirectedness - ItemMapping<IEdge,number>
A mapping that stores the directedness of the edges. This option sets the edgeDirectedness 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 sets 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 sets the subgraphEdges property on the created object.
Properties
Gets or sets a mapping that stores the directedness of the edges.
Remarks
- the edge's directedness is greater than
0.0and the edge is incoming (i.e. n is the edge's target), - the edge's directedness is smaller than
0.0and the edge is outgoing (i.e. n is the edge's source), - or the edge's directedness is
0.0(i.e. the edge is considered to be undirected).
Gets or sets a mapping for edge weights.
Remarks
nodeWeight(neighbor) * edgeWeight((node, neighbor)). In addition, the overall weight of a specific label is the sum of such weights for all neighbors with matching label. The weights are specified in nodeWeights and edgeWeights, respectively. If no values are provided uniform weights of 1.0 are applied.Gets or sets a mapping that stores the initial integer labels of each node.
Remarks
At the start of the algorithm, each node is associated with the label specified here. Negative values are ignored, i.e., at the start there may be nodes without label. This implies that there may be results, where some of the nodes are not associated with labels, too. Such nodes are not associated with any cluster.
If nothing is set each node starts with a unique label.
Gets or sets a mapping for node weights.
Remarks
nodeWeight(neighbor) * edgeWeight((node, neighbor)). In addition, the overall weight of a specific label is the sum of such weights for all neighbors with matching label. The weights are specified in nodeWeights and edgeWeights, respectively. If no values are provided uniform weights of 1.0 are applied.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 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
// prepare the label propagation algorithm
const algorithm = new LabelPropagationClustering({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge) =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow === IArrow.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))
}// prepare the label propagation algorithm
const algorithm = new LabelPropagationClustering({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow === IArrow.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 label propagation algorithm
const algorithm = new LabelPropagationClustering({
subgraphNodes: {
// only consider elliptical nodes in the graph
includes: (node) =>
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))
}// prepare the label propagation algorithm
const algorithm = new LabelPropagationClustering({
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
Detects the communities in the specified input graph by applying a label propagation algorithm.
Remarks
This algorithm iteratively assigns a label to each node. The label of a node is set to the most frequent label among its neighbors. If there are multiple candidates the algorithm randomly chooses one of them. After applying the algorithm, all nodes with the same label belong to the same community.
For a given node and neighbor, the weight of the neighbors label is nodeWeight(neighbor) * edgeWeight((node, neighbor)). In addition, the overall weight of a specific label is the sum of such weights for all neighbors with matching label. The weights are specified in nodeWeights and edgeWeights, respecitvely. If no values are provided uniform weights of 1.0 are applied.
If no initialLabels are provided each node starts with a unique label. Otherwise, at the start of the algorithm, each node is associated with the label specified with initialLabels Negative values are ignored, i.e., at the start there may be nodes without label. This implies that there may be results, where some of the nodes are not associated with labels, too. Such nodes are not associated with any cluster.
If edgeDirectedness is specified, the algorithm only considers a subset of the neighbors when determining the label of a node. More precisely, it only considers the neighbors connected by edges to a node n for which
- the edge's directedness is greater than
0.0and the edge is incoming (i.e. n is the edge's target), - the edge's directedness is smaller than
0.0and the edge is outgoing (i.e. n is the edge's source), - or the edge's directedness is
0.0(i.e. the edge is considered to be undirected).
Parameters
A map of options to pass to the method.
- graph - IGraph
- The undirected input graph.
Returns
- ↪LabelPropagationClusteringResult
- The resulting clusters.
Throws
- Exception({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.
Examples
// prepare the label propagation algorithm
const algorithm = new LabelPropagationClustering({
edgeWeights: (edge) =>
edge.style instanceof PolylineEdgeStyle
? edge.style.stroke.thickness
: 0,
nodeWeights: (node) => node.layout.width
})
// 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))
}// prepare the label propagation algorithm
const algorithm = new LabelPropagationClustering({
edgeWeights: (edge) =>
edge.style instanceof PolylineEdgeStyle
? edge.style.stroke!.thickness
: 0,
nodeWeights: (node) => node.layout.width
})
// 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)!)
}const algorithm = new LabelPropagationClustering({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge) => edge.sourceNode === edge.targetNode
}
})const algorithm = new LabelPropagationClustering({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.sourceNode === edge.targetNode
}
})0.0 results in ignoring them.0.0).