Weakly Connected Components

Find disconnected groups and network structure

Weakly Connected Components identifies maximal subgraphs where every node can reach every other node when edge direction is ignored.

What It Computes

For each node, assigns a component ID. All nodes with the same ID are part of the same connected group.

Key insight: Reveals network fragmentation - how many isolated groups exist, and how large is the main component.

When to Use It

✅ Network Analysis

Identify disconnected network segments

✅ Data Quality

Find isolated records or orphaned entities

✅ Fraud Detection

Separate independent fraud rings

✅ Social Networks

Measure network cohesion

Parameters

No parameters - runs on full graph.

Performance

Time Complexity: O(V + E)
Space Complexity: O(V)
Typical Runtime: <1 second for 1M edges

Scales to: 100M+ edges efficiently

Example

Output:

Real-World Use Cases

Network Fragmentation Analysis

Problem: Is network fragmenting over time?
Solution: Track component count evolution

Interpretation:

Decreasing components: Network connecting over time
Increasing components: Network fragmenting

Fraud Ring Separation

Problem: Multiple independent fraud rings in data
Solution: Each component = potential separate ring

Data Quality Check

Problem: Orphaned records in ETL pipeline
Solution: Isolated components indicate data issues

Giant Component

The Giant Component is the largest connected component, typically containing most nodes in social/technological networks.

Typical in social networks: 95%+ nodes in giant component
Fragmented networks: <50% nodes in giant component

Weakly vs Strongly Connected

Weakly Connected: Ignore edge direction
Strongly Connected: Respect edge direction (stricter)

Example:

Weakly: All 3 nodes in one component
Strongly: Depends on exact connections

When to use which:

Undirected graphs: Always weakly connected
Directed graphs: Weakly for general connectivity, strongly for directed reachability

Performance Tips

Use temporal windows for evolution tracking
Filter small components for analysis (size < 3)
Sample inspection: Check largest components first
Parallel processing: Components can be analyzed independently