# Proportion of spanning trees in a network in a social media messaging context

Consider a graph, such as the following:

I'm considering a model of message propagation (e.g. re-tweeting) in this network, starting from a root node (e.g. the node 1 in the lower-left). I'm modelling the message propagation in terms of trees rooted at the message source, where a node v is a parent to another node w if w first hears the message from v.

• The message propagates outward from 1, in a tree which "grows" in an iterative process. In this process, nodes which have been reached are either branching nodes (i.e. are the parent of some other node), live leaves (nodes which may become branch nodes), or dead leaves.
• Initially, all the neighbors of node 1 are children of 1, and are live leaves.
• The message propagates by iterations, as follows. We consider an arbitrary ordering L = (ℓ1, ..., ℓn) of the live leaves at the beginning of the iteration. For each 1 ≤ j ≤ n, we do the following:

1. Decide whether the node ℓj dies (doesn't propagate the message) or becomes a branch node (propagates the message). If all of the nodes adjacent to ℓj are already in the tree, then it dies by default.
2. If ℓj becomes a branch node, we attach every neighbor v of ℓj which is not already in the tree to ℓj, as a live leaf node for the following iteration.

After iterating through the elements of L, we proceed to the next iteration.

• If there are no more live leaves in the tree, we stop.

For the graph above, here are the trees that may be generated by this process:

I'm interested in considering how many of the trees which can be generated by this process are spanning trees, i.e. contain every node in the graph. Is there any formula to determine the ratio of the spanning trees to the total number of such trees?

N.B. The construction above is similar to a Galton-Watson process. However, there isn't meant to be a probabilistic model underlying the growth; the above is meant only to implicity describe a recursive process to recognise whether a subtree in the graph is valid in my model. I've added the probability tag just in case there is a useful approach from that direction.

Thanks!

-
These aren't paths, these are spanning trees. –  Ricky Demer Aug 25 '11 at 9:00
@Ricky: Not all of them are spanning trees of the original graph. It appears that Nicola wants all subtrees $T$ of the graph that include $1$ and have the property that if $v$ is a vertex of $T$, and $vw$ is an edge of $T$ that does not lie on the unique path in $T$ from $1$ to $v$, then $T$ contains all edges adjacent to $v$. (Probably he’d also like to be able to do this with any other vertex as root.) –  Brian M. Scott Aug 25 '11 at 9:58
@Nicola G: only the four trees in the bottom row are "spanning trees": a spanning tree must cover all vertices. The second image describes a collection of subtrees of the original graph, constructed according to some rule which is possibly implicit in your post but which is not clear. (If both 2 and 3 publish – or maybe retweet – something, why do you not get all of the edges 1-2, 1-3, 2-4, 3-4?) –  Niel de Beaudrap Aug 26 '11 at 10:01
@Nicola G: I've revised your question so that it describes what it is that you are interested in. Please check to see whether it agrees with what you want to know! –  Niel de Beaudrap Aug 27 '11 at 14:36
One could try working backwards: Start with all rooted trees on $n$ vertices and then add edges to get graphs G on $n$ vertices such that the rooted tree you started with is a valid endpoint of the algorithm applied to G. Count the number of possible Gs with duplication $(=f(n))$. Then try and generate $n$-vertex graphs G from $k$ vertex trees. Count the number of possible Gs with duplication $(=g(n,k), f(n) = g(n,n))$. Probability is then $f(n) / \sum_k g(n,k)$. –  Craig Sep 6 '11 at 14:48

Okay, taking a second stab at this. Same overall technique, hopefully I can count better this time.

We start with our root node, labeled '1'. We add nodes 2 through k in succession. The labels are intended to correspond to the order in which we choose them when running the algorithm. The leaves of the tree are the nodes which are "dead". We can attach each node to any of the nodes we have already placed, leading us to the conclusion that we have $(k-1)!$ labeled $k$-node trees where each node's parent has a smaller label than the node does. We will associate each tree with the sequence of parents $\{ 1 =p(2), p(3), ... p(k) \}$ where $p(j) \in [1,...,j-1]$.

We are then going to add nodes and edges to complete this to a graph $G$ that can give this tree as a result of the algorithm above. For the $(n-k)$ nodes that are not in the tree, we label them (all labelings are equivalent at this point), then we can connect them to the leaves of the tree and we can connect them to each other, leading to $e_1(l;n-k) = (n-k)*l + (n-k)C2$ possible edges for $l$ leaves.

Now to count within-tree edges. A node $i$ can be connected to a node $j+1 > i$ in the graph $G$ if one of three (mutually exclusive) conditions holds: 1) $i$ is the parent of $j+1$ in the tree ($i=p(j+1)$), 2) $i$ is greater than $p(j+1)$, or 3) $i$ is a leaf and $i$ is less than $p(j+1)$.

