# A Friend of a Friend: Transitivity in Large Random Graphs

Suppose we have a network $G$ of $n$ people, who share $M$ connections. Define the transitivity index $\tau(G)$ as the count of all possible threesomes having $3$ connections divided by the count of all possible threesomes having $2$ or $3$ connections (provided that these counts are not both zero, otherwise $\tau(G)=1$).

Suppose that the connections are distributed uniformly randomly (conditional on there being $M$ such connections). More precisely: Let $N\equiv\binom{n}{2}$ and let the model $\mathcal G(n,M)$ consist of all $\binom{N}{M}$ graphs, having vertices $\{1,2,\ldots,\ n\}$ and $M$ edges, in which every such graph is realised with probability $\binom{N}{M}^{-1}$.

Define the transitivity distribution implicitly by

$G\sim\mathcal G(n,M)\Rightarrow\tau(G)\sim\mathrm{TR}(n,M)$.

In $\mathcal G(n,M)$, what can be said about the transitivity distribution $\mathrm{TR}(n,M)$ for large $n$ and $M$?

Edit

I am particularly interested in quantiles of $\mathrm{TR}(n,M)$. For example, for $(n,M)=(100,150)$, the order statistic $\tau_{4750:5000}$ was about $0.054$ in simulation.

Enumeration is not an option. The number of automorphism classes containing graphs with vertex set $\{1,2,\ldots,n\}$ and size $M$ is for moderate $(n,M)=(50,75)$ at least $5\cdot10^{56}$.

But, of course, I am hoping that an analytical approximation is available, even if it only works well beyond say $(n,M)=(10^5,10^6)$.

Note

The fabulously useful answer provided by joriki may not work for $M<{{n}\over{2}}$, since the denominator then has mass at $0$, which is contra the assumption in Approximations for Mean and Variance of a Ratio. However, these cases are not at all as interesting with regards to (the) applications (I have in mind).

-

I don't know how to estimate quantiles, but you can estimate the variance by Taylor-expanding around the expected values of the numerator and denominator; see Calculating the variance of the ratio of random variables. The result linked to in raj's answer can be written as

$$\operatorname{Var}\frac CD\approx\frac{\langle CC\rangle\langle D\rangle\langle D\rangle-2\langle CD\rangle\langle C\rangle\langle D\rangle+\langle DD\rangle\langle C\rangle\langle C\rangle}{\langle D\rangle^4}\;.$$

Thus we only need first and second moments of the numerator $C=\sum_jC_j$ and the denominator $D=B+C=\sum_jB_j+\sum_jC_j$, where $j$ runs over all triples of vertices, $B_j$ is the indicator variable for triple $j$ sharing two connections and $C_j$ is the indicator variable for triple $j$ sharing three connections.

To calculate the second moments, note that the $\binom n3^2$ ordered pairs of triangles are of three types: $\binom n3$ pairs of identical triangles, $12\binom{\vphantom{h}n}4$ pairs of triangles sharing one edge, and $30\binom n5+20\binom n6$ pairs of triangles sharing no edges (the first term for those sharing one vertex and the second term for those sharing no vertices). You can work out the probabilities for the indicator variables and their products to be $1$ by counting how many of the $\binom NM$ possibilities that leaves; for instance, for the first of two triangles sharing an edge to have three connections and the second to have two (a case that occurs $12\binom{\vphantom{h}n}4$ times in $\langle\sum_{jk}B_jC_k\rangle$), there are $2$ options for which of the two non-shared edges in the second triangle to use and $\binom{N-5}{M-4}$ options for the remaining edges, so the contribution from that case is

$$12\binom n4\cdot2\frac{\binom{N-5}{M-4}}{\binom NM}=24\binom n4\frac{M(M-1)(M-2)(M-3)(N-M)}{N(N-1)(N-2)(N-3)(N-4)}\;.$$

Putting this all together yields a big mess, but if we assume that the probability $p=M/N$ of an edge being selected remains fixed as $n\to\infty$, we can retain only the leading order in $n$ to get an asymptotic estimate. Here's a Sage session that does all the calculations:

