<p>First, Yixin Cao's comment that similarity is problem-specific is <em>entirely correct</em>. It doesn't make sense to talk about trees being similar or not, without having an idea of what you are trying to compute. </p>

<p>That caveat aside, it is indeed very common to equip trees with metrics. One of the most common is to equip them with an ultrametric, where we define a distance function on trees:</p>

<p>$$d(t_1, t_2) = 2^{-n}$$ </p>

<p>where $n$ is the first level at which the branching structure of $t_1$ and $t_2$  differ. This is a generalization of the Cantor metric for sequences, where two strings have a distance of $2^-n$ where $n$ is the first position at which they differ. </p>

<p>The intuition behind this is a temporal one -- we think of a sequence as representing a series of events, and we want to say that two series are more similar the longer we have to wait to distinguish them. When we move from sequences to trees, it's a bit like moving from a linear model of time to a branching model of time. Trees with this kind of ultrametric are, IIRC, used a lot in phylogenetics, where they are called dendrograms, and used to work out possible lineages for species. </p>

<p>Another important metric on sequences is the Levenshtein distance, or edit distance. This measures the number of edits you have to make to change one string into another one. Generalizing this to trees gives you what is unsurprisingly called a "tree edit distance". Here's a survey by Phillip Bille on tree edit distances:</p>

<ul>
<li><a href="http://www.sciencedirect.com/science/article/pii/S0304397505000174" rel="nofollow">A survey on tree edit distance and related problems</a>, Philip Bille. <em>Theoretical Computer Science</em>, 2004. </li>
</ul>

<p>These tree edit distances are used for problems like detecting plagiarism in student source code, or diff algorithms for HTML and XML. </p>

CC BY-SA 3.0
2012-06-23T12:15:26.520Z
Thanks for your answer. Year, I'm working on the relationship between information propagation in networks and the network topology, then this question came into my mind naturally. How to define 'similarity' is the key to this question and I indeed want to know some related work which I'm unfamiliar with. The information you provided is very useful. Can you provide any survey or relevant papers for the first method?
zenos
CC BY-SA 3.0
2012-06-24T10:51:44.707Z
Unfortunately not. I've looked at ultrametrics in the semantics of programming languages (via the connection to temporal logic), and only have a casual acquaintance with their use in algorithms.
Neel Krishnaswami
CC BY-SA 3.0
2012-06-23T10:01:09.610Z
2012-06-23T10:01:09.610Z
Neel Krishnaswami
<p>Consider a set of trees $T=\{T_{\alpha}\}$, and for any $T_{\alpha}\in T$, $T_{\alpha}$ has $n$ nodes. Can we find a ‘characteristic’ function $f:T\longmapsto{\mathbb{R}}$ describing trees' topological feature? That is to say, $T_{\alpha}\simeq T_{\beta}$ only and if only $f(T_{\alpha})=f(T_{\beta})$, and if $T_{\alpha}$ is more similar to $T_{\gamma}$ than $T_{\beta}$ is, then $|f(T_{\alpha})-f(T_{\gamma})|&lt;|f(T_{\beta})-f(T_{\gamma})|$.</p>

<p>It seems that $f$ is a topological invariant of $T$ and this is a very natural thought. I'm not much familiar with graph theory and I'm wondering if someone has considered this problem before. There are two aspects about this problem, one is such $f$ exists, and another is how to calculate $f$， or what the algorithm is.</p>

CC BY-SA 3.0
2012-06-22T16:36:33.567Z
Since two trees can differ only in 1 node, it follows that such a function must have as an argument the entire tree structure. If we restrain ourselves to n-ary trees, for $n \geq 2$ any algorithm's output , like postfix, can be used to describe the tree structure. I assume that someone experienced in information theory could prove that a function like the one you would need a great (exponential in terms of depth) number of bits to be described.
chazisop
CC BY-SA 3.0
2012-06-22T18:05:22.347Z
@Zenos I'm not sure what you mean by "To determine whether two trees are isomorphism is conjectured to be NP-hard" - this can be done in poly time.
Suresh Venkat
CC BY-SA 3.0
2012-06-22T19:26:20.000Z
@Suresh: in linear time :)
Marzio De Biasi
CC BY-SA 3.0
2012-06-22T19:37:42.700Z
Or log space, if you prefer that over linear time.
Robin Kothari
CC BY-SA 3.0
2012-06-23T03:00:06.037Z
_...if $T_α$ is more similar to $T_γ$ than $T_β$ is..._ — What _exactly_ do you mean by "more similar"?
Jeffε
CC BY-SA 3.0
2012-06-23T03:24:10.983Z
@JɛﬀE: Sorry, there is something wrong with my account...Yes, it needs one definition for 'similar'. We may first think about the number of layers, then the number of nodes and the distribution of branches in each layer.
zenos
CC BY-SA 3.0
2012-06-23T05:07:34.287Z
@Zenos: That's not a definition.  Of course, you could always _define_ the similarity function to be $|f(T) - f(T')|$ where $f$ is your favorite topological invariant, but that's neither interesting nor useful.
Jeffε
CC BY-SA 3.0
2012-06-23T06:40:32.770Z
This question is not well defined and the measure of "similarity" is very application-oriented.  For example, sometime all path graph are considered similar, that means a tree of two vertices and a long path of 1,000,000 vertices are similar, while some will consider the number of vertices matters.
Yixin Cao
<ds.algorithms><graph-theory><co.combinatorics><tree><topology>
Is there a characteristic function of a tree?
zenos
# Is there a characteristic function of a tree?

