{'fraction_non_alphanumeric': 0.027687614876226976, 'fraction_numerical': 0.007469398928473661, 'mean_word_length': 5.043961238477901, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Retrieving Hierarchies

Several real-world and abstract structures and systems are characterized by marked hierarchy to the point of being expressed as trees. Because the study of these entities often involves sampling (or discovering) the tree nodes in a specific order that may not correspond to that originally shaping the tree, reconstruction errors can be obtained. The present work addresses this important problem based on two main resources: (i) the adoption of a simple model of trees, involving a single parameter; and (ii) the use of the coincidence similarity as the means to quantify the errors by comparing the original and reconstructed structures considering diverse sampling error probability and extent. Several interesting results are described and discussed, including the fact that the average and standard deviation values of the reconstruction errors depend only moderately on the extent of the errors as well as on the types of trees. At the same time, it is identified that the relative reconstruction accuracy substantially decreases markedly with the error probability, with larger reconstructions accuracy relative variations being observed for the smallest values of that probability.


Introduction
The physical world is characterized by an impressive diversity of structures and dynamics. Among the several possible organizations to be found, hierarchies represent a particularly interesting type of structure, being directly related to trees, the latter corresponding to connected graphs starting at a single node (the root) and then branching successively without loops along hierarchical levels, as illustrated in Figure 1.
Hierarchical organizations and trees play a particularly important role in scientific modeling because several real-world entities involve or even are completely determined by a respective hierarchical structure. Examples of intrinsically hierarchical physical structures include but are by no means limited to roots and branches of trees, vascularization, neuronal cells, among many other possibilities. At the same time, several abstractions underlying modeling also present hierarchical organization, including phylogenetics, taxonomies, archaeological chronology/stratigraphy, classifications, etc. Hierarchy plats such an important role in the modeling and understanding real-world and abstract systems that even non-hierarchical systems are often summarized in hierarchical manner, such as in terms of minimum spanning trees (e.g. [1]).
It is thus hardly surprising that substantial attention has been dedicated to the study of hierarchies, including several developments aimed at characterizing, studying, modeling, and generating hierarchical structures (e.g. [2,3,4,5,6]). In particular, research aimed at understanding how hierarchical structures can be generated can provide important basic subsidies for better understanding existing hierarchies. For instance, the branched structure of a given type of plant root can be better understood provided we know how it typically arises in nature. Additional examples of real-world related problems include ontologies, phylogenetic structures, as well as semantic structures.
Hierarchical structures can be generated in several manners, including the situation in which new entities are sampled in a given order and progressively incorporated into a respective reconstruction, e.g. while considering the overlap or similarity between the properties of the new entity and those already incorporated into the current hierarchical structure. Figure 2 illustrates the progressive reconstruction of an original reference hierarchy (a) by incorporation of successively sampled (or discovered) new entities (node in magenta). The properties of the new node (b) are compared to those of all the nodes already available in the current tree, and the maximum pairwise similarity is identified. The new entity is then respectively linked to node 0 (c), to which it is likely most similar. Given the great similarity between nodes 5 and 4, and nodes 4 and 0, by transitivity we have that node 5 will also be similar to node 0. This situation, in which one of the hierarchical levels along one of the tree paths (e.g. 0, 4, 5 → 0, 5) is missed because of the sampling order, constitutes the main reason for errors in the hierarchies reconstructions. A related question of critical interest and importance concerns to which extent different orders of sampling an original hierarchy, characterized by their various respective characteristics, can influence the respectively reconstructed trees. In our study, it is assumed that the existing tree is never reorganized other than by the inclusion of incoming nodes. This assumption, implying an incremental hierarchy retrieving approach, is aimed at modeling situations in which the currently available hierarchy has already been established as a reference, being unlikely to undergo major changes.
It is important to keep in mind that hierarchy retrieval depends not only on the order in which the new nodes are sampled (or discovered), but also on the original hierarchy, the features that characterize the nodes, as well as the adopted similarity metric. In the present approach, the sampling procedure considers two related errors: (a) the probability of changing the order of the currently sampled node; and (b) the extent of this error, which involves swapping the node order with an extent (or distance) δ.
The present work aims at studying this interesting and relevant problem, using the recently proposed coincidence methodology [7,8,9]. In addition, we resource to a simple but effective method for generating trees with diverse properties (e.g. number of levels and number of nodes per level) which involves a single parameter γ controlling the branching tendency.
Several interesting results have been reported and discussed, including the tendency of the reconstruction errors, as gauged by the average and standard deviation of the obtained coincidence values, to vary only moderately with the type of hierarchy (controled by the respective parameter of the adopted model) and with the extent of order sample error. However, the sensitivity of the average accuracy has been verified to vary more strongly with relatively small values of the probability error, increasing less markedly thereafter.
We start by presenting a review, in a non-exhaustive manner, some works related to hierarchical structures, and then follow by presenting the concepts of coincidence similarity, a simple but versatile model for generating hierarchies, and the problem of reconstructing hierarchies by sampling. The results are then presented and discussed, including several interesting findings such as the relatively independence of the average reconstruction accuracy respectively to the type of trees and error extent.

Related Works
Many works have been dedicated to hierarchical models and their applications. In order to develop a solution to the two-tree matching problem, in [4] the authors report a formal approach to matching hierarchical structures by constructing an association graph.
In another work [10], a measurement was proposed to convey the essential characteristics of the structure and hierarchy-related properties in a complex network. This measurement is based on the generalization of the concept of centrality, ranking nodes according to their impact on the whole network. In this same work, a visualization procedure was proposed for large complex networks, used to obtain a global qualitative image of the hierarchical nature of the network.
Several studies have suggested methods for building networks, trees, and hierarchical structures (e.g. [6,11,12]) for purposes such as studying its characteristics. Other studies have been dedicated to the classification and characterization of hierarchical structures (e.g. [2,3,12,13]).
Similarity concepts have also been considered while studying hierarchical structures. In [14] the authors propose a method to identify the similarity between documents based on a conceptual tree of these documents. In [15], an approach for comparing shapes is described, intended to find the best match between a pair of contours.
Works studying hierarchical network models have also been reported. As an example, [5], identify measurements that can be used to distinguish between hierarchical and non-hierarchical networks. It was described that the lack of robustness and the hierarchical structure tend to be correlated.

Basic Concepts
Similarity measures are widely used in science and technology (e.g. [16,17,18,8]), being employed to determine how much two mathematical objects are related or similar. For example, the similarity between strings can be estimated based on the characters that make up each string [17]. Similarity between sets of objects is also often considered as the means for data classification and clustering (e.g. [19,16]).
There are several alternative approaches to defining similarity, one of the most common and widely used in data analysis being the cosine distance [18,20,21]. This measure is defined as the cosine of the smallest angle between two vectors divided by the norms of these vectors. The Jaccard index (e.g. [22,23,7]) is frequently adopted for quantification of the similarity between sets, based on the concept of set cardinality.
The Coincidence Index [8,7,9] has been described as a measure to determine the similarity between virtually any type of mathematical entity, taking into account both the Jaccard and the Interiority (or overlap [17]) indices. This approach is motivated by the relative interiority between the compared sets not being captured by the Jaccard index [7], as well as by the need to generalize the Jaccard index to real-valued structures, including possibly negative values. In the present work we consider the similarity indices respectively to real, but exclusively non-negative values.
In particular, we apply the Coincidence Index to determine the similarity between two trees (or hierarchies) X and Y . Thus index can be defined as corresponding to the product between the Jaccard and Interiority indices, i.e.: where J (X, Y ) and I(X, Y ) are the Jaccard and Interiority indices, respectively.
The Interiority Index [8] is aimed at expressing how much one of the two sets is contained in the other set, and vice versa. The Interiority Index between two multisets (e.g. [24,25,26,27,28,29]) X and Y can be written [8] as: where x i and y i are the elements (taken as multiset multiplicities) of the trees X and Y , understood to correspond to the vectorization of the respective adjacency matrices representing the two trees to be compared, as illustrated in Figure 3.
Observe that 0 ≤ I(X, Y ) ≤ 1. The Jaccard index as a measurement of similarity between two multisets (e.g. [30]) X and Y can be expressed as: with 0 ≤ J (X, Y ) ≤ 1, so that 0 ≤ C(X, Y ) ≤ 1. Observe that an adapted version of the above equation [8,7] would be required in case the features can take negative values.
The coincidence similarity index has been found to implement a particularly strict quantification of the similarity between any two mathematical structures [8,31], being successfully applied for translating datasets into respective networks (e.g. [9,32,33]). Another advantage of adopting the coincidence similarity in the present work is that it will immediately apply in cases involving hierarchies with weighted links, in addition to the binary connections characterizing the present approach.

Methodology
In this section we present the simple method for generating hierarchies as well as characterize the problem of reconstructing hierarchies as developed in the current work.

A Simple Model for Generating Hierarchies
In order to synthesize trees having N nodes with varying properties, we developed a mathematic-computational model that requires just one parameter γ, which controls how branched the trees.
After fixing N and γ, new elements are incorporated in a specific order, and each new element links only to one of the existing nodes in the hierarchical tree. The connection of the new element with some of the already existing nodes, indexed by i, is done randomly with the connection probability specified as: where k i is the number of links of the element i and h i is its level in the hierarchy (with the hierarchical level starting in 0). Figure 4 illustrates the above probabilities respectively to γ = −1 (a) , 0 (b) , and −1 (c). Figure 5 shows examples of hierarchical structures generated by the proposed model for N = 20 and different values of γ between −3 and 3. Observe the progression from more linear trees obtained for the smaller values of γ to more intensely branching observed for the larger values of γ. After the hierarchy has been obtained by using the method described above, it is necessary to associate respective features to each node, so that it becomes possible to link nodes based on the similarity between these features [34]. In order to do so, we start with a set A with m features: A = [a 1 , a 2 . . . a m ], where a i are integer values. Each element will receive n (with n < m) aleatory features, with nβ of them coming from set A and n(1 − β) coming from its parent in the hierarchy tree. The rate β (with 0 ≤ β ≤ 1) determines the mix of features between the elements in this model.
Observe that, as a consequence of the method adopted for incorporating features (content) into each node, these nodes will result similar to the parent node from which they derive (one hierarchy higher), but still remaining partially distinct among themselves. In other words, each node has a portion of its features shared with the node from which its derived, while the remainder portion is specific to itself. This property is coherent with the concept of hierarchies, in which child nodes inherit properties, but also have specific distinguishing features (e.g. [34]), making each of them a specific non-exchangeable entity. Figure 6 depicts three important topological properties of trees generated by the proposed method respectively to several values of γ. The total number of nodes is henceforth kept fixed as N = 15.
Regarding the number of hierarchical levels H - Figure 6 (a), which is among the most important property of a tree, a gaussian-like distribution can be observed respectively to each of the considered parameters configurations. The most frequent value of H (abscissa of the density peaks) decreases steadily with γ. This is a direct consequence of the fact that as more branches per level are favored by larger values of γ, the number of levels tends to decrease so as to keep N constant (see Figure 5). At the same time, and for similar reasons, the width of the obtained densities also tends to decrease.
The average number of nodes per hierarchical level n h , shown in Figure 6 (b), also presents a gaussian-like profile respectively to each value of γ. Contrariwise to the number of hierarchical levels, the most frequent values of n h , as well as the respective width, tend to increase with γ. This tendency is accounted for by the fact that more nodes are incorporated at each level for larger values of γ, while N is kept fixed.
The distribution of the number of nodes per level, shown in Figure 6 (c), resembles log normal-like profiles, with the peak abscissa positions and the distribution widths both decreasing with γ.
In case tree configurations more specific than can be controlled by the parameter γ, i.e. with less variance of properties are required, it is possible to incorporate a filtering stage after the generation of the trees, to select only the tree configurations with properties (e.g. H or n h ) falling within specified intervals.

Reconstruction of Hierarchies
In this work, we study how the accuracy in the reconstruction of the hierarchical trees varies for different sampling orders. In this process, we considered the coincidence index between the adjacency matrices of the original and reconstructed trees in order to quantify the reconstruction accuracy. Figure 2 illustrates the adopted procedure for reconstructing the hierar- chies considering diverse sampling orders of the elements. The tree is reconstructed, one element at a time, defining its position in the hierarchy by connecting to the most similar element already existing in the network. In order to sample the nodes from the original tree, we select a fraction p of the elements to be dislocated by δ positions around its initial positions.
After these reconstructions have been obtained, we can compare it with the original hierarchy tree by using the coincidence similarity index between the adjacency matrices respective to those two graphs. Figure 7 illustrates an original hierarchy, corresponding to the tree on the left-hand size, and four respective reconstructions with decreasing accuracy. The adjacency matrices respective to each tree are also presented respectively in the figure. The first reconstruction (top) is exact, being characterized by C = 1.0. Three additional reconstructions with increasing errors, therefore implying in successively smaller values of C. It is interesting to observe that the finite number of nodes in the considered trees implies a discretization of the possible values of C to be obtained. In this case, with 7 nodes, we have only 6 links, so that any node change implies a relatively large change inaccuracy. The number of discrete coincidence values increases steadily with the number of nodes so that a substantially better resolution is obtained for the N = 15 nodes adopted for the experimental results in the present work.

Results and Discussion
In this section, we report the results and corresponding discussions regarding the accuracy while retrieving hierarchies in the presence of sampling order errors with probability p and extent δ. The types of hierarchies, in the sense of the number of involved levels and nodes per level, are specified by the parameter γ of the proposed model. More specifically, we start with a tree generated by the model for varying values of γ, which is understood as the original tree to be retrieved. Then, each of the nodes of this tree is sampled in a specific order, in presence of errors controlled by p and δ. Statistics of the obtained errors, as quantified by the coincidence similarity index for non-negative values are then obtained, presented, and discussed. Figure 8 presents the relative frequency of the coincidence similarities obtained for several configurations of the parameters p and γ. It is interesting to observe that only the similarity values corresponding to the discrete points marked along the curves were experimentally obtained, being interpolated only for the sake of enhanced visualization and comparison between the obtained profiles.
For the smallest value of p, i.e. p = 0.1, we observe high values of similarity for every adopted δ and γ. This means that accurate reconstructions of the original hierarchies were often obtained for this probability error, with a peak near 100%. However, it is important to keep in mind that relatively large reconstruction errors (i.e. small coincidence similarity values) can be obtained, though less likely, even for this small probability error. Interestingly, the curves obtained for the different values of δ are mostly similar, except for that respective to δ = 1.
For the other considered probability values p, the peaks of the curves obtained for δ = 1, 2, 3, 4 tend to shift from the left to right, indicating a monotonic decrease in the tree reconstruction accuracy. At the same time, for each fixed value of δ, the coincidence curve also tends to shift from right to left as p is increased, or γ is decreased. Figure 9 presents the average, mode, and standard deviation of the coincidence values obtained for reconstructions considering N = 15 and δ = 1, 2, 3, 4 respectively to γ = −1, 0, 1 and p = 0.0, 0.1, 0.2, 0.3, 0.4, 0.5.
All three measurements can be verified to vary markedly with p. Relatively moderate differences can be observed between the average and standard deviation curves obtained respectively to the considered δ andγ values, except for a larger decay ratio observed for larger values of δ verified in these two cases. Interestingly, the mode values present a stronger dependence on γ and δ. Generally speaking, it could be concluded that the mode of the obtained coincidence similarity indices vary with δ, γ, and p, while the average and standard deviation are substantially less dependent on δ and γ.
Another interesting result concerns the fact that the largest decrease of average coincidence is observed, in all considered cases, along with the smallest values of p, tending to become substantially smaller for larger values of p. This type of effect, related to the sensitivity of the average of the obtained coincidence values, can be approached objectively in terms of the derivative of this measurement with respect to p. Figure 10 depicts this sensitivity with respect to γ = −1, 0, 1 and δ = 1, 2, 3, 4. This result tends to corroborate the above observation that relatively larger variations of the average reconstruction accuracy are obtained for the smallest values of p, decreasing as the latter parameter is increased.   Figure 10: The sensitivity of the variation of the average reconstruction accuracy for γ = −1, 0, 1 and δ = 1, 2, 3, 4 in terms of the error probability p, as quantified by the absolute value of the derivative of the average coincidence values with respect to the error probability p is substantially higher for small values of p, decreasing markedly as p is increased.

Concluding Remarks
Several real-world structures and phenomena are characterized by respective hierarchical organization, to the point of being typically represented by respective trees. Examples of these situations include vascularization, neuronal cells, archaeological chronology, and phylogenetics, among many other possibilities. Even in structures not corresponding directly to trees, methods have been proposed to derive a respective hierarchical summarization, such as the minimal spanning tree (e.g. [1]).
In practice, the acquisition of these structures often proceeds by sampling the tree nodes in a given order. The sampled nodes are often appended to the currently available nodes while considering the similarity of their respective properties or features. Given that the sampling order may not correspond to that originally characterizing the hierarchy, substantial errors can be verified in the respectively reconstructed structures.
The present work focused on characterizing and studying the effect of the sampling order of hierarchical structures and phenomena respectively to several involved parameters, including the probability of error (p), the error extent (δ), as well as the branching level of the respectively reconstructed structures (γ).
In order to allow a systematic experimental investigation of the effect of these parameters on the obtained reconstruction errors, we developed a simple model for generating trees with varying branching levels, which are controlled by the parameter γ. The trees constructed by this tree generating model were characterized by respective properties including the distributions of the number of hierarchical levels and the number of nodes per level. It has been verified that quite diverse types of trees can be obtained by the proposed model by varying its single parameter γ. In addition to enabling the present study, this same model can be employed in several other applications.
The comparison between the original and reconstructed trees was quantified in terms of the coincidence similarity, which tends to provide a particularly strict quantification of the similarity between generic mathematical structures including the adjacency matrices used to represent the trees.
Several interesting results have been obtained and discussed. These include the fact that, at least for the adopted parameter configurations and types of hierarchies, the reconstruction average accuracy varied relatively little with respect to both δ and γ, but decreased monotonically with p. The mode of the coincidence values, however, presented a stronger variation with δ and γ. In other words, retrieving hierarchies, as seen from the respective average and standard deviation of the obtained accuracies quantified by the respective coincidence values, is more critical on the probability error p than on the type of hierarchy (indexed by γ) or the extent of the sampling order error δ. In addition, the relative variation of the accurac (sensitivity) was found to be substantially larger for smaller values of p, decreasing substantially for larger respective values.
The reported concepts, methods, and results paved the way for several related developments. To begin with, the proposed simple method for generating hierarchies with varying properties by using a single parameter can be adopted in several alternative problems and studies. Also worth investigating is the possibility of using alternative probability formulas dependent on h and k as the means for obtaining less overlap between trees respectively to distinct parameter configurations. Concerning the study of the reconstruction of hierarchies by sampling nodes, it would be interesting to study other types of sampling schemes and respective errors, as well as adopting other approaches for defining the respective features.