Graph Library (graphlib) — Communities Algorithms Extension

triangle_community

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

Parameters

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

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

Parameters

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)