Weakly Connected Components

Introduction

The Weakly Connected Components (WCC) algorithm identifies connected components within a directed graph, disregarding edge direction.

Output

The algorithm produces the following fields:

Field Name	Description
id	The ID of the node (vertex)
componentId	A generated integer ID representing the component of the node (vertex)

Query Example

cyphergremlin

CALL algo.wcc({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    maxIterations: 20
    }) YIELD id, componentId
RETURN id, componentId

graph.program(
  WeakConnectedComponentProgram.build()
    .maxIteration(20)
    .vertices("User")
    .edges("LINK")
    .create()
).submitAndGet().toList()

Filter edges by threshold

Set an edge attribute as weight / relationshipWeightProperty, then set a threshold. Only edges with weight greater than or equal to the threshold will be included.

cyphergremlin

CALL algo.wcc({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    relationshipWeightProperty: 'score',
    threshold: 5.0,
    maxIterations: 20
    }) YIELD id, componentId
RETURN id, componentId

graph.program(
  WeakConnectedComponentProgram.build()
    .maxIteration(20)
    .vertices("User")
    .edges("LINK")
    .setParams("threshold", 5.0, "weight", "score")
    .create()
).submitAndGet().toList()

Limit the minimal size of component

cyphergremlin

CALL algo.wcc({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    maxIterations: 20,
    minComponentSize: 5
    }) YIELD id, componentId
RETURN id, componentId

graph.program(
  WeakConnectedComponentProgram.build()
    .maxIteration(20)
    .vertices("User")
    .edges("LINK")
    .setParams("minComponentSize", 5)
    .create()
).submitAndGet().toList()

Set initial component ID

Set a node attribute as the initial component ID. If any node in a component has a non-null initial ID, the program will return one of the initial IDs as the final component ID. Two or more nodes having the same initial component ID may lead to different components having the same component ID in the result.

cyphergremlin

CALL algo.wcc({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    maxIterations: 20,
    seedProperty: 'city'
    }) YIELD id, componentId
RETURN id, componentId

graph.program(
  WeakConnectedComponentProgram.build()
    .maxIteration(20)
    .vertices("User")
    .edges("LINK")
    .setParams("seedProperty", 'city')
    .create()
).submitAndGet().toList()

Parameters

cyphergremlin

Name	Description	Required	Default Value
labels	Specifies the node labels to include in the algorithm	Yes
relationshipTypes	Specifies the relationship types to include	Yes
maxIterations	Maximum number of iterations	No	30
relationshipWeightProperty	Defines the property name for edge weights	No
threshold	Minimum edge weight value for it to be included in the algorithm	No	0.0
seedProperty	The node property used as the seed for the component ID	No	"id"
minComponentSize	Minimum size of the components to be returned	No	0

Method	Description	Required	Default Value
vertices(String... names)	Specifies the node (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 the edge weight property or a constant value as weight	1.0
threshold	Minimum edge weight value for it to be included in the algorithm	0.0
seedProperty	The node (vertex) property used as the component ID seed	"id"
minComponentSize	Minimum size of the components to be returned	0

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.wcc({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    relationshipWeightProperty: 'weight',
    threshold: 1.0
    }) YIELD id, componentId
RETURN id, componentId

graph.program(
    WeakConnectedComponentProgram.build()
            .maxIteration(20)
            .vertices("User")
            .edges("LINK")
            .setParams("weight", "amount", "threshold", 10.0)
            .create()
).submitAndSave([
  "exportTo": "s3://my_bucket/target_dir",
  "catalog": "puppygraph_catalog_name"
])