0
$\begingroup$

I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of elements attached to them (we could say they form clusters). Is there any method or algorithm that analyzes this problem?

enter image description here

enter image description here

$\endgroup$
  • 1
    $\begingroup$ If you've specified a root, the obvious clustering (which you've drawn) groups leaves by which root-adjacent node they descend from. $\endgroup$ – Neal Dec 11 '18 at 14:54
1
$\begingroup$

To the best of my knowledge, all serious graph-based software implements some form of community subgraph detection, with different documented algorithms, such as these (from Mathematica):

enter image description here


myGraph = 
  TreeGraph[
   RandomInteger[#] \[UndirectedEdge] # + 1 & /@ Range[0, 30]];
myMethods = {"Centrality", "Hierarchical", "Spectral", "CliquePercolation", "VertexMoving"};
Grid[{(CommunityGraphPlot[myGraph, FindGraphCommunities[myGraph,
       Method -> #]] & /@ myMethods), myMethods}]
$\endgroup$
1
$\begingroup$

You can apply most of the popular methods of community detection to trees. Here is a (perhaps outdated) overview paper, that should give you an idea of the types of algorithms to look for. The GenLouvain method is widely used, and available on GitHub.

If you use a modularity-based method, do not to read too much into the modularity score (the value that is optimized over all partitions) as a measure of how "good" your communities are, as this tends to be high for trees regardless of their structure.

$\endgroup$
1
$\begingroup$

There is not a universal "best way" to find the clusters. It depends very much on how big your tree is, how homogeneous it is, and most importantly on the precise mathematical notion of clustering that you are after (network modularity is a only one of them).

The C/R/python library igraph has several different community detection methods already implemented: they are based on different notions of clustering and/or different ways to identify the best clustering. If you don't know where to start, I suggest you read link and link. The latter also links to the academic papers where each of these methods has been proposed, in case you want to dig deeper.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.