Proporción de atravesar árboles en una red en un contexto de mensajes de los medios de comunicación social

Question

Considere la posibilidad de un gráfico, como el siguiente:

Estoy pensando en un modelo de propagación de mensajes (por ejemplo, re-twittear) en esta red, a partir de un nodo raíz (por ejemplo, el nodo 1 en la parte inferior izquierda). Estoy modelización de la propagación de mensajes en términos de árboles arraigados en el origen del mensaje, en donde un nodo v es un padre a otro nodo w si w oye primero el mensaje de v.

• El mensaje se propaga hacia el exterior de la 1, en un árbol que "crece" en un proceso iterativo. En este proceso, los nodos que se han alcanzado son la ramificación de los nodos (es decir, son los padres de algún otro nodo), vivir hojas (nodos que pueden convertirse en los nodos rama), o las hojas muertas.
• Inicialmente, todos los vecinos de el nodo 1 hijos de 1, y se deja vivir.

• El mensaje se propaga por iteraciones, de la siguiente manera. Consideramos arbitraria de pedido L = (ℓ₁, ..., ℓ_n) de las hojas al comienzo de la iteración. Para cada 1 ≤ j ≤ n, hacemos lo siguiente:
  

  1. Decidir si el nodo ℓ_jmuere (no propagar el mensaje), o se convierte en un nodo de rama (se propaga el mensaje). Si todos los nodos adyacentes a ℓ_j ya están en el árbol, luego se muere por defecto.
  2. Si ℓ_j se convierte en un nodo de rama, atribuimos a cada vecino v de ℓ_jque ya no está en el árbol a ℓ_j, como un nodo hoja para la siguiente iteración.
     

  Después de recorrer los elementos de L, de proceder a la siguiente iteración.

• Si no hay más vivo de las hojas en el árbol, nos detenemos.

Para la gráfica de arriba, aquí están los árboles que pueden ser generados por este proceso:

Estoy interesado en la consideración de cómo muchos de los árboles que pueden ser generados por este proceso son árboles de expansión, es decir, contienen cada nodo en el gráfico. ¿Hay alguna fórmula para determinar la proporción de los árboles de expansión para el número total de árboles?

N. B. La construcción de arriba es similar a una de Galton-Watson proceso. Sin embargo, no pretende ser un modelo de probabilidad subyacente del crecimiento; la de arriba es sólo para implícitamente describir un proceso recursivo para reconocer si un subárbol en el gráfico es válido en mi modelo. He añadido la probability etiqueta sólo en caso de que haya un enfoque útil a partir de esa dirección.

Gracias!

Answer 1

Tomar una puñalada en esta basada en mi comentario. Vamos a empezar con un k-vértice, el árbol de raíces . Deseamos añadir vértices y aristas para conseguir un n-vértice arraigada grafo G tales que la aplicación de su algoritmo de G puede terminar en el k-vértice del árbol que hemos empezado.

Así que supongo que el árbol tiene de profundidad d, y que, en cada nivel i de el árbol no se $n_i$ nodos de los cuales, $l_i$ son las hojas. Tenemos, en particular,

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

y vamos a establecer $n_0 = 1$ para la convención.

¿Cuántos de esos árboles hay? Luego de colocar la primera $j$ de los niveles de los nodos, se $n_j C l_j$ maneras de escoger qué nivel-j nodos son las hojas y $(n_{j+1}-1)C(n_j - l_j - 1)$ formas de colocación de la profundidad-$(j+1)$ nodos. Muchas de estas colocaciones son isomorfos, pero si se le asigna un etiquetado para el árbol (como haremos más adelante), son distinguibles. Por lo que el número total de $k$-vértice árboles de profundidad $d$ es

$\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) $

donde los árboles con una determinada secuencia de $n_i, l_i$ corresponden a un único término en la suma en la primera línea.

Entonces queremos etiquetar el árbol de etiquetas de $[2,...,n]$. Hay $(n-1)! / (n-k)!$ formas de hacerlo (la raíz se obtiene la etiqueta especial 1).

