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?
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):
myGraph =
TreeGraph[
RandomInteger[#] \[UndirectedEdge] # + 1 & /@ Range[0, 30]];
myMethods = {"Centrality", "Hierarchical", "Spectral", "CliquePercolation", "VertexMoving"};
Grid[{(CommunityGraphPlot[myGraph, FindGraphCommunities[myGraph,
Method -> #]] & /@ myMethods), myMethods}]
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.
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.