This is very difficult to count. It is best to note, however, that the within-tree edges are independent of $n$, and so we can count them once for any given tree.

Let $T_k$ be the set of labeled $k$-node trees as above and $T_{k,l}$ be the set of labeled $k$-node trees with $l$ leaves. Given a tree $t$ in $T_{k,l}$, let $e(t)$ be the number of edges one can add to $t$ consistent with $t$ being a potential outcome of the algorithm run on the resulting $k$-node graph. We note that since one may freely connect each leaf to every other leaf, $e(t) \geq lC2$. We will then define a polynomial

$t_k(x) = \sum_{l=1}^{k-1} \left( \sum_{t \in T_{k,l}} 2^{e(t)} \right) x^l$.

The coefficient of $x^l$ is the number of ways one may complete $k$-node, $l$-leaf trees to a $k$-node graph consonant with the algorithm. By definition, this coefficient is divisible by $2^{lC2}$.

The first few $t_k(x)$ are as follows (I think):

$\begin{array}{c} t_2(x) = x \\ t_3(x) = x + 2x^2 \\ t_4(x) = x + 14x^2 + 8x^3 \\ t_5(x) = x + 70x^2 + 264x^3 + 64x^4 \end{array}$

It is not immediately obvious that there is a recursion relation for these polynomials. One might hope that since adding a node to a $k$-node, $l$-leaf tree gives either a $(k+1)$-node, $l$-leaf tree or a $(k+1)$-node, $(l+1)$-leaf tree, that one could find a recursion relation for $[x^{l+1}]$ in $t_{k+1}(x)$ in terms of $[x^l]$ and $[x^{l+1}]$ in $t_k(x)$. I have not yet found such a relation.

Why do we care about these polynomials in the first place? It's fairly simple: given the dependence of $e_1(l;n-k)$ on $l$, the number of ways to complete $k$-node trees to an $n$-node graph is $2^{(n-k)C2} * t_k(2^{n-k})$. To get the number of ways to run the algorithm on the set of $n$-node graphs, one simply sums this quantity over $k$. And of course, the number of algorithm runs that result in a spanning tree is $t_n(1)$.

Update: I believe I have found a recursion for the coefficients of $t_k(x)$. I do not yet have the coefficients in closed form. This recursion requires us to divide up the set $T_{k,l}$ of $k$-node, $l$-leaf trees further.

For a given $(k+1)$-node, $(l+1)$ leaf tree $t$, we will consider the last non-leaf node (say it has label $a$), and any leaf of said non-leaf node (say it has label $b$). We then remove said leaf, and decrement the labels of all the later leaves. The resulting tree, $t'$, has $k$ nodes and either $l$ or $l+1$ leaves, depending on whether $a$ had more than one leaf in $t$. This map is not a function, as we can choose $b$ arbitrarily if $a$ has more than one node, but for now we will pretend it is a function. We will call this map $f: T_{k+1,l+1} \rightarrow T_{k,l} \cup T_{k,l+1}$.

If $a$ had more than one leaf in $t$, we find that $e(t) = e(t') + l$. If $a$ only had $b$ as a leaf in $t$ (so that $a$ itself is a leaf in $t'$), then we find that $e(t) = e(t') - (k-a) + l$. These equations are not difficult to verify.

We now divide up our set $T_{k,l}$ into sets $T_{k,l,m,q}$, where $k$ is the number of nodes in the tree, $l$ is the number of leaves, $m$ is the label of the last non-leaf node and $q$ is the number of leaves on node $m$. We let

$c_{k,l,m,q} = \sum_{t' \in T_{k,l,m,q}} 2^{e(t')}$

be the number of ways to reconstruct a $k$-node graph from trees in $T_{k,l,m,q}$.

We are now going to attempt to invert $f$ on $T_{k,l,m,q}$. We can either add a leaf to the non-leaf node $m$, giving a tree $t$ in $T_{k+1,l+1,m,q+1}$, or we can add a leaf to a leaf node $m' > m$, giving a tree $t$ in $T_{k+1,l,m',1}$. In each case, we need to consider what label we are going to assign to the new leaf (and we increment all the labels after the new label), and how $e(t)$ is related to $e(t')$.

In the latter case, $e(t) = e(t') - (k-m') + l$ and we have $(k+1-m')$ choices for the label of the new leaf. In the former case, $e(t) = e(t') + l$, and we have $(k+1-m)$ choices for the label of the new leaf. We point out that in this case, every tree $t$ in $T_{k+1,l+1,m,q+1}$ has $(q+1)$ not-necessarily-distinct images $t'$ under $f$, but all have the same value of $e(t')$ (this last fact is not too difficult to prove).

We therefore find the following recurrences:

$c_{k+1,l,m',1} = (k+1-m') * 2^{l +m' - k} \sum_{m<m'} \sum_{q} c_{k,l,m,q}$

