0
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ @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. $\endgroup$ – Suresh Venkat Jun 22 '12 at 18:05
  • 3
    $\begingroup$ @Suresh: in linear time :) $\endgroup$ – Marzio De Biasi Jun 22 '12 at 19:26
  • 3
    $\begingroup$ Or log space, if you prefer that over linear time. $\endgroup$ – Robin Kothari Jun 22 '12 at 19:37
  • 3
    $\begingroup$ ...if $T_α$ is more similar to $T_γ$ than $T_β$ is... — What exactly do you mean by "more similar"? $\endgroup$ – Jeffε Jun 23 '12 at 3:00
  • 2
    $\begingroup$ @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. $\endgroup$ – Jeffε Jun 23 '12 at 5:07
4
$\begingroup$

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:

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – zenos Jun 23 '12 at 12:15
  • $\begingroup$ 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. $\endgroup$ – Neel Krishnaswami Jun 24 '12 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.