Ahora, dado un árbol, ¿en cuántas formas podemos invertir el algoritmo para obtener un n-vértice de la gráfica de G? Bien, vamos a diferenciar en primer lugar los bordes entre dos vértices en el árbol, y los bordes de incidentes (al menos uno) de los $(n-k)$ restantes vértices. El $(n-k)$ restantes vértices son libres para conectar el uno al otro y a cualquier hoja en el árbol, para $e_1 = (n-k)C2 + (n-k)*\sum_i l_i$ potencial de los bordes. Cualquier vértice en el árbol puede ser conectado a una hoja en menor profundidad, no es difícil ver que esto agota todas las posibles aristas que puede ser añadido al árbol cuando nos invertir el algoritmo. Que da $e_2 = \sum_i n_i \sum_{j<i} l_j$ posible de los bordes. Por lo que el número de n vértices gráficos que puede dar a este árbol como salida es $2^{e_1 + e_2}$.

Podemos combinar estas dos fórmulas para obtener $g(n,k)$. No puedo entender cómo evaluar esta exactamente en este punto, pero es fácilmente calculable para pequeñas $n,k$.

Una vez que hemos hecho esto, podemos calcular el promedio de la proporción de algoritmo de salidas que son árboles de expansión. (Aviso que yo no requieren que mi grafo G se conecta a comenzar con, obviamente no desconectado gráfico, que dará lugar a un árbol de expansión).

Answer 2

Bien, teniendo una segunda puñalada en este. Misma técnica general, espero que lo puede contar mejor esta vez.

Comenzamos con nuestro nodo raíz, con la etiqueta '1'. Añadimos los nodos de la 2 a la k en la sucesión. Las etiquetas tienen la intención de corresponder a la orden en la que podemos elegir cuando se ejecuta el algoritmo. Las hojas del árbol son los nodos que están "muertos". Se pueden asociar a cada nodo cualquiera de los nodos ya hemos colocado, lo que nos lleva a la conclusión de que tenemos $(k-1)!$ etiquetados $k$-nodo de árboles, donde cada nodo padre tiene una pequeña etiqueta que el nodo. Vamos a asociar a cada árbol con la secuencia de los padres $\{ 1 =p(2), p(3), ... p(k) \}$ donde $p(j) \in [1,...,j-1]$.

Estamos a continuación, vamos a añadir nodos y bordes para completar esta a un gráfico de $G$ que puede dar este árbol como un resultado del algoritmo anterior. Para el $(n-k)$ los nodos que no están en el árbol, las etiquetamos (todos los etiquetados son equivalentes en este punto), entonces podemos conectar a las hojas del árbol y nos podemos conectar uno con el otro, conduce a $e_1(l;n-k) = (n-k)*l + (n-k)C2$ posible de los bordes de la $l$ hojas.

Ahora a contar dentro del árbol de los bordes. Un nodo $i$ puede ser conectado a un nodo de $j+1 > i$ en el gráfico de $G$ si uno de los tres (mutuamente excluyentes) las condiciones se tiene: 1) $i$ es el padre de $j+1$ en el árbol ($i=p(j+1)$), 2) $i$ es mayor que $p(j+1)$, o 3) $i$ es una hoja y $i$ está a menos de $p(j+1)$.

Esto es muy difícil de contar. Es mejor nota, sin embargo, que dentro del árbol de los bordes son independientes de $n$, y así podemos contar con ellos de una vez para un árbol dado.

Deje $T_k$ el conjunto de la etiqueta $k$-nodo de árboles como el anterior y $T_{k,l}$ el conjunto de la etiqueta $k$-nodo de árboles con $l$ hojas. Dado un árbol de $t$$T_{k,l}$, vamos a $e(t)$ el número de bordes se puede añadir a $t$ consistente con $t$ es un resultado posible de que el algoritmo se ejecute en el resultando $k$-gráfico de nodos. Tomamos nota de que, dado que uno puede libremente conectar cada hoja, cada hoja, $e(t) \geq lC2$. Vamos entonces a definir un polinomio

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

El coeficiente de $x^l$ es el número de maneras en que uno puede completar $k$-nodo, $l$-hojas de los árboles, a una $k$-gráfico de nodos en consonancia con el algoritmo. Por definición, este coeficiente es divisible por $2^{lC2}$.

El primer par de $t_k(x)$ son de la siguiente manera (creo):

$\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}$

