3
$\begingroup$

So I am working on a problem where I have a set of (labeled) nodes and I have a tree structure (rooted) over that set of nodes. The goal for me is to automatically generate that tree structure. To find the performance of my algorithm, I am trying to use the score as the fraction of edges that I have common in the generated tree and the given tree. I want to compare this score with an expected value of the fraction if we generate the tree randomly (equal probability for all tree structures). What should be my approach to find this? Is there a computable efficient method for this? The brute force method (with some optimizations so that I only iterate on the structure without the labels) usually fails over n>10.

I understand if there is some efficient method to find no. of trees with k common edges then my problem is solved to much extent, but I am having a hard time to solve this as well.

EDIT: The edges are considered to be directed, towards the root.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Does the tree have any meaning? Is it given as part of the input? I'm not sure I understand the computational problem you are trying to solve. Can you specify input and output more precisely? $\endgroup$ – Raphael♦ Jan 14 '16 at 14:00
  • $\begingroup$ @Raphael Yes, it is a machine learning approach, so the tree is given as the input which we have to predict. The problem is related to argumentation mining where the arguments are assumed to be tree structured. $\endgroup$ – arkanath Jan 15 '16 at 4:48
2
$\begingroup$

Let $T$ be your reference tree (on $n$ vertices), and let $R$ be the random tree. Label the edges of the tree randomly from $1$ to $n-1$. Let $X_i$ denote the event that the $i$th edge of $R$ is an edge of $T$. Linearity of expectation shows that the expected size of $T \cap R$ is $\sum_i \Pr[X_i]$. Each $X_i$ is a uniformly random edge, and so it belongs to $T$ with probability $|T|/\binom{n}{2} = 2/n$. Hence the expected size of the intersection is $(n-1) \cdot 2/n = 2(1-1/n)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer, I forgot to mention in the question, the edges are considered to be directed, with the edges directed towards the root. How will the answer change in this? will it be (n-1)/n, giving the expected fraction as 1/n ? $\endgroup$ – arkanath Jan 14 '16 at 10:23
  • $\begingroup$ I'll let you figure that out yourself, using the same technique. $\endgroup$ – Yuval Filmus Jan 14 '16 at 10:26
  • $\begingroup$ @calmyoursenses Yea, I edited the question after the answer. 1/n sounds correct to me. $\endgroup$ – arkanath Jan 14 '16 at 10:43

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.