PGX 1.2.0
Documentation Closeness Centrality Algorithms

PGX 1.2.0 has two different algorithms to compute closeness centrality.

Closeness Centrality (Unit Length)

Time ComplexityO(N*E)Space RequirementO(N)

Computes the closeness centrality value of each node in the graph. Note that this algorithm is only defined on strongly connected graphs.

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
CC nodeProperty node property holding the centrality value for each node. If the graph is not connected, the value for all nodes will be 0.
Return Value Type Comment
bool true if the graph is connected, false otherwise

Green-Marl Code

/*
*/
/*
* Closeness Centrality:
*    http://en.wikipedia.org/wiki/Closeness_centrality#Closeness_centrality
*
*  - The algorithm is computationally expensive. O(n*m) and should be used for small-graphs.
*  - This algorithm assumes unit value of edge cost.
*  - The value is all zero if the graph is disconnected
*
* Input:
*    G: graph
*    CC: Connected Centrality (output)
* Ouput:
*    bool - true if the graph is connected. false if disconnected.
*/
procedure closeness_centrality(G: graph; CC: nodeProp<double>) : 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 (Double Length)

Time ComplexityO(N*E*d) [d = path-length diameter of graph]Space RequirementO(N)

Computes the closeness centrality value of each node in the graph. Note that this algorithm is only defined on strongly connected graphs. This version of the algorithm uses weighted edges to compute the distance between two nodes.

Signature

Input Argument Type Comment
G graph
len edgeProperty edge property holding the edge lengths.
Output Argument Type Comment
CC nodeProperty node property holding the centrality value for each node. If the graph is not connected, the value for all nodes will be 0.
Return Value Type Comment
bool true if the graph is connected, false otherwise

Green-Marl Code

/*
*/
/*
Closeness Centrality:
http://en.wikipedia.org/wiki/Closeness_centrality#Closeness_centrality

- The algorithm is computationanlly very expensive. O(K*n*m)

- This algorithm assumes double type for edge length

- The CC value becomes all zero if the graph is disconnected

Execution:
The algorithm runs all-to-all shortest path algorithm N times.

Arguments
G: graph
CC: Connected Centrality (output)

return:
bool - true if the graph is connected. false if disconnected.

*/

procedure closeness_centrality_double_length(G: graph, len: edgeProp<double>;
CC: nodeProp<double>) : bool
{
N_P<bool> updated;
N_P<bool> updated_nxt;
N_P<double> dist;
N_P<double> dist_nxt;

G.dist = INF;

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

// Run Bell-man Ford Algorithm
{
G.dist    = (_ == root) ? 0 : +INF;
G.updated = (_ == root) ? true : false;
G.dist_nxt = _.dist;
G.updated_nxt = _.updated;
bool fin = false;

while(!fin) {
fin = true;

foreach(n: G.nodes)(n.updated) {
foreach(s: n.nbrs) {
edge(G) e = s.toEdge(); // 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.len; true>;
}
}

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

}

// Update CC
bool b  = exist(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;
}