sage: n,p,x = var ('n, p, x')
sage: N = binomial (n,2)
sage: M = p * N
sage: t3 = binomial (n,3)
sage: t4 = 12 * binomial (n,4)
sage: t56 = 30 * binomial (n,5) + 20 * binomial (n,6)
sage: def expand (expr,order=0) : return taylor (expr.substitute (n=1/x),x,0,order).substitute (x=1/n);
sage: C = expand (t3 * M*(M-1)*(M-2) / (N*(N-1)*(N-2)))
sage: B = expand (t3 * 3 * M*(M-1)*(N-M) / (N*(N-1)*(N-2)))
sage: BB = expand (t3 * 3 * M*(M-1)*(N-M) / (N*(N-1)*(N-2)) + t4 * M*(M-1)*(M-2)*(N-M) * ((M-3) + 4*(N-M-1)) / (N*(N-1)*(N-2)*(N-3)*(N-4)) + t56 * 9 * M*(M-1)*(M-2)*(M-3)*(N-M)*(N-M-1) / (N*(N-1)*(N-2)*(N-3)*(N-4)*(N-5)))
sage: BC = expand (t4 * 2 * M*(M-1)*(M-2)*(M-3)*(N-M) / (N*(N-1)*(N-2)*(N-3)*(N-4)) + t56 * 3 * M*(M-1)*(M-2)*(M-3)*(M-4)*(N-M) / (N*(N-1)*(N-2)*(N-3)*(N-4)*(N-5)))
sage: CC = expand (t3 * M*(M-1)*(M-2) / (N*(N-1)*(N-2)) + t4 * M*(M-1)*(M-2)*(M-3)*(M-4) / (N*(N-1)*(N-2)*(N-3)*(N-4)) + t56 * M*(M-1)*(M-2)*(M-3)*(M-4)*(M-5) / (N*(N-1)*(N-2)*(N-3)*(N-4)*(N-5)))
sage: D=B+C
sage: DC = BC + CC
sage: DD = BB + 2 * BC + CC
sage: expand (C/D)
-p/(2*p - 3)
sage: expand ((CC*D*D - 2*DC*C*D + DD*C*C) / D^4,3)
18*(p^3 + p^2 - 5*p + 3)/((16*p^5 - 96*p^4 + 216*p^3 - 216*p^2 + 81*p)*n^3)


The results (which I tested in simulations) can be expressed as

$$\left\langle\frac CD\right\rangle\approx\frac p{3-2p}$$

and

$$\operatorname{Var}\frac CD\approx\frac{18(1-p)^2(3+p)}{n^3p(3-2p)^4}\;.$$

Interestingly, it turns out that, whereas if edges are selected independently with probability $p$ the variance goes as $n^{-2}$, in your case more terms cancel and the variance goes as $n^{-3}$, which makes sense, since there's no variance in the total number of edges selected.

In your example with $n=100$ and $M=150$, the expected value is about $0.01$ and the standard deviation is about $0.005$, so your order statistic is about $9$ standard deviations away from the mean – I didn't see a single configuration like that out of $4$ million in my simulations, so unless I misunderstood something, you may want to check your simulation code (here's mine).

-
Wow, thanks! That's already quite something. And very usefully documented, I must say! – Keep these mind Jan 19 '13 at 12:46
Checking my simulation algorithm would involve some pre-historic digging and reconstruction, but is probably feasible. (It's certainly different because it was supposed to improve time complexity.) However, perhaps I just made a typo in the number at the time. Could I possibly ask you to check ($n, M, \tau_{4750:5000}$) $10,15,0.477$; $20,30,0.258$; $50,75,0.106$? (I have no practical means or knowledge to actually execute your algorithm.) – Keep these mind Jan 19 '13 at 13:09
@Gugg: I don't know this notation; am I interpreting correctly that you're referring to the expected value of the $4750$-th of $5000$ samples, sorted in increasing order? If so, roughly $5\%$ of all values should lie above these values. That's not the case in my simulations; these values are exceeded by approximately $0.00005$ of all samples in the first case, and never in millions in the other two cases. In all cases these values are something like $8$ standard deviations away from the expected value. I wonder whether I misunderstood some aspect of your setup. Anything else we can compare? – joriki Jan 19 '13 at 13:56
I am kicking myself here. I think I gave the wrong $\tau$ in the original question (an alternative I later dismissed)! Aargh!!! I can't believe it... Could you try to set to something like double ratio = 3*count3 / ((double) count2+2*count3); (or its proper equivalent). I'm so sorry. – Keep these mind Jan 19 '13 at 14:45
The question will stay as it is, because it still has perfect meaning. And it has a great answer! (Maybe I should put up a duplicate?) – Keep these mind Jan 19 '13 at 14:56