Speaker-Listener Label Propagation

Supported Graph Characteristics

Unweighted edges

Directed edges

Undirected edges

Homogeneous vertex types

Heterogeneous vertex types

Algorithm link: Speaker-Listener Label Propagation

The Speaker-listener Label Propagation Algorithm (SLPA) is a variation of the Label Propagation algorithm that is able to detect overlapping communities. The main difference between LPA and SLPA is that each node can only hold a single label in LPA while it is allowed to possess multiple labels in SLPA.

The algorithm begins with each vertex having its own unique label. It then iteratively records labels in a local accumulator based on specific speaking and listening rules. Then the post-processing of the record labels is applied. Finally, the algorithm removes the nested communities and outputs all the communities. Note that it is not guaranteed to produce the same results every time.

Notes

For more information, see SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process.

Specifications

CREATE QUERY tg_slpa (SET<STRING> v_type, SET<STRING> e_type, FLOAT threshold, INT max_iter, INT output_limit,
BOOL print_accum = TRUE, STRING file_path = "")

Parameters

Parameter Description Default

SET<STRING> v_type

The vertex types to use

(empty set of strings)

SET<STRING> e_type

The edge types to use

(empty set of strings)

FLOAT threshold

The threshold to drop a label

0

INT max_iter

The maximum number of iterations

10

BOOL print_accum

Whether to print the output in JSON format

False

STRING file_path

The file to write the output to in CSV format

(empty string)

INT output_limit

The maximum number of vertices to output. A value of -1 will output all vertices.

0

Output

Assigns a list of component IDs in INT form to each vertex, such that members of the same component have the same ID value.

The result size is equal to \$V\$, the number of vertices.

Time complexity

This algorithm has a complexity of \$O(E*k)\$, where \$E\$ is the number of edges and \$k\$ is the number of iterations.

Example

In the example below, we run the tg_slpa algorithm on the social10 graph. We set max_iter = 10 and threshold = 0.1.

  • Query

  • Result

# Use _ for default values
RUN QUERY (["Person"], ["Coworker"], _, _, _, _, _
[
  {
    "@@COM": {
      "Fiona": [294649859],
      "Alex": [270532609],
      "Damon": [279969793],
      "Justin": [270532609],
      "Eddie": [279969793],
      "Chase": [279969793],
      "Howard": [294649859],
      "George": [294649859],
      "Bob":[270532609],
      "Ivy":[294649859]
    }
  }
]

The result shows that each community has a unique community ID in the com attribute.

Visualized results