Label Propagation Algorithm

Introduction

The Label Propagation Algorithm (LPA) is a fast and efficient method for detecting communities within a graph.

Output

The algorithm produces the following fields:

Field Name	Description
id	The ID of the vertex (node)
communityId	A community ID assigned to the node.

Query Example

cyphergremlin

CALL algo.labelPropagation({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    relationshipWeightProperty: 'weight',
    labelProperty: 'tag'
    }) YIELD id, communityId
RETURN id, communityId

graph.compute().program(
  LabelPropagationProgram.build()
    .maxIteration(20)
    .vertices("User")
    .edges("LINK")
    .setParams("weight", "amount")
    .setParams("labelProperty", "tag")
    .setParams("pinLabel", true)
    .create()
).submit().get().toList()

Parameters

cyphergremlin

Name	Description	Required	Default Value
labels	Specifies the node labels to include in the algorithm	Yes
relationshipTypes	Specifies the types of relationships to include	Yes
maxIterations	Maximum number of iterations	No	30
relationshipWeightProperty	Defines the property name representing edge weights	No
labelProperty	The property used to assign an initial community ID	No	""
pinLabel	Determines if the initial label of vertices remains fixed	No	false

Method	Description	Required	Default Value
vertices(String... names)	Specifies the vertex labels to include	Yes
edges(String... names)	Specifies the edge labels to include	Yes
maxIteration(int n)	Sets the maximum iteration count	No	30
setParams(Object... args)	Adds additional parameters using alternating keys and values	No	see below

Additional parameter keys in setParams

Key	Description	Default Value
weight	Specifies edge weight property or a constant number	1.0
labelProperty	Property name for assigning an initial community ID	""
pinLabel	Determines if the initial label of vertices remains unchanged	false

Exporting Query Results

For large datasets, export the results to object storage:

cyphergremlin

EXPORT TO 's3://my_bucket/target_dir'
PROPERTIES {
  catalog: 'puppygraph_catalog_name'
}
CALL algo.labelPropagation({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    relationshipWeightProperty: 'weight'
    }) YIELD id, communityId
RETURN id, communityId

graph.compute().program(
    LabelPropagationProgram.build()
            .maxIteration(20)
            .vertices("User")
            .edges("LINK")
            .setParams("weight", "amount")
            .create()
).submit().get().save([
  "exportTo": "s3://my_bucket/target_dir",
  "catalog": "puppygraph_catalog_name"
])