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.
In the example below, we run the tg_slpa
algorithm on the social10 graph. We set max_iter = 10 and threshold = 0.1.
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