Search code examples
neo4jcypher

Find groups of connected nodes in Cypher

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?

enter image description here

Solution

  • 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)