Ultrametric

Fig. 7.3 A representation of the (conjectured) ultrametric distribution of spin-glass equilibrium states. The leaves of the tree at bottom are identified with the states overlaps between states are measured by the number of levels it takes to trace the states back to their common roots . For the three states a, 0 and 7, for example, we have that qot y = q y = q and = 92 > 9l-...

Two popular distance metrics are the Manhattan distance metric (r = 1), which represents the sum of the absolute descriptor differences, and the ultrametric (r = °o), which represents the maximum absolute descriptor difference. Both the Manhattan and Euclidean distance metrics obey all four metric properties. 

Many hierarchical clustering algorithms are based on ultrametric partitionings of the objects. As described by Johnson (1967), an ultrametric d between clusters satisfies the usual metric conditions plus the ultrametric inequality,... 

Given an ultrametric, Johnson s hierarchical clustering schemes define the level eiu) of a subtree u as... 

The Cayley tree is a pictorial representation of a space that is called ultrametric. Each point of the ultrametric space can be put into correspondence with an element of the fractal set that is, the fractal set and ultrametric space are topologically equivalent sets. We remark that the main feature of an ultrametric space, as well as that of a fractal set, is its hierarchical property. 

The following constitutes the definition of the distance between two points in an ultrametric space. The points in an ultrametric space on a given hierarchical level are the ends of the Cayley tree branches (Fig. 13). The number of points on the rath level of the Cayley tree is equal to Nn = j". Each point on the nth level can be numbered ... 

Thus, each point on the nth level of an ultrametric space corresponds to an n-digit number in the /-digit system of calculation (Fig. 13) ... 

These points constitute a space with ultrametric topology. 

The distance between two points in the ultrametric space is defined by the number of steps from these points to the common limit. For example, the distance between points 00 and 03 equals 1, and the distance between points 02 and 12 equals 2 (Fig. 13). Thus, the distance between two points in the ultrametric space with coordinates given by w-digit numbers in the /-digit system of calculation only depends on which digit these numbers first differ and does not depend on the specific values of this difference. 

The points of the discrete ultrametric space (Cayley tree junctions) on the nth level, namely, N , are divided into clusters (groups). Each cluster contains j points the distance between which is / = 1 and has its progenitor on the (.n — l)th level. The number of such clusters is N /j = jn l ... 

The unity of clusters corresponds to an arbitrary distance l between points in the ultrametric space. All points are united in j subclusters with distance l — 1 and having/ points. Thus, the group of clusters formed on the hierarchical level n — 1 corresponds to an arbitrary distance l. If the limit transition is made when n —> oo, then the number of the points attaining level n approaches infinity (Nn —y oo) that is, the intervals between points Ax = 1/Nn become infinitely small, and the ultrametric space itself becomes continuous. On the Cayley free, the transition to a continuous ultrametric space indicates a condensation of the hierarchical levels. 

The distance between two points in an ultrametric space in the conventional Euclidean sense can be defined as... 

This approximate equation means that the ultrametric space has a logarithmic metric. Thus, when constructing a fractal set, each element corresponds to a point of the ultrametric space with geometric image represented by the Cayley tree. 

The hierarchical chain of changes from the initial state (t = 0) to the final one (t —> oo) can be compared to a Cayley tree [25,26] (see Fig. 64). Here, the knots of the Cayley tree will correspond to static ensembles a and p which correspond to the dots in ultrametric space divided by the distance lap. 

The value of lap is defined by the number of steps over the levels of the Cayley tree up to the mutual knot in Fig. 64 and it yields the extent of a hierarchical link. Therefore, both the barrier height, Qap, and the relaxation time, xap, are connected with functions of the distance lap in ultrametric space, that is,... 

To describe the thermodynamics and kinetics of clusters with due regard for the multiplicity of the structure states (SS) of these nuclei, it is necessary to introduce the SS sets. The mutual transformations of clusters by atom attach ment or detachment, or by atom rearrangements are possible. It means that the SS set may be ordered to form a space. Then, it is possible to consider the nucleation of noncrystalline nuclei (clusters) as a diffusion process in an extended space of cluster structure states (CSS), which is, in fact, the join of hierarchy of ultrametric subspaces. The kinetic criterion of glass transition can be formulated as a condition of the overwhelming transformation of a liquid into a noncrystalline amorphous solid. 

In the previous discussion we have broadly compared trees generated from widely differing character sets. For each tree, a matrix of ultrametric distance values has been computed in order to test the goodness of fit of the cluster analyses to the data (Rohlf and Sokal, 1981). The resultant coefficients of cophenetic correlation indicated very good fits (r > 0.9) for all tested trees with the exception of the tree based on body... 

There is also no safety in ignoring such outlandish things as nonstandard analysis, superspace and anticommuting integration, p-adic and ultrametric space. All three have applications in both electrical engineering and physics. Onc complex numbers were equally outlandish, but th frequently proved the shortest path between real results. Similady, the first two topics named have already provided a number of wormhole paths. There is no telling where all this is leading -fortunatdy. 

The ultrametricity of the tree is a direct consequence of the non-intersecting property of the locally optimal paths. In ultrametric space, any three points A, A2 and A3 satisfy the inequality [22] ... 

Figure 2. An illustration of the ultrametric tree formed by locally optimal paths from the apex to the base of a 1 + 1 dimensionaJ delta. Three non-intersecting paths are drawn to schematically represent the directed optim ll paths from O to the sites A, A2 and A3. The ultrametric distances between these three sites on the base have the relation U(Ai,A2) = U(A3,Ai) > U(A2, A3) which is the same as the relation in Eq. (22).

The definition of the energy of a path given in Eq. (48) implies that the space of the optimal path energies has ultrametric structure for any three sites A, A and Az on the lattice... 

---