Degree Centrality in Oracle Graph (SQL/PGQ)

Betweenness centrality measures the likelihood of a node being on the shortest paths between any two other nodes. This metric effectively identifies "bridge" nodes that facilitate connectivity between different parts of a graph. This algorithm assigns a score to each node- higher scores indicating nodes that exert greater influence over the flow and connectivity of the network.

 In this blogpost we will show examples of running the Betweenness Centrality algorithm on a concrete graph. The intention is to illustrate what the results look like and to provide a guide in how to make use of the algorithm in a real setting. We will do this on a small social network graph of a handful nodes connected in a particular pattern. The example graph looks like this:

 

We will run the Betweenness Centrality algorithm on this node and compute the Node. Can you guess which node will score the highest. Yes, in this case it is easy to visually inspect and guestimate. However in a large graph this will not be possible without the use of some algorithm.

Let's start by generating some sample data:

 

create table users (user_id int, user_name varchar(256));
create table knows (user_id_from int, user_id_to int, relationship varchar(256));

insert into users values (1, 'Fatima')
  , (2, 'Uroosa')
  , (3, 'Hannah')
  , (4, 'Maryam')
  , (5, 'Zainab')
  , (6, 'Urwa')
  , (7, 'Zoha');


insert into knows values (1, 2, 'knows')
  , (1, 5, 'knows')
  , (3, 1, 'knows')
  , (4, 3, 'knows')
  , (4, 6, 'knows')
  , (6, 5, 'knows')
;

Next create a Property Graph to define the relationships in the Social Network

CREATE OR REPLACE PROPERTY GRAPH social_graph
  VERTEX TABLES (
    users KEY (user_id) PROPERTIES ARE ALL COLUMNS
  )
  EDGE TABLES ( 
    knows
      key (user_id_from, user_id_to) 
      SOURCE KEY (user_id_from) REFERENCES users(user_id)
      DESTINATION KEY(user_id_to) REFERENCES users(user_id)
      PROPERTIES ARE ALL COLUMNS
    
);

We can query the the Property Graph as follows:

SELECT distinct 
   *
FROM GRAPH_TABLE (
       social_graph
       MATCH   (user_id_from  IS users) - [e_path is knows] -> (user_id_to is users)
       COLUMNS (
               user_id_from.user_name  as user_name_a
               , user_id_to.user_name  as user_name_b
               , vertex_id(user_id_from) as v1
               , vertex_id(user_id_to) as v2
               , edge_id(e_path) as e1

        )
) --as recommendations
;

   Next let's run the Betweenness Centrality on this Network Graph

print(session)
graph = session.read_graph_by_name("SOCIAL_GRAPH", "pg_sql")
print(graph)
analyst.vertex_betweenness_centrality(graph)
graph.query_pgql("""
SELECT 
  a.user_name
  , a.betwenness
FROM MATCH (a)
""").print()


+-------------------------+
| user_name | betweenness |
+-------------------------+
| Fatima    | 3.0         |
| Uroosa    | 0.0         |
| Hannah    | 2.0         |
| Maryam    | 0.0         |
| Zainab    | 0.0         |
| Urwa      | 1.0         |
| Zoha      | 0.0         |
+-------------------------+
 

We note that the 'Fatima' node has the highest score, followed by the 'Hannah' node. Studying the example graph we can see that these nodes are in bottleneck positions in the graph. The 'Fatima' node connects the 'Uroosa' nodes to all other nodes, which increases its score. In particular, the shortest path from 'Uroosa' to any other reachable node passes through 'Fatima'. 

Conversely, there are no shortest paths that pass through either of the nodes 'Uroosa', 'Maryam', or 'Zainab' which causes their betweenness centrality score to be zero.