Label Propagation Algorithm

Overview

The Label Propagation algorithm (LPA) is a community detection algorithm using label propagation. Each node is initialized with a label and at every iteration of the algorithm, each node updates its label to the one that is most prevalent among its neighbors. This iterative process allows densely connected groups of nodes to converge on a consensus labels, nodes sharing the same label then forming a community.

LPA does not optimize any specific chosen measure of community strengths, and does not require the number of communities to be predefined. Instead, it leverages the network structure to guide its progression. This simplicity enables LPA to efficiently analyze large and complex networks.

Related material of the algorithm:

• U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks (2007)

Concepts

Label

Label of a node is initialized with a specified property value, or its unique UUID.

Nodes that have the same label at the end of the algorithm indicate their affiliation to a common community.

NOTE

In LPA, all initial labels are valid and able to propagate. If there is a need to specify some labels as invalid, please contact Ultipa team for customization.

Label Propagation

In the simplest settings, at every iteration of propagation, each node updates its label to the one that the maximum numbers of its neighbors belongs to.

As the following example shows, the label of the blue node will be updated from d to c.

When considering node and edge weights, the label weight equals to the sum of the products of the corresponding node and edge weights, each node updates its label to the one with the largest weight.

As the weights of nodes and edges denoted in the example below, the label of the blue node will be updated from d to a.

Multi-label Propagation

In multi-label propagation, each node accept multiple labels during the propagation. In this case, a label probability that is proportional to its weight is given to each label of a node, while the sum of label probabilities of each node keeps as 1.

In the example below, each node keeps 2 labels, the probabilities are written next to labels, the labels of the blue node will be updated from d, c to a, c with label probabilities P_a = 6.3/(6.3+1.85) = 0.77 and P_c = 1.85/(6.3+1.85) = 0.23.

Considerations

• LPA ignores the direction of edges but calculates them as undirected edges.
• Node with self-loops propagates its current label(s) to itself, and each self-loop is counted twice.
• LPA follows the synchronous update principle when updating node labels. This means that all nodes update their labels simultaneously based on the labels of their neighbors. However, in some cases, label oscillations can occur, particularly in bipartite graphs. To address this issue, the algorithm incorporates an interrupt mechanism that detects and prevents excessive label oscillations.
• Due to factors such as the order of nodes, the random selection of labels with equal weights, and parallel calculations, the community division results of LPA may vary.

Syntax

• Command: algo(lpa)
• Parameters:

Examples

The example graph is as follows, nodes are of schema user, edges are of schema connect, the value of @connect.strength is shown in the graph:

File Writeback

UQL
algo(lpa).params({
  k: 2,
  loop_num: 5,
  edge_weight_property: 'strength'
}).write({
  file:{
    filename: "lpa"
  }
})

Statistics: label_count = 7
Results: File lpa

File
O,1,0.599162,2,0.400838,
N,1,0.634582,2,0.365418,
M,1,0.610834,2,0.389166,
L,1,0.607434,2,0.392566,
K,1,0.619842,2,0.380158,
J,14,0.655975,8,0.344025,
I,14,0.546347,8,0.453653,
H,9,0.690423,7,0.309577,
G,14,0.569427,8,0.430573,
F,9,0.784132,7,0.215869,
E,9,0.519003,12,0.480997,
D,14,0.781072,9,0.218928,
C,12,0.540345,9,0.459655,
B,9,0.559427,14,0.440573,
A,14,0.768171,12,0.231829,

Property Writeback

UQL
algo(lpa).params({
  node_label_property: 'interest',
  edge_weight_property: '@connect.strength',
  k: 2,
  loop_num: 10
}).write({
  db:{
    property: "lab"
  }
})

Statistics: label_count = 5
Results: The labels and the corresponding probability of each node is written to new properties lab_1, probability_1, lab_2 and probability_2 respectively

Direct Return

UQL
algo(lpa).params({
  node_label_property: '@user.interest',
  node_weight_property: '@user.level'
}) as res
return res

Results: res

UQL
algo(lpa).params({
  node_label_property: 'interest',
  k: 2
}) as res, stats
return res, stats

Results: res and stats

Stream Return

UQL
algo(lpa).params({
  node_label_property: '@user.interest',
  node_weight_property: '@user.level',
  edge_weight_property: 'strength',
  loop_num: 10
}).stream() as lpa
group by lpa.label_1
with count(lpa) as labelCount
return table(lpa.label_1, labelCount) 
order by labelCount desc

Results: table(lpa.label_1, labelCount)

Stats Return

UQL
algo(lpa).params({
  node_label_property: 'interest',
  edge_weight_property: 'strength',
  k: 1,
  loop_num: 5
}).stats() as count 
return count

Results: count