Skip to content

Latest commit

 

History

History
119 lines (97 loc) · 4.75 KB

pgx_builtin_c1_community_detection_label_propagation.md

File metadata and controls

119 lines (97 loc) · 4.75 KB

Label Propagation

Label Propagation is an algorithm designed to find community structures in a graph. It assigns a unique community label to each vertex in the graph, which then is updated on each iteration by looking and choosing the most frequent label amongst those from its neighbors. Convergence is achieved once the label of each vertex is the same as the most frequent one amongst its neighbors, i.e. when there are no changes in the communities assigned to the vertices in one iteration.

Signature

Input Argument Type Comment
G graph
max_iter int maximum number of iterations that will be performed.
Output Argument Type Comment
label vertexProp vertex property holding the label of the community assigned to each vertex.
Return Value Type Comment
long returns the total number of communities found.

Code

/*
 * Copyright (C) 2013 - 2025 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import oracle.pgx.algorithm.ControlFlow;

@GraphAlgorithm
public class LabelPropagation {
  public long labelPropagation(PgxGraph g, int maxIter, @Out VertexProperty<Long> label) {
    VertexProperty<PgxVertex> order = VertexProperty.create();
    PgxVertex p, q, tmp;
    long numVertices = g.getNumVertices();
    Scalar<Long> l = Scalar.create();
    Scalar<Boolean> converged = Scalar.create();
    int cnt = 0;

    long numberOfStepsEstimatedForCompletion = g.getNumVertices() * maxIter * 3 / 2;
    ControlFlow.setNumberOfStepsEstimatedForCompletion(numberOfStepsEstimatedForCompletion);

    g.getVertices().forSequential(n -> {
      label.set(n, l.get());
      order.set(n, n);
      l.set(l.get() + 1);
    });

    do {
      converged.set(false);
      l.set(0L);
      do {
        p = g.getRandomVertex();
        q = g.getRandomVertex();
        tmp = order.get(p);
        order.set(p, order.get(q));
        order.set(q, tmp);
        l.increment();
      } while (l.get() < numVertices / 2);

      g.getVertices().forEach(n -> {
        PgxMap<Long, Long> hist = PgxMap.create();
        PgxVertex z = order.get(n);

        z.getOutNeighbors().forSequential(w ->
            hist.set(label.get(w), hist.get(label.get(w)) + 1)
        );

        z.getInNeighbors().forSequential(w ->
            hist.set(label.get(w), hist.get(label.get(w)) + 1)
        );

        if (hist.get(label.get(z)) < hist.get(hist.getKeyForMaxValue())) {
          label.set(z, hist.getKeyForMaxValue());
          converged.reduceOr(true);
        }
      });

      cnt++;
    } while (converged.get() && cnt < maxIter);

    return relabelingCommunities(g, label);
  }

  private long relabelingCommunities(PgxGraph g, @Out VertexProperty<Long> label) {
    Scalar<Long> l = Scalar.create(-1L);
    PgxMap<Long, Long> mapping = PgxMap.create();

    g.getVertices().forSequential(n -> {
      if (mapping.containsKey(label.get(n))) {
        label.set(n, mapping.get(label.get(n)));
      } else {
        mapping.set(label.get(n), l.get());
        label.set(n, l.get());
        l.increment();
      }
    });

    return l.get();
  }
}