$c_{k+1,l+1,m,q+1} = \frac{k+1-m}{q+1} * 2^l c_{k,l,m,q}$.

Boundary conditions on these recurrences are as follows:

$c_{k,l,m,q} = 0$ if $l\geq k$ or $q>l$ or $m+q>k$

$c_{l+1,l,1,l} = 2^{lC2}$

The coefficients of the polynomial $t_k(x)$ are $[x^l] = \sum_{m,q} c_{k,l,m,q}$.

-

Taking a stab at this based on my comment. We start with a k-vertex, rooted tree . We wish to add vertices and edges to get an n-vertex rooted graph G such that applying your algorithm to G can end at the k-vertex tree we started with.

So suppose that the tree has depth d, and that at each level i of the tree there are $n_i$ nodes of which $l_i$ are leaves. We have in particular

$\sum_{i=1}^d n_i = k-1$, $n_i \geq l_i$, $n_d = l_d$, and $n_{i+1} \geq n_i-l_i$

and we will set $n_0 = 1$ for convention.

How many such trees are there? Then after we place the first $j$ levels of nodes, there are $n_j C l_j$ ways of picking which level-j nodes are leaves and $(n_{j+1}-1)C(n_j - l_j - 1)$ ways of placing the depth-$(j+1)$ nodes. Many of these placements are isomorphic, but if we assign a labeling to the tree (as we will do later), they are distinguishable. So the total number of $k$-vertex trees of depth $d$ is

$\sum_{l_i, \sum n_i = k-1} \prod_{i=1}^d (n_i-1)C(n_{i-1} - l_{i-1} -1) * n_i C l_i$ $= \sum_{\{ n_i \}} \prod_{i=1}^{d-1} (n_i+n_{i+1}-1) C (n_i -1)$

where trees with a given sequence of $n_i, l_i$ correspond to a single term in the sum on the first line.

We then want to label the tree with labels from $[2,...,n]$. There are $(n-1)! / (n-k)!$ ways of doing so (the root gets the special label 1).

Now, given such a tree, in how many ways can we invert the algorithm to get a n-vertex graph G? Well, we will first distinguish edges between two vertices on the tree, and edges incident to (at least one of) the $(n-k)$ remaining vertices. The $(n-k)$ remaining vertices are free to connect to each other and to any leaf on the tree, for $e_1 = (n-k)C2 + (n-k)*\sum_i l_i$ potential edges. Any given vertex on the tree can be connected to a leaf at a lesser depth -- it is not difficult to see that this exhausts all possible edges that can be added to the tree when we invert the algorithm. That gives $e_2 = \sum_i n_i \sum_{j<i} l_j$ possible edges. So the number of n-vertex graphs that can give this tree as output is $2^{e_1 + e_2}$.

We can combine these two formulas to get $g(n,k)$. I can't figure out how to evaluate this exactly at this point, but it is readily calculable for small $n,k$.

Once we've done this, we can compute the average proportion of algorithm outputs that are spanning trees. (Notice that I did not require that my graph G was connected to begin with -- obviously no disconnected graph will give rise to a spanning tree).

-
Okay, I inverted the algorithm incorrectly. The correct way of inverting the algorithm would impose a labelling on the tree where each node has a label in $[2,...,k]$ and every child has a label greater than its parent. Then $e_1$ is defined correctly, but counting the within-tree edges would involve 1) connecting from a node with label i to non-leaf nodes with labels in $(p(i),i)$, where $p(i)$ is the label of the parent of node $i$ and also 2) connecting to leaf nodes $j$ with $j<i$. Not sure how to count these. –  Craig Sep 8 '11 at 20:31
What is the big C? –  graphtheory92 Sep 9 '11 at 14:02
"Choose" -- it's the binomial coefficient. –  Craig Sep 9 '11 at 15:26
FYI, I'm working on a slight variant of my counting argument, which will hopefully lead to some more concrete results. It involves an interesting set of polynomials $T_k(x)$ (of degree $k-1$), where the $l$th coefficient of $T_k(x)$ is the number of ways to invert the algorithm on a $l$-leaf, $k$-node labeled tree to a $k$-vertex graph (or conversely the number of ways to run the algorithm on a $k$-vertex graph to get an $l$-leaf spanning tree). –  Craig Sep 9 '11 at 15:30
Yes, leaves of the tree are the "dead" nodes. The counting method I used was supplanted by the one in the other answer, but I'll explain what I was doing here. That sum is attempting to count the number of $k$-vertex trees of depth $d$ by looking at the number of nodes ($n_i$) and leaves ($l_i$) at any given depth $i\leq d$. We have that the total number of nodes is $k-1$, not counting the root. We also have that $l_i \in [n_i - n_{i+1},n_i]$. The summation is over all sets of $n_i, l_i$ satisfying these constraints. The product counts the number of ways to construct a tree with those –  Craig Sep 10 '11 at 23:03