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_coefficientComputes the clustering coefficient for each node.
average_clustering_coefficientComputes 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
vG:nodeA node in G.
valFloatThe 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[2]
//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