Weakly Connected Components (WCC)

Overview

The WCC algorithm identifies the weakly connected components in a graph. A weakly connected component is a maximal subset of nodes where a path exists between any pair of nodes when edge directions are ignored.

The number of connected components serves as a coarse-grained measure of graph connectivity. If the number remains unchanged after modifications to the graph, it suggests that the macroscopic connectivity has not been altered significantly.

Concepts

Connected Component

A connected component is a maximal subset of nodes in a graph where all nodes in that subset are reachable from one another by following edges. A maximal subset means that no additional nodes can be added to the subset without breaking the connectivity requirement.

Weakly vs Strongly Connected Components

• A weakly connected component (WCC) is a subset of nodes where a path exists between any pair of nodes when edge directions are ignored.
• A strongly connected component (SCC) is a subset of nodes in a directed graph where there is a directed path between every pair of nodes in both directions. See SCC for details.

This example shows the 3 strongly connected components and 2 weakly connected components of a graph.

Considerations

• The algorithm treats all edges as undirected.
• Each isolated node constitutes its own connected component.

Example Graph

GQL
INSERT (Mike:member {_id: "Mike"}), (Cathy:member {_id: "Cathy"}),
       (Anna:member {_id: "Anna"}), (Joe:member {_id: "Joe"}),
       (Sam:member {_id: "Sam"}), (Bob:member {_id: "Bob"}),
       (Bill:member {_id: "Bill"}), (Alice:member {_id: "Alice"}),
       (Cathy)-[:helps]->(Mike), (Anna)-[:helps]->(Sam),
       (Anna)-[:helps]->(Joe), (Joe)-[:helps]->(Bob),
       (Bob)-[:helps]->(Joe), (Bob)-[:helps]->(Bill),
       (Bill)-[:helps]->(Alice), (Bill)-[:helps]->(Anna),
       (Alice)-[:helps]->(Anna)

Run Mode

Returns:

GQL
CALL algo.wcc() YIELD nodeId, componentId, componentSize

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.wcc.stream() YIELD nodeId, componentId, componentSize
RETURN componentId, COLLECT(nodeId) AS members, componentSize
GROUP BY componentId

Result:

Stats Mode

Returns:

GQL
CALL algo.wcc.stats() YIELD nodeCount, componentCount, largestComponentSize, smallestComponentSize

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.wcc.write({}, {
  db: {
    property: "wcc_id"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs