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, 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. Conversely, a low local clustering coefficient indicates a more dispersed ego network.

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.

Example Graph

GQL
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)

Parameters

Run Mode

Returns:

GQL
CALL algo.localclusteringcoefficient({
  order: "desc"
}) YIELD nodeId, coefficient, triangles, degree

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.localclusteringcoefficient.stream({direction: "in"}) YIELD nodeId, coefficient
RETURN nodeId, coefficient

Result:

Stats Mode

Returns:

GQL
CALL algo.localclusteringcoefficient.stats() YIELD nodeCount, avgCoefficient, globalClusteringCoefficient

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.localclusteringcoefficient.write({}, {
  db: {
    property: "lcc"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs