Find groups of connected nodes in Cypher

Question

I have nodes with label A. Some of them are connected with the relationship TEST (see Figure A).

I want to MATCH the groups of connected nodes, create a new node B for each group and create a relationship from each member of the group to the new node B (see Figure B). I know that the groups are small, never more then 3 steps of TEST relationships.

How can I MATCH the A nodes and return connected groups? Is there a graph algorithm implemented in APOC?

Martin Preusse Martin Preusse · Accepted Answer · 2019-03-07T11:31:03

I found the answer, maybe it's still helpful for someone:

There are several algorithms for community detection in the graph algorithm package ()https://neo4j.com/docs/graph-algorithms/current/. In this case, we look for connected components: https://neo4j.com/docs/graph-algorithms/current/algorithms/connected-components/

The algorithm can find connected components and store an ID for the component on the nodes:

CALL algo.unionFind('A', 'TEST', {write:true, partitionProperty:"partition"})
YIELD nodes, setCount, loadMillis, computeMillis, writeMillis;

With this new property it's simple to MATCH all nodes belonging to a particular group:

MATCH (a:A)
WITH a.partition AS p, a
RETURN p, count(a)

Find groups of connected nodes in Cypher

1 Answers