2.1.0
User Documentation for Apache MADlib
Closeness

The Closeness function returns various closeness centrality measures and the k-degree for given subset of vertices. The closeness measures are the inverse of the sum, the inverse of the average, and the sum of inverses of the shortest distances to all reachable target vertices (excluding the source vertex).

Note
The closeness measures require a valid output from a prior APSP run - both the APSP table and the associated output summary table. APSP is a computationally expensive algorithm because it finds the shortest path between all nodes in the graph. The worst case run-time for this implementation is O(V^2 E) where V is the number of vertices and E is the number of edges. In practice, run-time will be generally be much less than this, depending on the graph.

Closeness
graph_closeness( apsp_table,
                 output_table,
                 vertex_filter_expr
               )

Arguments

apsp_table

TEXT. Name of the output table generated by a prior run of all pairs shortest path (APSP).

out_table

TEXT. Name of the table to store the closeness measures. It contains a row for every vertex of every group and have the following columns (in addition to the grouping columns):

  • inverse_sum_dist: Inverse of the sum of shortest distances to all reachable vertices.
  • inverse_average_dist: Inverse of the average of shortest distances to all reachable vertices.
  • sum_inverse_dist: Sum of the inverse of shortest distances to all reachable vertices.
  • k_degree: Total number of reachable vertices.

vertex_filter_expr (optional)

TEXT, default = NULL. Valid PostgreSQL expression that describes the vertices to generate closeness measures for. If this parameter is not specified, closeness measures are generated for all vertices in the apsp table. You can think of this input parameter as being like a WHERE clause.

Some example inputs:

  • If you want a short list of vertices, say 1, 2 and 3:
    vertex_id IN (1, 2, 3)
  • If you want a range of vertices between 1000 and 2000:
    vertix_id BETWEEN 1000 AND 2000
  • If you want a set of vertices from a separate table satisfying to a condition
    EXISTS (SELECT vertex_id FROM vertices_of_interest
                 WHERE vertex_id > 5000 AND condition = 'xyz')
    

Examples
  1. Create vertex and edge tables to represent the graph:
    DROP TABLE IF EXISTS vertex, edge;
    CREATE TABLE vertex(
            id INTEGER,
            name TEXT
            );
    CREATE TABLE edge(
            src_id INTEGER,
            dest_id INTEGER,
            edge_weight FLOAT8
            );
    INSERT INTO vertex VALUES
    (0, 'A'),
    (1, 'B'),
    (2, 'C'),
    (3, 'D'),
    (4, 'E'),
    (5, 'F'),
    (6, 'G'),
    (7, 'H');
    INSERT INTO edge VALUES
    (0, 1, 1.0),
    (0, 2, 1.0),
    (0, 4, 10.0),
    (1, 2, 2.0),
    (1, 3, 10.0),
    (2, 3, 1.0),
    (2, 5, 1.0),
    (2, 6, 3.0),
    (3, 0, 1.0),
    (4, 0, -2.0),
    (5, 6, 1.0),
    (6, 7, 1.0);
    
  2. Calculate the all-pair shortest paths:
    DROP TABLE IF EXISTS out_apsp, out_apsp_summary;
    SELECT madlib.graph_apsp('vertex',      -- Vertex table
                             'id',          -- Vertix id column (NULL means use default naming)
                             'edge',        -- Edge table
                             'src=src_id, dest=dest_id, weight=edge_weight',
                                            -- Edge arguments (NULL means use default naming)
                             'out_apsp');        -- Output table of shortest paths
    
  3. Compute the closeness measure for all nodes:
    DROP TABLE IF EXISTS out_closeness;
    SELECT madlib.graph_closeness('out_apsp', 'out_closeness');
    SELECT * FROM out_closeness;
    
     src_id |  inverse_sum_dist  | inverse_avg_dist  | sum_inverse_dist | k_degree
    --------+--------------------+-------------------+------------------+----------
          1 | 0.0285714285714286 |               0.2 | 1.93809523809524 |        7
          3 | 0.0357142857142857 |              0.25 | 2.87424242424242 |        7
          4 |                 -1 |                -7 |               -1 |        7
          0 | 0.0434782608695652 | 0.304347826086957 | 3.68333333333333 |        7
          6 |                  1 |                 1 |                1 |        1
          2 | 0.0416666666666667 | 0.291666666666667 |             3.75 |        7
          5 |  0.333333333333333 | 0.666666666666667 |              1.5 |        2
          7 |             [NULL] |            [NULL] |                0 |        0
    (8 rows)
    
  4. Create a graph with 2 groups and find APSP for each group:
    DROP TABLE IF EXISTS edge_gr;
    CREATE TABLE edge_gr AS
    (
      SELECT *, 0 AS grp FROM edge
      UNION
      SELECT *, 1 AS grp FROM edge WHERE src_id < 6 AND dest_id < 6
    );
    INSERT INTO edge_gr VALUES
    (4,5,-20,1);
    
  5. Find APSP for all groups:
    DROP TABLE IF EXISTS out_gr, out_gr_summary;
    SELECT madlib.graph_apsp(
                             'vertex',      -- Vertex table
                             NULL,          -- Vertex id column (NULL means use default naming)
                             'edge_gr',     -- Edge table
                             'src=src_id, dest=dest_id, weight=edge_weight',
                             'out_gr',      -- Output table of shortest paths
                             'grp'          -- Grouping columns
    );
    
  6. Compute closeness measure for vertex 0 to vertex 5 in every group
    DROP TABLE IF EXISTS out_gr_path;
    SELECT madlib.graph_closeness('out_gr', 'out_gr_closeness', 'src_id >= 0 and src_id <=5');
    SELECT * FROM out_gr_closeness ORDER BY grp;
    
     grp | src_id |  inverse_sum_dist   |  inverse_avg_dist  | sum_inverse_dist  | k_degree
    ----—+-------—+--------------------—+-------------------—+------------------—+---------—
       0 |      0 |  0.0434782608695652 |  0.304347826086957 |  3.68333333333333 |        7
       0 |      5 |   0.333333333333333 |  0.666666666666667 |               1.5 |        2
       0 |      4 |                  -1 |                 -7 |                -1 |        7
       0 |      3 |  0.0357142857142857 |               0.25 |  2.87424242424242 |        7
       0 |      1 |  0.0285714285714286 |                0.2 |  1.93809523809524 |        7
       0 |      2 |  0.0416666666666667 |  0.291666666666667 |              3.75 |        7
       1 |      3 |   0.142857142857143 |  0.714285714285714 |  1.97979797979798 |        5
       1 |      5 |              [NULL] |             [NULL] |                 0 |        0
       1 |      0 |                0.25 |               1.25 |               2.5 |        5
       1 |      1 |  0.0588235294117647 |  0.294117647058824 | 0.988095238095238 |        5
       1 |      2 |                 0.1 |                0.5 |  1.79166666666667 |        5
       1 |      4 | -0.0416666666666667 | -0.208333333333333 |             -2.55 |        5
    (12 rows)