PGX 21.1.1
Documentation

Local Clustering Coefficient (LCC)

Category structure evaluation

Algorithm ID pgx_builtin_s13_local_clustering_coefficient

Time Complexity O(V ^ 2) with V = number of vertices

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

Javadoc

The LCC of a vertex V is the fraction of connections between each pair of neighbors of V, i.e. the fraction of existing triangles from all the possible triangles involving V and every other pair of neighbor vertices of V. This implementation is intended for undirected graphs. Nodes with a degree smaller than 2 will be assigned a LCC value of 0.

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
lcc vertexProp vertex property holding the lcc value for each vertex.

Code

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

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

@GraphAlgorithm
public class ClusteringCoefficient {
  public void localClusteringCoefficient(PgxGraph g, @Out VertexProperty<Double> lcc) {
    lcc.setAll(0d);

    g.getVertices().filter(v -> v.getOutDegree() >= 2).forEach(v -> {
      Scalar<Long> lcount = Scalar.create(0L);
      v.getNeighbors().forEach(m ->
          v.getNeighbors().filter(m::lessThan).forEach(n -> {
            if (m.hasEdgeTo(n)) {
              lcount.increment();
            }
          })
      );
      lcc.set(v, (2.0 * lcount.get()) / ((double) v.getOutDegree() * (v.getOutDegree() - 1)));
    });
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure local_clustering_coefficient(graph G; vertexProp<double> lcc) {

  G.lcc = 0;

  foreach (v: G.nodes) (v.degree() >= 2) {
    long lcount = 0;
    foreach (m: v.nbrs) {
      foreach (n: v.nbrs) (m < n) {
        if (m.hasEdgeTo(n)) {
          lcount++;
        }
      }
    }
    v.lcc = (2.0 * lcount) / ((double) v.degree() * (v.degree() - 1));
  }
}