Overview

Connected Component algorithm is used to count the number of connected components in the current GraphSet, it is an indicator to examine the connectivity of the graph.

Connected component is a coarse-grained metering method, if the number of connected components of a graph does not change, it can be considered from a macroscopic point of view that the topology characteristics of the graph have not changed.

Basic Concept

Connected Graph

In undirected graph, if there is path between any two nodes, the graph is regarded as connected. There is no path between the red and green nodes in the graph below, so it is not connected.

In directed graph, if there is path between any two nodes in at least one direction, the graph is regarded as Weakly Connected Graph; if there are paths in both two directions, the graph is regarded as Strongly Connected Graph. Known from the definition, strongly connected graph must meet the conditions of weakly connected graph.

In the graph above, node pairs (1,4), (2,4) and (3,4) only have one-way paths, the graph only meets the requirements of weakly connected graph. Let's add another edge to the graph and calculate again:

After the modification, all node pairs in the graph have bidirectional paths, so the modified graph is strongly connected graph.

The criterion for determining a weakly connected graph in a directed graph can also be understood as: see if there is path between any two nodes when ignoring the direction of edges in the graph.

Connected Component

A connected component is a connected subgraph that is not part of any larger connected subgraph. According to the definition of connected graph, connected component can be divided into Weakly Connected Component and Strongly Connected Component.

The example above calculates the strongly and weakly connected components of the same graph. The graph can be divided into 3 strongly connected components, or 2 weakly connected components. Strongly connected component has more stringent judgement conditions than weakly connected component, so that the number of strongly connected components is always greater than the number of weakly connected components.

Special Case

Lonely Node, Disconnected Graph

Each lonely node in the graph is an independent connected component, it is both a strongly connected component and a weakly connected component.

This algorithm calculates the number of connected components, if the current graph is a strongly connected graph, it has 1 connect component.

Self-loop Edge

Self-loop edge does not affect the connectivity of the graph, i.e. it does not participate in the calculation of connected components.

Directed Edge

Calculation of strongly connected component relies on the direction of directed edges, calculation of weakly connected component ignores the direction of edges.

Results and Statistics

Take the graph below as an example, run the Connected Component algorithm against all nodes:

Algorithm results 1: Calculate weakly connect components of the whole graph, return _id, community_id or _uuid、community_id according to the execution method

Algorithm statistics 1: Number of weakly connected components community_count

Algorithm results 2: Calculate strongly connect components of the whole graph, return _id, community_id or _uuid、community_id according to the execution method

Algorithm statistics 2: Number of strongly connected components community_count

Command and Configuration

• Command: algo(connected_component)
• Configurations for the parameter params():

Example: Calculate weakly connected components of the whole graph

algo(connected_component).params({ 
  cc_type: 1 
}) as wcc
return wcc

Algorithm Execution

Task Writeback

1. File Writeback

Example: Calculate strongly connected components of the whole graph, write the algorithm results back to file named info, members and count

algo(connected_component).params({
  cc_type: 2
}).write({
  file:{ 
    filename_community_id: "info",
    filename_ids: "members",
    filename_num: "count"
  }
})

2. Property Writeback

Example: Calculate strongly connected components of the whole graph, write the community ID back to node property named community_id

algo(connected_component).params({
  cc_type: 2
}).write({
  db:{ 
    property: "community_id"
  }
})

3. Statistics Writeback

Example: Calculate strongly connected components of the whole graph, write the algorithm statistics back to task information

algo(connected_component).params({
  cc_type: 2
}).write()

Direct Return

Example: Calculate strongly connected components of the whole graph, define algorithm results and statistics as aliases named r1 and r2, and return the results and statistics

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

Streaming Return

Configurations for the parameter stream():

Example: Calculate weakly connected components of the whole graph, define algorithm results as alias named communities, and return the results ordered by the descending count of nodes in community

algo(connected_component).params({
  order: "desc"
}).stream({
  mode: 2
}) as communities
return communities

Real-time Statistics

Example: Calculate weakly connected components of the whole graph, define algorithm statistics as alias named count, and return the statistics

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