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.

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 = "")
Characteristic Value

Result

Assigns a list of component id (INT) to each vertex, such that members of the same component have the same id value.

Required Input Parameters

**v_type**: vertex types to traverse`**e_type**: edge types to traverse**threshold**: threshold to drop a label**max_iter**: number of iterations**print_accum**: print JSON output**file_path**: file to write CSV output to**output_limit**`: max #vertices to output (-1 = all)

Result Size

V = number of vertices

Time Complexity

O(E*k), E = number of edges, k = number of iterations.

Graph Types

Undirected edges

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]
    }
  }
]
Visualized results