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.

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.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().node_schema("user").edge_schema("connect")
create().node_property(@user,"interest",string).node_property(@user,"level",int32).edge_property(@connect,"strength",int32)
insert().into(@user).nodes([{_id:"A",interest:"flute",level:2}, {_id:"B",interest:"football",level:4}, {_id:"C",interest:"piano",level:4}, {_id:"D",interest:"violin",level:2}, {_id:"E",interest:"piano",level:4}, {_id:"F",interest:"movie",level:1}, {_id:"G",interest:"piano",level:4}, {_id:"H",interest:"tennis",level:2}, {_id:"I",interest:"violin",level:3}, {_id:"J",interest:"badminton",level:5}, {_id:"K",interest:"swimming",level:4}, {_id:"L",interest:"cello",level:1}, {_id:"M",interest:"saxophone",level:2}, {_id:"N",interest:"novel",level:3}, {_id:"O",interest:"swimming",level:3}])
insert().into(@connect).edges([{_from:"A",_to:"B",strength:3}, {_from:"A",_to:"C",strength:5}, {_from:"A",_to:"F",strength:8}, {_from:"A",_to:"K",strength:6}, {_from:"B",_to:"C",strength:2}, {_from:"C",_to:"D",strength:9}, {_from:"D",_to:"A",strength:5}, {_from:"D",_to:"E",strength:6}, {_from:"E",_to:"A",strength:5}, {_from:"F",_to:"G",strength:9}, {_from:"F",_to:"J",strength:4}, {_from:"G",_to:"H",strength:10}, {_from:"H",_to:"F",strength:3}, {_from:"I",_to:"H",strength:4}, {_from:"I",_to:"F",strength:2}, {_from:"J",_to:"I",strength:1}, {_from:"K",_to:"F",strength:1}, {_from:"K",_to:"N",strength:10}, {_from:"L",_to:"M",strength:1}, {_from:"L",_to:"N",strength:4}, {_from:"M",_to:"N",strength:8}, {_from:"M",_to:"K",strength:10}, {_from:"N",_to:"M",strength:4}, {_from:"O",_to:"N",strength:1}])

Running on HDC Graphs

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_lpa:

CALL hdc.graph.create("hdc-server-1", "hdc_lpa", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_lpa", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: lpa

File Writeback

CALL algo.lpa.write("hdc_lpa", {
  params: {
    return_id_uuid: "id",
    k: 2,
    loop_num: 5,
    edge_weight_property: 'strength'
  },
  return_params: {
    file: {
      filename: "lpa"
    }
  }
})

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

DB Writeback

Writes each label_<N> and the corresponding probability_<N> from the results to the specified node properties. The property types are string and float, respectively.

CALL algo.lpa.write("hdc_lpa", {
  params: {
    node_label_property: 'interest',
    k: 2,
    loop_num: 10
  },
  return_params: {
    db: {
      property: "lab"
    }
  }
})

algo(lpa).params({
  projection: "hdc_lpa",
  node_label_property: 'interest',
  k: 2,
  loop_num: 10
}).write({
  db: {
    property: "lab"
  }
})

The label and label probability of each node is written to new properties lab_1, probability_1, lab_2, and probability_2.

Stats Writeback

CALL algo.lpa.write("hdc_lpa", {
  params: {
    node_label_property: 'interest',
    k: 2,
    loop_num: 10
  },
  return_params: {
    stats: {}
  }
})

algo(lpa).params({
  projection: "hdc_lpa",
  node_label_property: 'interest',
  k: 2,
  loop_num: 10
}).write({
  stats:{}
})

Result:

Full Return

CALL algo.lpa("hdc_lpa", {
  params: {
    return_id_uuid: "id",
    node_label_property: "@user.interest",
    k: 2
  },
  return_params: {}
}) YIELD r
RETURN r

exec{
  algo(lpa).params({
    return_id_uuid: "id",
    node_label_property: "@user.interest",
    k: 2
  }) as r
  return r
} on hdc_lpa

Result:

Stream Return

CALL algo.lpa("hdc_lpa", {
  params: {
    return_id_uuid: "id",
    node_label_property: "@user.interest",
    node_weight_property: "@user.level",
    edge_weight_property: "strength",
    loop_num: 10
  },
  return_params: {
    stream: {}
  }
}) YIELD r
RETURN r.label_1 AS label, count(r) GROUP BY label

exec{
  algo(lpa).params({
    return_id_uuid: "id",
    node_label_property: "@user.interest",
    node_weight_property: "@user.level",
    edge_weight_property: "strength",
    loop_num: 10
  }).stream() as r
  group by r.label_1 as label
  return table(label, count(r)) 
} on hdc_lpa

Result:

Stats Return

CALL algo.lpa("hdc_lpa", {
  params: {
    node_label_property: "interest",
    edge_weight_property: "strength",
    k: 1,
    loop_num: 5
  },
  return_params: {
    stats: {}
  }
}) YIELD s
RETURN s

exec{
  algo(lpa).params({
    node_label_property: "interest",
    edge_weight_property: "strength",
    k: 1,
    loop_num: 5
  }).stats() as s
  return s
} on hdc_lpa

Result:

Running on Distributed Projections

Creating Distributed Projection

To project the entire graph to its shard servers as dist_lpa:

create().projection("dist_lpa", {
  nodes: {"*": ["*"]}, 
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true
})

Parameters

Algorithm name: lpa