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 Complexity O(N*E)    Space Requirement O(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

/*
* Copyright (C) 2013 - 2015 Oracle and/or its affiliates. All rights reserved.
*/
/*
* 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 Complexity O(N*E*d) [d = path-length diameter of graph]    Space Requirement O(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

/*
* Copyright (C) 2013 - 2015 Oracle and/or its affiliates. All rights reserved.
*/
/*
 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;
}