Local Clustering Coefficient

Overview

The Local Clustering Coefficient algorithm calculates the density of connection among the immediate neighbors of a node. It quantifies the ratio of actual connections among the neighbors to the maximum possible connections.

The local clustering coefficient provides insights into the cohesion of a node's ego network. In the context of a social network, the local clustering coefficient helps understand the degree of interconnectedness among an individual's friends or acquaintances. A high local clustering coefficient suggests that the person's friends are likely to be connected to each other, indicating the presence of a closely-knit social group, such as a family. Conversely, a low local clustering coefficient indicates a more dispersed or loosely interconnected ego network, where the person's friends do not have strong connections with each other.

Concepts

Local Clustering Coefficient

Mathematically, the local clustering coefficient of a node in an undirected graph is calculated as the ratio of the number of connected neighbor pairs to the total number of possible neighbor pairs:

where n is the number of nodes contained in the 1-hop neighborhood of node v (denoted as N(v)), i and j are any two distinct nodes within N(v), δ(i,j) is equal to 1 if i and j are connected, and 0 otherwise.

In this example, the local clustering coefficient of the red node is 1/(5*4/2) = 0.1.

Considerations

• The Local Clustering Coefficient algorithm ignores the direction of edges but calculates them as undirected edges.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
  knows ()-[]->()
};
INSERT (Lee:default {_id: "Lee"}),
       (Choi:default {_id: "Choi"}),
       (Mia:default {_id: "Mia"}),
       (Fiona:default {_id: "Fiona"}),
       (Chang:default {_id: "Chang"}),
       (John:default {_id: "John"}),
       (Park:default {_id: "Park"}),
       (Choi)-[:knows]->(Park),
       (Choi)-[:knows]->(Lee),
       (Park)-[:knows]->(Lee),
       (Park)-[:knows]->(Mia),
       (Lee)-[:knows]->(Mia),
       (Mia)-[:knows]->(Fiona),
       (Fiona)-[:knows]->(Lee),
       (Lee)-[:knows]->(Chang),
       (Lee)-[:knows]->(John),
       (John)-[:knows]->(Fiona);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: clustering_coefficient

File Writeback

GQLUQL
CALL algo.clustering_coefficient.write("my_hdc_graph", {
  ids: ["Lee", "Choi"],
  return_id_uuid: "id"
}, {
  file: {
    filename: "lcc"
  }
})

Result:

File: lcc
_id,clce_centrality
Lee,0.266667
Choi,1

DB Writeback

Writes the clce_centrality values from the results to the specified node property. The property type is float.

GQLUQL
CALL algo.clustering_coefficient.write("my_hdc_graph", {}, {
  db: {
    property: "lcc"
  }
})

Full Return

GQLUQL
CALL algo.clustering_coefficient.run("my_hdc_graph", {
  return_id_uuid: "id",
  order: "desc"
}) YIELD r
RETURN r

Result:

Stream Return

GQLUQL
CALL algo.clustering_coefficient.stream("my_hdc_graph", {}) YIELD r
FILTER r.clce_centrality = 1 
RETURN count(r)

Result: 2