CODEWITHSUNDEEP
neo4j
scottandrus
scottandrus

Reputation: 93

Finding distinct node groupings based on mutual relations in neo4j

Is there a query for a Neo4J graph that could traverse said graph and find nodes based on mutual relationships? For example, if Node A is related to Node B (bidirectionally), B is related to C, C is related to D, D is related to A, A is related to C, and B is related to D, such that there is a subgraph in which every node is connected to every other node, is there an efficient way to return that subgraph or group of Nodes?

I realize my explanation is poor, so I provide an example graph in the console: http://console.neo4j.org/r/qb2xmp

Here, I have created a graph, and I would like to return groups that are mutually related of 3 or more - so, in this case, I would ideally like to be returning the group of Scott, Josh, Frank, and Ben, as well as the group of Frank, Ben, and Eric. If possible, I would like to be able to identify who composes those individual groups.

Upvotes: 2

Views: 1166

Answers (2)

Aerodynamika
Aerodynamika

Reputation: 8413

did you find any solutions for this?

I implemented something like this on my project for text network visualization but it launches Gephi Toolkit (on Java) to perform some metric calculations on the graph, detect communities, etc. But that's too heavy...

You might be interested to look into Gephi's algorithms though, especially the Force Atlas layout implemented in Sigma.Js and especially the modularity algorithm used in Gephi itself. This might give you some clues as to how to proceed...

Upvotes: 0

ZachM
ZachM

Reputation: 903

This is an instance of the Clique Problem and is NP-Complete.
Here is a related question on SO with a good explanation!

Sorry I hit enter too soon. So there is no "efficient" way to do this. It is not unattemptable though in certain cases, and you will have the best luck looking for an algorithm that solves this general problem and implementing it in Neo4J.

Upvotes: 1

Related Questions