Connected Component

Overview

The Connected Component algorithm identifies the connected components in a graph, which is the essential indicator to examine the connectivity and topology characteristics of the graph.

The number of connected components in a graph can serve as a coarse-grained metering method. If the number of connected components remains unchanged after certain operations or modifications to the graph, it suggests that the macroscopic connectivity and topology characteristics of the graph have not been altered significantly.

This information is valuable in various graph analysis scenarios. For example, in social networks, if the number of connected components remains the same over time, it implies that the overall connectivity patterns and community structures within the network have not experienced substantial changes.

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 in the graph. A maximal subset means that no additional nodes can be added to the subset without breaking the connectivity requirement.

The number of connected components in a graph indicates the level of disconnectedness or the presence of distinct subgraphs within the overall graph. A graph that has exactly one component, consisting of the whole graph, is called a connected graph.

Weakly and Strongly Connected Component

There are two important concepts related to connected component: weakly connected component (WCC) and strongly connected component (SCC):

• A WCC refers to a subset of nodes in a directed or undirected graph where there exists a path between any pair of nodes, regardless of the direction of the edges.
• A SCC is a subset of nodes in a directed graph where there is a directed path between every pair of nodes. In other words, for any two nodes u and v in a SCC, there is a directed path from u to v and also from v to u. In directed path, all edges have the same direction.

This example shows the 3 strongly connected components and 2 weakly connected components of a graph. The number of SCCs in a graph is always equal to or greater than the number of WCCs, as determining a SCC requires stricter conditions compared to a WCC.

Considerations

• Each isolated node in the graph is a connected component, and it is both a strongly connected component and a weakly connected component.

Syntax

• Command: algo(connected_component)
• Parameters:

NOTE

In Ultipa's Connected Component algorithm, each connected component is denoted as a community.

Examples

The example graph is as follows:

File Writeback

UQL
algo(connected_component).params({
  cc_type: 1
}).write({
  file:{ 
    filename_community_id: 'f1',
    filename_ids: 'f2',
    filename_num: 'f3'
  }
})

Statistics: community_count = 2
Results: Files f1, f2, f3

File: f1
Alice,0
Bill,0
Bob,0
Sam,0
Joe,0
Anna,0
Cathy,6
Mike,6

File: f2
0,Alice,Bill,Bob,Sam,Joe,Anna,
6,Cathy,Mike,

File: f3
0,6
6,2

Property Writeback

UQL
algo(connected_component).params().write({
  db:{ 
    property: 'wcc_id'
  }
})

Statistics: community_count = 2
Results: The community ID of each node is written to a new property named wcc_id

Direct Return

UQL
algo(connected_component).params({
  cc_type: 2
}) as r1, r2
return r1, r2

Results: r1 and r2

Stream Return

UQL
algo(connected_component).params({
  cc_type: 2
}).stream() as r
return r

Results: r

UQL
algo(connected_component).params({
  cc_type: 2,
  order: 'asc'
}).stream({
  mode: 2
}) as r
return r

Results: r

Stats Return

UQL
algo(connected_component).params().stats() as count
return count

Results: count