# Graph Library (`graphlib`

) — Communities Algorithms Extension

A library extension to `graphlib`

containing various communities algorithms.

## Module: rel:graphlib

View source`rel:graphlib[G]`

This section of the graph library supports the following community detection algorithms:

Measure | Description |
---|---|

`triangle_community` | A mapping from nodes to community labels via the `K` -clique algorithm with `K = 3` . |

`label_propagation` | A mapping from nodes to community labels via the label propagation algorithm. |

### triangle_community

View source```
triangle_community
triangle_community[v]
triangle_community(v, community_label)
```

`triangle_community`

uses the K-clique algorithm (with `K = 3`

) to
partition nodes into communities and assigns to each node a community index.
`triangle_community[v]`

computes the community index for the node `v`

.
`triangle_community(v, community_label)`

checks if node `v`

is assigned
to community with index `community_label`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | No | |

Weighted | Yes | Ignores weights. |

Parameters

Parameter | Type | Description |
---|---|---|

`v` | `G:node` | A node in `G` . |

`community_label` | `Int` | An integer label representing to community to which node `v` is assigned. |

Explanation

`triangle_community`

finds K-clique communities (with `K = 3`

) using the
percolation method (opens in a new tab).
A triangle community is the union of nodes of all triangles that can be reached
from one another by adjacent triangles — that is, triangles that share exactly
two nodes. For a given undirected graph `G`

, the algorithm works as follows:
First, all triangles in `G`

are enumerated and assigned a unique label, each of which
becomes a node in a new graph called the **clique-graph** of `G`

, where
two nodes in this new graph are connected by an edge if the
corresponding triangles share exactly two nodes, i.e., the corresponding triangles
are adjacent in `G`

. Next, the connected components of the clique-graph of `G`

are
computed and then assigned community label. Finally, each node in the original graph
is assigned the community label of the triangle to which it belongs. Nodes that are
not contained in any triangle are not assigned a community label. Note, this algorithm
is not supported for directed graphs since adjacency is not defined for directed triangles.

Examples

Compute triangle community labels for each node in an undirected graph:

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

Compute the community label of a given node:

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

Check if a node belongs to a given community:

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

### label_propagation

View source```
label_propagation
label_propagation[v]
label_propagation(v, label)
```

`label_propagation`

is a mapping from nodes to labels via
the synchronous label propagation algorithm. `label_propagation[v]`

is the label of node `v`

. `label_propagation(v, label)`

is true if node `v`

has label `label`

.

Supported Graph Types

Graph Type | Supported | Notes |
---|---|---|

Undirected | Yes | |

Directed | Yes | |

Weighted | Yes |

Parameters

Parameter | Type | Description |
---|---|---|

`v` | `G:node` | A node in `G` . |

`label` | `Int` | An integer label representing the community to which node `v` is assigned. |

Explanation

The Label Propagation Algorithm (LPA) identifies communities within graphs through iterative steps. In each iteration, nodes adopt the label that is most common among their neighbors. For unweighted graphs, this is determined by the most frequently occurring label. In the context of weighted graphs, the sum of edge weights corresponding to each label is considered, with nodes adopting the label with the highest total weight. For directed graphs, the algorithm relies on out-neighbor labels. Ties, whether in label frequency (unweighted) or summed weight (weighted), are resolved deterministically. The algorithm terminates when node labels stabilize or upon reaching a preset maximum number of iterations.

Examples

Compute labels for each node in an undirected graph:

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

Compute the label of a node:

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

Check if a node has a label:

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

Compute labels for a weighted graph:

```
def W = {
(1, 2, 1.0);
(1, 3, 1.0);
(2, 3, 1.0);
(1, 4, 0.5);
(4, 5, 1.0);
(4, 6, 1.0);
(5, 6, 1.0)
}
def my_graph = create_graph[{(:weight, W)}, {(:is_weighted)}]
@inline def mylib = rel:graphlib[my_graph]
def output = mylib:label_propagation
//output> (1, 3)
// (2, 3)
// (3, 3)
// (4, 6)
// (5, 6)
// (6, 6)
```