Minimum spanning trees

Hierarchical methods are preferred when a visual representation of the clustering is wanted. When the number of objects is not too large, one may even compute a clustering by hand using the minimum spanning tree. 

Cherition D, Tarjan RE (1976) Finding minimum spanning trees. SIAM J Computing 5 724... 

Subramaniam, S. and S. B. Pope (1998). A mixing model for turbulent reactive flows based on Euclidean minimum spanning trees. Combustion and Flame 115,487-514. 

A very different approach to characterize clustering tendency is based on the frequency distributions of the lengths of the edges in the minimum spanning tree connecting the objects in the real data and in uniformly distributed data (Forina et al. 2001). 

The length obtained by the traversal of the minimum spanning tree (MST). 

Graphical methods in connection with pattern recognition algorithms, i.e. geometrical or statistical methods, e.g. minimum spanning tree or cluster analysis, are more powerful methods for explorative data analysis than graphical methods alone. 

Mount et al. [32] describe a DBCS method that is based on a minimum spanning tree. A spanning tree is a set of edges that connect a set of objects. The objects in this method are the molecules in the subset, and each edge is labeled by the dissimilarity between the two molecules it connects. A minimum spanning tree is the spanning tree that connects all molecules in the subset with the minimum sum of pairwise dissimilarities thus, the diversity is the sum of just some of the intermolecular similarities rather than all of them as in MaxSum. A similar function has also been developed by Brown et al. [34],... 

The use of hierarchical cluster analysis leading to the construction of dendrograms and minimum spanning trees for data sets where the samples analyzed have... 

In the first case the auctioneer would like to buy the edges necessary to build the minimum spanning tree. If the auctioneer uses a VCG auction, what does she end up paying for an edge, e, say, in the MST ... 

Recall that one way to phrase to the minimum spanning tree problem is as follows find the least weight collection of edges that intersect every cycle of the graph at least once. 

Hence the tree T as constructed by the algorithm (i)-(iii) is a minimum spanning tree of gi h G. If we have Cj = Cy for some j f, the minimum spanning tree need not be unique but the sum (A. 14) is equal for any such tree. If Cj Cj. for any j /, T is unique and we have strict inequality in (A.24). Clearly, a maximum tree will be found with the inverse order of arcs. 

Figure 36.4 Two dimensional ordination plots of the selected OGUs on the principal axes of nonmetric multidimensional scaling. Stress value 0.1 I. Minimum spanning trees and bond links are superimposed on the plot the heavier the line the stronger the link. Continuous lines represent strong connections (bond >2), whereas dashed lines loose intergroups relationships.

Gower, J.C. and Ross, GJ.S. (1969) Minimum spanning trees and single linkage cluster analysis... 

---