PGX 21.1.1
Documentation

# Closeness Centrality Algorithms

PGX 21.1.1 has two different algorithms to compute closeness centrality.

## Closeness Centrality (Unit Length)

##### Categoryranking and walkingAlgorithm IDpgx_builtin_k4a_closeness_centrality_unit_lengthTime ComplexityO(V * E) with V = number of vertices, E = number of edgesSpace RequirementO(V) with V = number of verticesJavadocAnalyst#closenessCentralityUnitLength(PgxGraph graph) Analyst#closenessCentralityUnitLength(PgxGraph graph, VertexProperty cc)

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 vertexProp 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

```/*
*/
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();
});

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;
}
}
}
```
```/*
*/
procedure closeness_centrality(graph G; vertexProp<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 / (double) levelSum;
}
}

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

## Closeness Centrality (with weights)

##### Categoryranking and walkingAlgorithm IDpgx_builtin_k4b_closeness_centrality_double_lengthTime ComplexityO(V * E * d) with E = number of edges, V = number of vertices, d = diameter of the graphSpace RequirementO(5 * V) with V = number of verticesJavadocAnalyst#closenessCentralityDoubleLength(PgxGraph graph, EdgeProperty cost) Analyst#closenessCentralityDoubleLength(PgxGraph graph, EdgeProperty cost, VertexProperty cc)

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 vertexProp 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

```/*
*/
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);
}
}
}
```
```/*
*/

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

vertexProp<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; vertexProp<double> dist) {

vertexProp<bool> updated;
vertexProp<bool> updated_nxt;
vertexProp<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};
}
}
```