Library: graphlib (clustering)

EXPERIMENTAL: These features are experimental and should not be used in production systems.

# Graph Library (`graphlib`) — Clustering Algorithms Extension

A library extension to `graphlib` containing various clustering algorithms.

## Module: rel:graphlib

View source
``rel:graphlib[G]``

This section of the graph library supports the following clustering algorithms:

MeasureDescription
`local_clustering_coefficient`Computes the clustering coefficient for each node.
`average_clustering_coefficient`Computes the average clustering coefficient of all nodes.

### local_clustering_coefficient

View source
``````local_clustering_coefficient
local_clustering_coefficient[v]
local_clustering_coefficient(v, val)``````

`local_clustering_coefficient` computes the local clustering coefficient values for each node in the graph. `local_clustering_coefficient[v]` computes the local clustering coefficient of the node `v` in the graph. `local_clustering_coefficient(v, val)` checks if `val` is the local clustering coefficient of node `v` in the graph. Currently, only undirected graphs are supported.

Parameters

ParameterTypeDescription
`v``G:node`A node in `G`.
`val``Float`The Local Clustering Coefficient of node `v`.

Explanation

`local_clustering_coefficient` computes the local clustering coefficient for each node in the graph. The local clustering coefficient is a measure used for a single node in a network. It quantifies how close the node’s neighbors are to being a clique — that is, how interconnected they are. The coefficient ranges from 0 to 1, where 0 means none of the neighbors are connected and 1 means all neighbors are directly connected to each other. The formal definition of the local clustering coefficient (C) for a node (v) can be given as:

``            C(v) = (2 * num_edges) / (degree(v) * (degree(v) - 1))``

Here, `num_edges` represents the number of edges between the neighbors of node `v` and `degree(v)` represents the degree of the node, i.e., the number of edges connected to the node.

Examples

Compute the local clustering coefficient each node in an undirected graph:

``````def my_edges = {(1, 2); (1, 3); (2, 3); (3, 4); (4, 5); (2, 4); (3, 5)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

// Compute the local clustering coefficient for each node in the graph.
def output = my_graphlib:local_clustering_coefficient
//output> (1, 1.0)
//        (2, 0.6666666666666666)
//        (3, 0.5)
//        (4, 0.6666666666666666)
//        (5, 1.0)``````

Compute the local clustering coefficient of a node in an undirected graph:

``````def my_edges = {(1, 2); (1, 3); (2, 3); (3, 4); (4, 5); (2, 4); (3, 5)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

// Compute the local clustering coefficient for each node in the graph.
def output = my_graphlib:local_clustering_coefficient
//output> 0.6666666666666666``````

### average_clustering_coefficient

View source
``average_clustering_coefficient``

`average_clustering_coefficient` computes the average of the local clustering coefficients of each node in a graph.

Explanation

The average clustering coefficient measures the degree to which nodes in the graph tend to cluster and provides an overall indication of the clustering in the graph.

Examples

Compute the average clustering coefficient for a undirected graph:

``````def my_edges = {(1, 2); (1, 3); (1, 4); (1, 5); (2, 3)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

// Compute the average clustering coefficient for the graph.
def output = my_graphlib:average_clustering_coefficient
//output> 0.4333333333333334``````

`local_clustering_coefficient`