Vertex clustering coefficient

How it works

For each node u in an undirected graph, the clustering coefficient is:

$$C_u = \frac{2T(u)}{deg(u)(deg(u)-1)}$$

Where:

• T(u) — the number of triangles passing through node u (pairs of neighbors that are also directly connected to each other)

• deg(u) — the degree of node u (number of direct neighbors)

Configure the component

PAI -name NodeDensity
    -project algo_public
    -DinputEdgeTableName=NodeDensity_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=NodeDensity_func_test_result
    -DmaxEdgeCnt=500;

Example

This example runs the Vertex Clustering Coefficient algorithm on a small graph with 7 nodes and 11 edges, then reads the results.

The graph has the following edges (each row is one edge):

Node 1 connects to 5 neighbors (nodes 2–6), but only 4 of the 10 possible pairs among those neighbors are directly connected (2–3, 3–4, 4–5, 5–6). This gives node 1 a clustering coefficient of 0.4.

Step 1: Add a SQL Script component. Deselect Use Script Mode and Whether the system adds a create table statement. Enter the following SQL statements to create the input edge table and output table.

drop table if exists NodeDensity_func_test_edge;
create table NodeDensity_func_test_edge as
select * from
(
  select '1' as flow_out_id, '2' as flow_in_id
  union all
  select '1' as flow_out_id, '3' as flow_in_id
  union all
  select '1' as flow_out_id, '4' as flow_in_id
  union all
  select '1' as flow_out_id, '5' as flow_in_id
  union all
  select '1' as flow_out_id, '6' as flow_in_id
  union all
  select '2' as flow_out_id, '3' as flow_in_id
  union all
  select '3' as flow_out_id, '4' as flow_in_id
  union all
  select '4' as flow_out_id, '5' as flow_in_id
  union all
  select '5' as flow_out_id, '6' as flow_in_id
  union all
  select '5' as flow_out_id, '7' as flow_in_id
  union all
  select '6' as flow_out_id, '7' as flow_in_id
)tmp;
drop table if exists NodeDensity_func_test_result;
create table NodeDensity_func_test_result
(
  node string,
  node_cnt bigint,
  edge_cnt bigint,
  density double,
  log_density double
);

Step 2: Add a second SQL Script component. Deselect Use Script Mode and Whether the system adds a create table statement. Enter the following PAI commands and connect the two SQL Script components.

drop table if exists ${o1};
PAI -name NodeDensity
    -project algo_public
    -DinputEdgeTableName=NodeDensity_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=${o1}
    -DmaxEdgeCnt=500;

Step 3: Click in the upper-left corner to run the pipeline.

Step 4: Right-click the SQL Script component created in Step 2 and choose View Data > SQL Script Output to view the results.

Output columns:

Nodes 2 and 7 both have a clustering coefficient of 1.0, meaning all their neighbors are directly connected to each other. Node 1 has the lowest coefficient (0.4), because only 4 of its 10 possible neighbor pairs are connected.