PGX 21.1.1 has two different algorithms to compute closeness centrality.
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.
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. |
/* * 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; 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; } }
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.
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. |
/* * 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; 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}; } }