documentationfor yFiles for HTML 3.0.0.3

LabelPropagationClustering

Show usages

Detects the communities in the specified input graph by applying a label propagation algorithm.

Inheritance Hierarchy
LabelPropagationClustering

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 neighbor's 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.0 and the edge is incoming (i.e. n is the edge's target),
  • the edge's directedness is smaller than 0.0 and 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

@PRODUCT@ supports a number of other clustering algorithms:

Examples

Calculating clusters of a graph using the label propagation method
// 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)!)
}
Excluding self-loop edges
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

See Also

LayoutGraphAlgorithms.labelPropagation
A node with a self-loop is considered to be a neighbor of itself. Hence, the node's label is also included when calculating the most frequent label among the neighbors. If you want to prevent this, you can explicitly exclude self-loop edges. Alternatively, you can specify suitable edge weights. Setting the weight of self-loops to 0.0 results in ignoring them.
If none of the neighbors of a node is associated with a label with positive weight, the node keeps its current label.
If no edgeDirectedness is specified, the algorithm assumes that all edges are undirected (i.e. have directedness 0.0).
The labels which are considered in this algorithm are internally assigned integer values. They have nothing to do with the marking objects which are commonly referred to as "label" in @PRODUCT@.

Constructors

Properties

Methods