No es obvio que hay una relación de recursividad para estos polinomios. Uno podría esperar que, dado que agregar un nodo a un $k$-nodo, $l$-hoja de árbol da un $(k+1)$-nodo, $l$-hoja de árbol o $(k+1)$-nodo, $(l+1)$-hoja de árbol, que uno podría encontrar una relación de recursividad para $[x^{l+1}]$ $t_{k+1}(x)$ en términos de $[x^l]$ $[x^{l+1}]$ $t_k(x)$. Todavía no he encontrado esa relación.

¿Por qué nos preocupamos de estos polinomios en el primer lugar? Es bastante simple: debido a la dependencia de $e_1(l;n-k)$$l$, el número de maneras para completar $k$-nodo árboles a una $n$-gráfico de nodos es $2^{(n-k)C2} * t_k(2^{n-k})$. Para obtener el número de maneras de ejecutar el algoritmo sobre el conjunto de la $n$-nodo gráficos, simplemente se resume esta cantidad a lo largo de $k$. Y, por supuesto, el número de algoritmo se ejecuta en el resultado de un árbol de expansión es $t_n(1)$.

Actualización: creo que he encontrado una recursividad para los coeficientes de $t_k(x)$. Yo todavía no tiene los coeficientes en forma cerrada. Esta recursividad nos obliga a dividir el conjunto de $T_{k,l}$ $k$- nodo, $l$-hojas de los árboles más.

Para un determinado $(k+1)$-nodo, $(l+1)$ hoja de árbol de $t$, se tendrá en cuenta el último nodo hoja no (decir que tiene la etiqueta $a$), y cualquier hoja de dicho nodo hoja no (decir que tiene la etiqueta $b$). Nosotros, a continuación, retirar la hoja, y disminuir las etiquetas de todos los posteriores hojas. El árbol resultante, $t'$, $k$ nodos y bien $l$ o $l+1$ hojas, dependiendo de si $a$ tenía más de una hoja en $t$. Este mapa es no una función, podemos optar $b$ arbitrariamente si $a$ tiene más de un nodo, pero por ahora vamos a pretender que es una función. Vamos a llamar a este mapa de $f: T_{k+1,l+1} \rightarrow T_{k,l} \cup T_{k,l+1}$.

Si $a$ tenía más de una hoja en $t$, nos encontramos con que $e(t) = e(t') + l$. Si $a$ había $b$ como una hoja en $t$ (de modo que $a$ sí es una hoja en $t'$), entonces nos encontramos con que $e(t) = e(t') - (k-a) + l$. Estas ecuaciones no son difíciles de verificar.

Ahora podemos dividir nuestro set $T_{k,l}$ en los conjuntos de $T_{k,l,m,q}$ donde $k$ es el número de nodos en el árbol, $l$ es el número de hojas, $m$ es la etiqueta de la última nodo hoja no e $q$ es el número de hojas en el nodo $m$. Nos vamos a

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

ser el número de maneras de reconstruir un $k$-gráfico de nodos de los árboles en $T_{k,l,m,q}$.

Ahora vamos a intentar invertir $f$$T_{k,l,m,q}$. Podemos añadir una hoja para el nodo hoja no $m$, dando un árbol de $t$$T_{k+1,l+1,m,q+1}$, o se puede añadir una hoja a un nodo hoja $m' > m$, dando un árbol de $t$$T_{k+1,l,m',1}$. En cada caso, tenemos que considerar lo que la etiqueta que vamos a asignar a la nueva hoja (y el incremento de todas las etiquetas después de la nueva etiqueta), y cómo $e(t)$ está relacionado con $e(t')$.

En el último caso, $e(t) = e(t') - (k-m') + l$ y tenemos $(k+1-m')$ opciones para la etiqueta de la hoja de nuevo. En el primer caso, $e(t) = e(t') + l$, y tenemos $(k+1-m)$ opciones para la etiqueta de la hoja de nuevo. Podemos señalar que en este caso, cada árbol $t$ $T_{k+1,l+1,m,q+1}$ $(q+1)$ no-necesariamente-distintas imágenes de $t'$ bajo $f$, pero todos tienen el mismo valor de $e(t')$ (este último hecho no es demasiado difícil de probar).

Por lo tanto, encontrar la siguiente recurrencia:

$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} $.

Las condiciones de contorno en estas recurrencias son como sigue:

$c_{k,l,m,q} = 0$ si $l\geq k$ o $q>l$ o $m+q>k$

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

Los coeficientes del polinomio $t_k(x)$$[x^l] = \sum_{m,q} c_{k,l,m,q}$.