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

To create this graph:

// Runs each row separately in order in an empty graphset
create().edge_schema("knows")
insert().into(@default).nodes([{_id:"Lee"}, {_id:"Choi"}, {_id:"Mia"}, {_id:"Fiona"}, {_id:"Chang"}, {_id:"John"}, {_id:"Park"}])
insert().into(@knows).edges([{_from:"Choi", _to:"Park"}, {_from:"Choi", _to:"Lee"}, {_from:"Park", _to:"Lee"}, {_from:"Park", _to:"Mia"}, {_from:"Lee", _to:"Mia"}, {_from:"Mia", _to:"Fiona"}, {_from:"Fiona", _to:"Lee"}, {_from:"Lee", _to:"Chang"}, {_from:"Lee", _to:"John"}, {_from:"John", _to:"Fiona"}])

Creating HDC Graph

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

CALL hdc.graph.create("hdc-server-1", "hdc_lcc", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_lcc", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: clustering_coefficient

File Writeback

CALL algo.clustering_coefficient.write("hdc_lcc", {
  params: {
    ids: ["Lee", "Choi"],
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "lcc.txt"
    }
  }
})

algo(clustering_coefficient).params({
  projection: "hdc_lcc",
  ids: ["Lee", "Choi"],
  return_id_uuid: "id"
}).write({
  file: {
    filename: "lcc.txt"
  }
})

Result:

_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.

CALL algo.clustering_coefficient.write("hdc_lcc", {
  params: {},
  return_params: {
    db: {
      property: "lcc"
    }
  }
})

algo(clustering_coefficient).params({
  projection: "hdc_lcc"
}).write({
  db: {
    property: "lcc"
  }
})

Full Return

CALL algo.clustering_coefficient("hdc_lcc", {
  params: {
    return_id_uuid: "id",
    order: "desc"
  },
  return_params: {}
}) YIELD result
RETURN result

exec{
  algo(clustering_coefficient).params({
    return_id_uuid: "id",
    order: "desc"
  }) as result
  return result
} on hdc_lcc

Result:

Stream Return

CALL algo.clustering_coefficient("hdc_lcc", {
  params: {},
  return_params: {
    stream: {}
  }
}) YIELD r
FILTER r.clce_centrality = 1 
RETURN count(r)

exec{
  algo(clustering_coefficient).params().stream() as r
  where r.clce_centrality == 1
  return count(r)
} on hdc_lcc

Result: 2