I have a directed graph representing some topics organized as follows (below screenshot is a subset of the graph):

enter image description here

I'm looking for an algorithm to group a set of nodes (in blue in the diagram) following this logic:

  • Groups as evenly sized as possible: we don't want groups with very few nodes and others with lots of nodes
  • If multiple groups have the same nodes, take the most specific group ie the group that's the closer successor

Now I know multiple solutions may exist for the same problem (eg 4 groups of 2 or 2 groups of 4?) but if there are existing algorithms similar to what I'm looking for I would be greatly if you can share their names so I can start testing them and see what works best for me and tweak them if needed.

Q: Do you know algorithms designed to perform similar types of node grouping?

  • $\begingroup$ Hi D.W: sorry for the lack of clarity, same items= same nodes from the set (A,B,C... G,H.I) we're trying to group. more speceific= a more direct successor $\endgroup$ – Panda Coder Oct 2 at 6:30
  • $\begingroup$ As for the tradeoffs I don't know yet, I plan on running the algorithm with various parameters, and crowdsource the rating of the output to settle for what most people prefer. $\endgroup$ – Panda Coder Oct 2 at 6:41
  • $\begingroup$ Sorry, I still don't understand. I hope you can revise the question to state the problem clearly. Apparently there's a set of nodes, and some other set, and I'm not clear on how they are related, or what an item is, or how it relates to a node. I don't know what a direct successor is or how to use that to evaluate a group. If you don't know how you want to trade them off, you don't know what answer you want from the algorithm yet, so I don't see how we can suggest an algorithm. $\endgroup$ – D.W. Oct 2 at 8:47
  • $\begingroup$ No need to be sorry. Item: term removed, I only talk about "nodes". direct successor: en.wikipedia.org/wiki/Directed_graph#Basic_terminology (here the closer the successor, the more specific). Tradeoffs: I have some general principles (not too many groups, groups evenly sized, the more specific the better) but don't know the exact balance yet. I will use crowd feedback to rate the output based on various tuning parameters. So right now I'm just looking for names of algorithms close to what I'm after so I can start experimenting and refining my approach. $\endgroup$ – Panda Coder Oct 2 at 11:57
  • $\begingroup$ I don't understand what you mean by a group. Can you define your terms precisely? I would understand "groups" as a partition of the set of nodes, but then I don't understand how multiple groups can have the same nodes. I still don't see any clear description of what is meant by a "more specific group"; saying it is about direct successor doesn't help because I don't know what the direct successor of a group is (that terminology is used for nodes, not sets of nodes), nor do I understand what you mean to "take" a group or not take it. $\endgroup$ – D.W. Oct 2 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.