PGX 20.2.2
Documentation

Label Propagation

Category community detection

Algorithm ID pgx_builtin_c1_community_detection_label_propagation

Time Complexity O(E * k) with E = number of edges, k <= maximum number of iterations

Space Requirement O(2 * V) with V = number of vertices

Javadoc


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 - 2020 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;

@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;

    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.getNeighbors().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();
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure label_propagation(graph G, int max_iter; vertexProp<long> label) : long {

  vertexProp<node> order;
  node p,q,tmp;
  long N = G.numNodes();
  long l = 0;
  bool converged;
  int cnt = 0;

  for (n: G.nodes) {
    n.label = l;
    n.order = n;
    l = l + 1;
  }

  do {
    converged = false;
    l = 0;
    do {
      p = G.pickRandom();
      q = G.pickRandom();
      tmp = p.order;
      p.order = q.order;
      q.order = tmp;
      l++;
    } while (l < N / 2);

    foreach (n: G.nodes) {

      map<long, long> hist;
      node z = n.order;

      for (w: z.nbrs) {
        hist[w.label] = hist[w.label] + 1;
      }
      for (w: z.inNbrs) {
        hist[w.label] = hist[w.label] + 1;
      }
      if (hist[z.label] < hist[hist.getMaxKey()]) {
        z.label = hist.getMaxKey();
        converged |= true;
      }
    }
    cnt++;

  } while (converged && cnt < max_iter);

  return relabeling_communities(G, label);
}

local relabeling_communities(graph G; vertexProp<long> label) : long {
  long l = 0;
  map<long, long> mapping;

  for (n: G.nodes) {
    if (mapping.hasKey(n.label)) {
      n.label = mapping[n.label];
    } else {
      mapping[n.label] = l;
      n.label = l;
      l++;
    }
  }
  return l;
}