2

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.

scottandrus
  • 93
  • 7
  • I believe you are searching your graph for cliques (http://en.wikipedia.org/wiki/Clique_(graph_theory)) or 'complete subgraphs'. http://en.wikipedia.org/wiki/Clique_problem describes approaches to this (not so simple) problem. Unfortunately I don't know if neo4j has such an algorithm. But I fear it has not. – Slomo Jun 27 '12 at 19:19
  • Thanks! The outlook is grim, but I appreciate knowing that! – scottandrus Jun 27 '12 at 19:25

2 Answers2

1

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.

Community
  • 1
  • 1
ZachM
  • 893
  • 2
  • 8
  • 22
  • Shoot. I imagined that this was probably a larger-scope algorithms problem, but I was hoping that Neo4j might have an algorithm defined for this. Thanks! – scottandrus Jun 27 '12 at 19:26
  • Also, if you can come up with an implementation, the Neo4j community would be very interested to add it to the graph-algo component, see https://github.com/neo4j/community/tree/master/graph-algo – Peter Neubauer Jul 02 '12 at 09:46
  • I'll be interested in finding a way to contribute if I can find a solution. I am currently working through a C#/.NET implementation of the [Bron-Kerbosch algorithm](http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm). – scottandrus Jul 06 '12 at 19:32
0

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...

Aerodynamika
  • 7,883
  • 16
  • 78
  • 137