Distribuição e variância da contagem de triângulos no gráfico aleatório

10

Considere um gráfico aleatório Erdos-Renyi . O conjunto de vértices é rotulado por . O conjunto de arestas é construído por um processo aleatório.G=(V(n),E(p))nVV={1,2,,n}E

Seja uma probabilidade , então cada par não ordenado de vértices ( ) ocorre como uma aresta em com probabilidade , independentemente dos outros pares.p0<p<1{i,j}ijEp

Um triângulo em é um triplo não ordenado de vértices distintos, de modo que , e são arestas em .G{i,j,k}{i,j}{j,k}{k,i}G

O número máximo de triângulos possíveis é (n3) . Definir a variável aleatória X ser a contagem observada de triângulos no gráfico G .

A probabilidade de três links estarem presentes simultaneamente é p3 . Portanto, o valor esperado de X é dado por E(X)=(n3)p3 . Ingenuamente, pode-se adivinhar que a variação é dada por E(X2)=(n3)p3(1p3) , mas esse não é o caso.

O seguinte código do Mathematica simula o problema:

n=50;
p=0.6;
t=100;
myCounts=Table[Length[FindCycle[RandomGraph[BernoulliGraphDistribution[n,p]],3,All]],{tt,1,t}];
N[Mean[myCounts]] // 4216. > similar to expected mean
Binomial[n,3]p^3 // 4233.6
N[StandardDeviation[myCounts]] // 262.078 > not similar to "expected" std
Sqrt[Binomial[n,3](p^3)(1-p^3)] // 57.612
Histogram[myCounts]

Qual é a variação do X ?

LBogaardt
fonte

Respostas:

4

Seja se se formar um triângulo. Então e cada . Isto é o que você usou para calcular o valor esperado.{ i , j , k } X = i , j , k Y i j k Y i j kB e r n o u l l i ( p 3 )Yijk=1{i,j,k}X=i,j,kYijkYijkBernoulli(p3)

Para a variação, o problema é que os não são independentes. De fato, escreva Precisamos calcular , que é a probabilidade de ambos os triângulos estarem presentes. Existem vários casos: X 2 = i , j , k i ' , j , k Y i j k Y i j k . E [ Y i j k Y i ' j k ]Yijk