(Asked by: username_0 on 2012-06-22)

Consider a set of trees $T=\{T\_{\alpha}\}$, and for any $T\_{\alpha}\in T$, $T\_{\alpha}$ has $n$ nodes. Can we find a ‘characteristic’ function $f:T\longmapsto{\mathbb{R}}$ describing trees' topological feature? That is to say, $T\_{\alpha}\simeq T\_{\beta}$ only and if only $f(T\_{\alpha})=f(T\_{\beta})$, and if $T\_{\alpha}$ is more similar to $T\_{\gamma}$ than $T\_{\beta}$ is, then $|f(T\_{\alpha})-f(T\_{\gamma})|<|f(T\_{\beta})-f(T\_{\gamma})|$.

It seems that $f$ is a topological invariant of $T$ and this is a very natural thought. I'm not much familiar with graph theory and I'm wondering if someone has considered this problem before. There are two aspects about this problem, one is such $f$ exists, and another is how to calculate $f$， or what the algorithm is.

**Tags:** ds.algorithms, graph-theory, co.combinatorics, tree, topology
> **Comments:**
> **username_1**: Since two trees can differ only in 1 node, it follows that such a function must have as an argument the entire tree structure. If we restrain ourselves to n-ary trees, for $n \geq 2$ any algorithm's output , like postfix, can be used to describe the tree structure. I assume that someone experienced in information theory could prove that a function like the one you would need a great (exponential in terms of depth) number of bits to be described.  
> **username_2**: @Zenos I'm not sure what you mean by "To determine whether two trees are isomorphism is conjectured to be NP-hard" - this can be done in poly time.  
> **username_3**: @Suresh: in linear time :)  
> **username_4**: Or log space, if you prefer that over linear time.  
> **username_5**: _...if $T_α$ is more similar to $T_γ$ than $T_β$ is..._ — What _exactly_ do you mean by "more similar"?  
> **username_0**: @JɛﬀE: Sorry, there is something wrong with my account...Yes, it needs one definition for 'similar'. We may first think about the number of layers, then the number of nodes and the distribution of branches in each layer.  
> **username_5**: @Zenos: That's not a definition.  Of course, you could always _define_ the similarity function to be $|f(T) - f(T')|$ where $f$ is your favorite topological invariant, but that's neither interesting nor useful.  
> **username_6**: This question is not well defined and the measure of "similarity" is very application-oriented.  For example, sometime all path graph are considered similar, that means a tree of two vertices and a long path of 1,000,000 vertices are similar, while some will consider the number of vertices matters.  

---

## 1 answers

### Answer by username_7 on 2012-06-23. Score: 4

First, Yixin Cao's comment that similarity is problem-specific is *entirely correct*. It doesn't make sense to talk about trees being similar or not, without having an idea of what you are trying to compute.

That caveat aside, it is indeed very common to equip trees with metrics. One of the most common is to equip them with an ultrametric, where we define a distance function on trees:

$$d(t\_1, t\_2) = 2^{-n}$$

where $n$ is the first level at which the branching structure of $t\_1$ and $t\_2$ differ. This is a generalization of the Cantor metric for sequences, where two strings have a distance of $2^-n$ where $n$ is the first position at which they differ.

The intuition behind this is a temporal one -- we think of a sequence as representing a series of events, and we want to say that two series are more similar the longer we have to wait to distinguish them. When we move from sequences to trees, it's a bit like moving from a linear model of time to a branching model of time. Trees with this kind of ultrametric are, IIRC, used a lot in phylogenetics, where they are called dendrograms, and used to work out possible lineages for species.

Another important metric on sequences is the Levenshtein distance, or edit distance. This measures the number of edits you have to make to change one string into another one. Generalizing this to trees gives you what is unsurprisingly called a "tree edit distance". Here's a survey by Phillip Bille on tree edit distances:

* [A survey on tree edit distance and related problems](http://www.sciencedirect.com/science/article/pii/S0304397505000174), Philip Bille. *Theoretical Computer Science*, 2004.

These tree edit distances are used for problems like detecting plagiarism in student source code, or diff algorithms for HTML and XML.

> **Comments:**
> **username_0**: Thanks for your answer. Year, I'm working on the relationship between information propagation in networks and the network topology, then this question came into my mind naturally. How to define 'similarity' is the key to this question and I indeed want to know some related work which I'm unfamiliar with. The information you provided is very useful. Can you provide any survey or relevant papers for the first method?  
> **username_7**: Unfortunately not. I've looked at ultrametrics in the semantics of programming languages (via the connection to temporal logic), and only have a casual acquaintance with their use in algorithms.  

---

