Local Clustering Coefficient

Compute the per-node local clustering coefficient and triangle count

Category: community-detection

Syntax

SELECT * FROM graph_lcc(table_name)

Description

The local clustering coefficient (Watts and Strogatz 1998) measures how tightly a node's neighbourhood is interconnected. For a node v with deg(v) distinct undirected neighbours, the engine computes LCC(v) = 2 * triangles(v) / (deg(v) * (deg(v) - 1)), the fraction of neighbour pairs of v that are themselves connected. The result is bounded in [0.0, 1.0]: 1.0 means every neighbour of v is connected to every other neighbour (a complete subgraph on v's neighbourhood); 0.0 means no neighbour pair is connected. Nodes with deg(v) < 2 have no neighbour pairs, so LCC is defined as 0.0 by convention. This matches Neo4j GDS gds.localClusteringCoefficient. The function loads edge data from a registered Delta table as an undirected graph in Compressed Sparse Row (CSR) format. The CPU implementation computes a global triangle count first (per-edge intersection of endpoint neighbour sets), then divides by deg * (deg - 1) / 2. For directed inputs, the neighbour set is taken as the union of out- and in-neighbours so the LCC matches an undirected interpretation, which is what GDS does. Column names for source and target are auto-detected from standard conventions (src/source/src_id, dst/target/dst_id). Edge weights are ignored. The GPU implementation uses the Chiba-Nishizeki degree-ordered DAG to avoid the O(deg^2) per-vertex enumeration cost that the naive shape would incur on hubs. Each triangle is oriented so that the vertex with the smallest (degree, id) tuple owns the enumeration step; the other two vertices are reached by a two-pointer sorted intersection of their adjacency slices. Each triangle is therefore visited exactly once, and the per-thread cost is bounded by min-degree rather than degree, which prevents a single celebrity hub from serialising the whole pass. Triangle counts are accumulated as atomic<u32> on device, and a separate normalise pass divides by deg * (deg - 1) on the GPU before readback. The dispatch also collapses parallel edges per row on the host before upload (CSR's within-bucket sort guarantees duplicates cluster contiguously), so the simple-graph contract that LCC requires holds regardless of whether the input edge table contains duplicate (src, dst) pairs. A warning is logged when any duplicates are dropped. The per-vertex u32 triangle counter is safe up to a post-dedup degree of 92681 (a hub with a complete neighbourhood at that degree saturates u32). The dispatch emits a tracing warning above that threshold; WGSL has no portable atomic<u64> so widening is not possible today, and clustering results on adversarial hubs near that bound should be treated as suspect. The graph cache (256 MB default budget, LRU eviction, 10-minute idle timeout) retains the CSR topology across repeated invocations.

Parameters

Name	Type	Description
`table_name`		Specify the name of the registered Delta table containing edge data. The table must include source and target columns (auto-detected as src/source/src_id and dst/target/dst_id). The graph is loaded as undirected for triangle enumeration. Edge weights are ignored: clustering coefficient is a topological quantity.

Examples

CREATE TABLE social_network AS
SELECT * FROM VALUES
  (1, 2, 1.0),
  (2, 3, 1.0),
  (3, 1, 1.0),
  (3, 4, 1.0),
  (4, 5, 1.0),
  (5, 3, 1.0)
AS t(src, dst, weight);

SELECT * FROM graph_lcc('social_network')
ORDER BY coefficient DESC;

SELECT node_id, triangle_count, coefficient
FROM graph_lcc('social_network')
WHERE coefficient >= 0.5
ORDER BY coefficient DESC;

SELECT AVG(coefficient) AS avg_clustering
FROM graph_lcc('social_network');

SELECT l.node_id, l.coefficient, d.total_degree
FROM graph_lcc('social_network') l
JOIN graph_degree('social_network') d
  ON l.node_id = d.node_id
WHERE l.coefficient = 0.0
ORDER BY d.total_degree;

Pitfalls

Nodes with degree below 2 have LCC = 0.0 by convention, not because their neighbourhood is sparsely connected but because no neighbour pairs exist to evaluate. Filter or join against graph_degree before averaging LCC values across the graph if low-degree nodes would bias the result.
The graph is treated as undirected. Directed reciprocity (A follows B, B does not follow A) is collapsed; the LCC matches gds.localClusteringCoefficient, which is the conventional reading. If directed triangles are required, use a manual SQL join over the edge table instead.
Edge weights are ignored. LCC is a purely topological measure: two graphs with identical adjacency but different weights produce identical coefficients. If a weighted clustering measure is needed, compose triangle_count with edge weights yourself.
Parallel edges (duplicate src, dst rows) and self-loops corrupt the naive triangle count. The GPU path collapses consecutive duplicate destinations after the per-row sort and logs a tracing warning when any are dropped. The CPU path inherits the behaviour of graph_triangle_count for multigraphs; if your edge table contains duplicates and you want the simple-graph reading, deduplicate before invocation.
Average LCC across the whole graph is a well-defined quantity but is not the same as the graph's global clustering coefficient (3 * triangles / connected_triples). Both are useful; do not substitute one for the other.
Hub vertices with degree above ~92681 and a near-complete neighbourhood can in principle overflow the GPU's atomic<u32> triangle counter. The dispatch warns in logs when max post-dedup degree exceeds this threshold; treat coefficients on those vertices as suspect on GPU runs. The CPU path uses 64-bit accumulators and is not subject to this limit.
GPU acceleration excels on dense neighbourhoods but falls back to CPU when the adjacency structure exceeds device memory. Silent fallback means very large graphs may not actually use the GPU; verify with EXPLAIN when GPU speedup is a requirement.