10
$\begingroup$

Consider a graph, such as the following:

Entire graph

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:

Possible trees

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!

  • 1
    These aren't paths, these are spanning trees.2011-08-25
  • 2
    @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.)2011-08-25
  • 0
    Are you looking for an algorithm to generating these subtrees, or do you want to be able to count them?2011-08-25
  • 0
    @Brian, you got it! I'm sorry if my maths languages wasn't clear. I would like to count the number of possible generable subtrees, therefore "count them"2011-08-25
  • 0
    @Brian: I interpreted the first 3 rows as being used to find the 4th row.2011-08-25
  • 0
    The second image is to show that from that graph, there are 9 possible spanning trees2011-08-25
  • 1
    @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?)2011-08-26
  • 0
    you should try to investigate the graph theory (strictly related to probability theory) but I'm not sure you can find reliable information in Internet. You should read specific math books.2011-08-26
  • 0
    @niel, ok I know the last row are spanning trees. Imagine the retweet world, the last graphs are the best case for a retweeted content. Imagine 3 or 2 don't retweet, the tweet will not reach everybody, so I want to count how many probabilities (so how many trees) the retweet can generate and at the end, do a proportion between max number of possible trees and number of spanning trees.2011-08-27
  • 2
    @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!2011-08-27
  • 0
    Thanks so much niel it is perfectly the question i was asking!2011-08-28
  • 1
    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)$.2011-09-06

2 Answers 2