X2=i,j,ki,j,kYijkYijk.
E[YijkYijk]
  • Se (mesmos 3 vértices), então . Haverá esses termos na soma dupla.E [ Y i j k Y i ' j ' k ' ] = p 3 ( n{i,j,k}={i,j,k}E[YijkYijk]=p3(n3)
  • Se os conjuntos e têm exatamente 2 elementos em comum, precisamos de 5 arestas presentes para obter os dois triângulos, de modo que . haverá esses termos na soma.{ i ' , j , k } E [ Y i j k Y i ' j k ] = p 5 12 ( n{i,j,k}{i,j,k}E[YijkYijk]=p512(n4)
  • Se os conjuntos e têm 1 elemento em comum, precisamos de 6 arestas presentes, para que . Haverá desses termos na soma.{ i ' , j ' , k ' } E [ Y i j k Y i ' j k ' ] = p 6 30 ( n{i,j,k}{i,j,k}E[YijkYijk]=p630(n5)
  • Se os conjuntos e têm 0 elemento em comum, precisamos de 6 arestas presentes, para que . Haverá tais termos na soma.{ i ' , j ' , k ' } E [ Y i j k Y i ' j k ' ] = p 6 20 ( n{i,j,k}{i,j,k}E[YijkYijk]=p620(n6)

Para verificar se cobrimos todos os casos, observe que a soma total é .(n3)2

(n3)+12(n4)+30(n5)+20(n6)=(n3)2

Lembrando de subtrair o quadrado da média esperada, juntar tudo isso dá:

E[X2]E[X]2=(n3)p3+12(n4)p5+30(n5)p6+20(n6)p6(n3)2p6

Usando os mesmos valores numéricos do seu exemplo, o código R a seguir calcula o desvio padrão, que é razoavelmente próximo ao valor de 262 da sua simulação.

n=50
p=0.6
sqrt(choose(n, 3)*p^3+choose(n, 2)*(n-2)*(n-3)*p^5+(choose(n, 3)*choose(n-3, 3)+n*choose(n-1, 2)*choose(n-3, 2))*p^6-4233.6^2)
298.7945

O código do Mathematica a seguir também calcula o desvio padrão, que fornece o mesmo resultado.

mySTD[n_,p_]:=Sqrt[Binomial[n,3]p^3+12Binomial[n,4]p^5+30 Binomial[n,5]p^6+20Binomial[n,6]p^6-(Binomial[n,3]p^3)^2]
mySTD[50,0.6] // gives 298.795
Robin Ryder
fonte
2
Na verdade, bastante direto. Bem feito! Atualizei sua resposta um pouco, simplificando as expressões e adicionando o código do Mathematica . Também executei minha simulação 10k vezes e obtive um valor padrão de 295,37, muito próximo do valor esperado.
LBogaardt 11/04
11
Obrigado pela edição. Fico feliz que a simulação com 10k iterações confirma a resposta!
Robin Ryder
Encontrei a referência original, para gráficos direcionados: Holland (1970). Um método para detectar estrutura em dados sociométricos.
LBogaardt
0

Eu forneço uma abordagem ligeiramente diferente de derivar .X2

Com a mesma distinção entre casos que Robin Ryder:

  • Se ou seja, os 3 vértices são os mesmos, portanto, devemos escolher 3 vértices dentre n possíveis . Devemos ter 3 arestas presentes . Combinado:{i,j,k}={i,j,k}(n3)p3(n3)p3

  • Se e tiverem dois vértices em comum, isso significa nos quais e vice-versa (cada triângulo possui um vértice que não faz parte do outro triângulo). Imagine que e são os vértices disjuntos mencionados e = , = . Para atingir = , = , precisamos escolher os mesmos dois vértices dentre n possíveis . Para{i,j,k}{i,j,k}v{i,j,k}v{i,j,k}v=kv=kiijjiijj(n2)kkdevemos escolher mais dois dos vértices que restam. Primeiro: e segundo: . Como as arestas e são as mesmas, precisamos ter 5 arestas presentes . Combinado:(n2)(n3){i,j}{i,j}p5(n2)(n2)(n3)p5

  • Se e tiverem apenas um vértice em comum, então 4 serão disjuntos. Imagine, wlog, que = . Isso significa que, dentre n possíveis vértices, devemos escolher 1 . Para o triângulo , escolhemos 2 vértices dos restantes . Para o triângulo escolhemos 2 dos restantes , isso se deve à suposição de que e . Como temos apenas um vértice em comum, precisamos ter 6 arestas presentes{i,j,k}{i,j,k}iin{i,j,k}(n1)(n12){i,j,k}(n3)(n32)j{i,j,k}k{i,j,k}p6 . Combinados:n(n12)(n32)p6

  • Para o último caso: Se e não têm vértice em comum, então os 2 triângulos são disjuntos. Escolhemos o primeiro triângulo, 3 vértices de n possíveis . E o segundo triângulo, 3 vértices dos restantes . Os triângulos são disjuntos, ou seja, eles não compartilham arestas e vértices, portanto, 6 arestas devem estar presentes . Combinado:{i,j,k}{i,j,k}(n3)(n3)(n33)p6(n3)(n33)p6

Como na abordagem de Robin Ryder, também podemos verificar que:

(n3)+(n2)(n2)(n3)+n(n12)(n32)+(n3)(n33)=(n3)2 .

Isto leva a:

Var[X]=E[X2]E[X]2=(n3)p3+(n2)(n2)(n3)p5+n(n12)(n32)p6+(n3)(n33)p6(n3)2p6.

Josh
fonte