Graphical separation using the Neo4j database

Question

I know that there are some well-known tools of the graph separation algorithm, such as METIS, which is implemented by karypis Lab ( http://glaros.dtc.umn.edu/gkhome/metis/metis/overview )

but I want to know if there is any method for splitting a graph stored in Neo4j? or should I flush the Neo4j data and convert the node and edge format manually to fit the METIS input format?

Answer 1

As for new and interesting algorithms, this is by no means exhaustive or modern, but these are the first places I would look:

Specific Algorithm: DiDiC (Distributed Diffusion Clustering) - I used it once in my dissertation ( Graph Partition Tables )

• You iterate over all the nodes, then for each node, extract all the neighbors to spread some "some units" to all your neighbors
• Easy to implement.
• Can be made deterministic
• Iterative - since it is based on iterations (e.g. Super Steps in Pregel), you can stop it at any time. The longer you leave it, the better, theoretically (although in some cases, it may be unstable on some forms of the graph)
• When we realized this, we performed it for 100 iterations on a machine with ~ 30 GB of RAM, for ~ up to 4 million nodes - it took no more than two days.

Specific Algorithm: EvoCut "Locating Sparse Slices Locally Using Evolving Sets" - Microsoft's Local Probabilistic Algorithm - Related Documents

• Hard to implement
• Local Algorithm - BFS-like access patterns (random walks)
• Some time has passed since I read this paper, but I remember that it was built on pure abstractions:
  • EvoNibble (plug-in) - determines how much of the neighborhood is added to the current cluster.
  • EvoCut (calls EvoNibble several times to find a local cluster)
  • EvoPartition (repeatedly calls EvoCut to share the entire chart)
• Not deterministic

General Algorithm Family: Clustering Hierarchical Graphs

From a high level:

• Grab of the graph by folding nodes into aggregate nodes
  • coarsening strategy is chosen
• Find clusters in an enlarged / smaller chart
  • Clustering Strategy Selected
• Incrementally decorate the graph, clarifying during clustering at each step
  • cleaning strategy is selected

Notes:

• If the schedule changes slowly (or the results do not have to be relevant), it is possible that sometime (or rarely) it will be possible to enlarge the work, and then work with the enlarged schedule to save the calculations
• I do not know a specific algorithm to recommend

Common limitations are what several clustering algorithms do:

• Node types are not validated - i.e. all nodes processed equally
• Relationship types not confirmed - i.e. all relationships that are treated equally
• The direction of the relationship is not confirmed - i.e. relationships treated as undirected

Answer 2

Working independently with METIS and Neo4j in the past, I don’t know a single tool for creating a METIS file from Neo4j. At the same time, writing such a tool should be an easy task and will be a great community contribution.

Another approach for integrating METIS with Neo4j may be to connect METIS to Neo4j from C ++ through JNI. However, it will be much more active, as he will have to take care of such things as transactions, concurrency, etc.

In the more general question of graph partitioning, it is possible to implement reasonable efforts with some of the more well-known and simple algorithms.