PGX 20.1.1
Documentation

Closeness Centrality Algorithms

PGX 20.1.1 has two different algorithms to compute closeness centrality.

Closeness Centrality (Unit Length)

Category ranking and walking

Algorithm ID pgx_builtin_k4a_closeness_centrality_unit_length

Time Complexity O(V * E) with V = number of vertices, E = number of edges

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

Javadoc

The Closeness Centrality of a node V is the reciprocal of the sum of all the distances from the possible shortests paths starting from V. Thus the higher the centrality value of V, the closer it is to all the other vertices in the graph. This implementation is meant for undirected graphs.

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
cc nodeProp node property holding the closeness centrality value for each node.
Return Value Type Comment
bool returns true if the graph is connected, false otherwise.

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.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;

@GraphAlgorithm
public class ClosenessCentrality {
  public boolean closenessCentrality(PgxGraph g, @Out VertexProperty<Double> cc) {
    Scalar<Boolean> connected = Scalar.create(true);

    g.getVertices().forEach(s -> {
      Scalar<Integer> foundNodes = Scalar.create(0);
      Scalar<Integer> levelSum = Scalar.create(0);

      inBFS(g, s).forward(v -> {
        foundNodes.increment();
        levelSum.reduceAdd(currentLevel());
      });

      if (foundNodes.get() != g.getNumVertices() || levelSum.get() == 0) {
        connected.reduceAnd(false);
      } else {
        cc.set(s, 1.0 / levelSum.get());
      }
    });

    if (connected.get()) {
      return true;
    } else {
      cc.setAll(0.0);

      return false;
    }
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure closeness_centrality(graph G; nodeProp<double> cc) : bool {
  bool connected = true;

  foreach (s : G.nodes) {
    long foundNodes = 0;
    long levelSum;

    inBFS (v: G.nodes from s) {
      foundNodes++;
      levelSum += currentBFSLevel();
    }

    if (foundNodes != G.numNodes() || levelSum == 0) {
      connected &= false;
    } else {
      s.cc = 1.0 / levelSum;
    }
  }

  if (connected) {
    return true;
  } else {
    G.cc = 0.0; // disconnected graph
    return false;
  }
}

Closeness Centrality (with weights)

Category ranking and walking

Algorithm ID pgx_builtin_k4b_closeness_centrality_double_length

Time Complexity O(V * E * d) with E = number of edges, V = number of vertices, d = diameter of the graph

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

Javadoc

This variant of Closeness Centrality takes into account the weights from the edges when computing the reciprocal of the sum of all the distances from the possible shortests paths starting from the vertex V, for every vertex in the graph. The weights of the edges must be positive values greater than 0.

Signature

Input Argument Type Comment
G graph
weight edgeProp edge property holding the weight of each edge in the graph.
Output Argument Type Comment
cc nodeProp vertex property holding the closeness centrality value for each vertex.
Return Value Type Comment
bool boolean flag that checks if the graph is connected.

Code

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

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
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 static oracle.pgx.algorithm.Reduction.updateMinValue;
import static java.lang.Double.POSITIVE_INFINITY;

@GraphAlgorithm
public class ClosenessCentralityDoubleLength {
  public boolean closenessCentralityDoubleLength(PgxGraph g, EdgeProperty<Double> weight,
      @Out VertexProperty<Double> cc) {
    VertexProperty<Double> dist = VertexProperty.create(POSITIVE_INFINITY);

    Scalar<Boolean> disconnected = Scalar.create(false);

    // for every vertex in G
    g.getVertices().forSequential(root -> {
      // Run Bellman-Ford Algorithm
      bellmanFord(g, root, weight, dist);

      // Update cc
      boolean b = g.getVertices().anyMatch(v -> dist.get(v) == POSITIVE_INFINITY);
      double levelSum = g.getVertices().sum(dist);
      dist.setAll(POSITIVE_INFINITY);

      if (b) {
        cc.setAll(0d); // disconnected graph
        disconnected.set(true);
      } else {
        cc.set(root, 1.0 / levelSum);
      }
    });

    return !disconnected.get();
  }

  void bellmanFord(PgxGraph g, PgxVertex root, EdgeProperty<Double> weight, @Out VertexProperty<Double> dist) {
    VertexProperty<Boolean> updated = VertexProperty.create();
    VertexProperty<Boolean> updatedNxt = VertexProperty.create();
    VertexProperty<Double> distNxt = VertexProperty.create();

    dist.setAll(v -> (v == root) ? 0d : POSITIVE_INFINITY);
    updated.setAll(v -> v == root);
    distNxt.setAll(dist::get);
    updatedNxt.setAll(updated::get);
    boolean done = false;

    while (!done) {
      g.getVertices().filter(updated).forEach(n -> n.getNeighbors().forEach(s -> {
        PgxEdge e = s.edge(); // the edge to s
        // updatedNxt becomes true only if distNxt is
        // actually updated
        updateMinValue(s, distNxt, dist.get(n) + weight.get(e)).andUpdate(s, updatedNxt, true);
      }));

      dist.setAll(distNxt::get);
      updated.setAll(updatedNxt::get);
      updatedNxt.setAll(false);

      done = !g.getVertices().anyMatch(updated::get);
    }
  }
}

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

procedure closeness_centrality_double_length(graph G, edgeProp<double> weight; nodeProp<double> cc) : bool {

  nodeProp<double> dist;
  G.dist = INF;

  // for every vertex in G
  for (root: G.nodes) {

    // Run Bell-man Ford Algorithm
    bellman_ford(G, root, weight, dist);

    // Update cc
    bool b = any (v: G.nodes) {v.dist == INF};
    double levelSum = sum (v: G.nodes) {v.dist};
    G.dist = INF;

    if (b) {
      G.cc = 0.0;     // disconnected graph
      return false;
    } else {
      root.cc = 1.0 / (double) levelSum;
    }
  }

  return true;
}

local bellman_ford(graph G, node root, edgeProp<double> weight; nodeProp<double> dist) {

  nodeProp<bool> updated;
  nodeProp<bool> updated_nxt;
  nodeProp<double> dist_nxt;

  G.dist = (_ == root) ? 0 : +INF;
  G.updated = (_ == root) ? true : false;
  G.dist_nxt = _.dist;
  G.updated_nxt = _.updated;
  bool done = false;

  while (!done) {
    done = true;

    foreach (n: G.nodes) (n.updated) {
      foreach (s: n.nbrs) {
        edge e = s.edge(); // the edge to s
        // updated_nxt becomes true only if dist_nxt is
        // actually updated
        <s.dist_nxt; s.updated_nxt> min= <n.dist + e.weight; true>;
      }
    }

    G.dist = _.dist_nxt;
    G.updated = _.updated_nxt;
    G.updated_nxt = false;
    done = !any (n: G.nodes) {n.updated};
  }
}