Número de realizaciones de un determinado tipo de tríada

Question

Dados cuatro tipos de tríadas (figura inferior) sus probabilidades en un dígrafo aleatorio de Bernoulli son las siguientes:

• $T_{003}$ : $(1-p)^6$
• $T_{012}$ : $6p(1-p)^5$
• $T_{102}$ : $3p^2(1-p)^4$
• $T_{111D}$ : $6p^3(1-p)^3$

Por ejemplo, para la tríada $T_{012}$ hay seis realizaciones de la díada asimétrica y para la tríada $T_{102}$ hay tres realizaciones de la díada mutua.

Mi pregunta es cómo expresar adecuadamente el número de realizaciones de cada tipo de tríada.

Answer 1

Si tienes, por ejemplo, un gran dígrafo aleatorio de Bernoulli $G$ y buscamos el número de "copias" de un subgrafo $H$ podemos escribir algo parecido:

"...el número de subgrafos inducidos de $G$ isomorfo a $H$ es...".

Esta es la definición típica en el motivo de la red (que parece ser el giro moderno de las díadas, tríadas, etc.). Las variaciones sobre este tema no son desconocidas (por ejemplo, para tener en cuenta el hecho de que la definición anterior cuenta con "copias" superpuestas de $H$ por separado).

Obsérvese la palabra "inducido", que se omite con frecuencia (y, desde la perspectiva de la teoría de grafos, erróneamente) en muchas publicaciones de este ámbito. Por ejemplo, el subgrafo etiquetado como "003" ocurriría exactamente ${n \choose 3}$ veces como un subgrafo en cualquier $n$ -mientras que es probable que aparezca menos veces como subgrafo inducido.

Nota : también es bastante normal (al menos en la teoría de grafos) llamar a estos grafos aleatorios, Grafos aleatorios de Erdős-Rényi ya que se generan con el mismo espíritu que el modelo no dirigido. Esta terminología se utiliza, por ejemplo, en:

B. Bollobás, O. Riordan, Mathematical results on scale-free random graphs, en Handbook of graphs and networks, 2002.

Esta es la referencia por defecto cuando se utilizan grafos aleatorios de Erdős-Rényi:

P. Erdos, A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci, Vol. 5 (1960), pp. 17-61.