Probability of relations in a network Imagine, i have a random graph with $n$ nodes representing people. Between every two nodes there is an edge representing friendship with probability $p_2$. These edges are independently generated, so I expect there to be $\binom{n}{2}p_2$ friends. Now, imagine, I count (observe) the number of times that 3 people are all friends of each other in this world: $\binom{n}{3} p_3$. Therefor, I expect the probability of three random people being friends to be $p_3$. (probabilities $p_2, p_3 \in [0..1]$)
I'm trying to calculate the probability that any 4 people in my world are all friends with each other. Without knowing $p_3$ I would estimate the probability to be $p_2^6$. But obviously knowing $p_3$ influences the probability. For example if $\frac{p_3}{p_2}$ increases, I expect the friendships to be denser and thus more 4 people will form groups. I have trouble however finding a formula to express this probability, because the probabilities that the different subgroups of 3 people are friends are not independent. And if I take four random people the probability that at least 3 subgroups of three people are friends is the same as that at least 4 subgroups of three people are friends.
Could you provide any advice on how one typically calculates such a problem or what to search for? By what factor does $\frac{p_3}{p_2}$ increase the probability of a third connecting edge in presence of two edges? I would assume one would somehow express this using conditional probabilities, although I can't seem to figure out exactly how.
 A: The answer to this is simple:
For $n$ nodes with probability $p$ of a connecting edge, the probabilty $p_n$ that a given group of all selected nodes have mutual connecting edges is:
$p_n = p^ \frac{n!}{2(n-2)!}$
That is, the combined probability that the required number of unique edges required occur concurrently.
To illustrate:
for $n = 2$:
$p_n = p_{12}$

for $n = 3$:
$p_n = (p_{12})(p_{13})(p_{23})$

for $n = 4$:
$p_n = (p_{12})(p_{13})(p_{14})(p_{23})(p_{24})(p_{34})$

As the probability of any connecting edge has been defined as $p$, there is no need to further delimit the probability of any two specific nodes having a connecting edge.
Therefore:
for $n = 2$:
$p_n = p^1$            (identity)
for $n = 3$:
$p_n = p^3$
for $n = 4$:
$p_n = p^6$
The probability of an edge occuring between two nodes is not affected by whether one of the nodes has other connecting edges.
Mutual Inclusion Factor
If, however, you're looking for a probability $p_n$ given a conditional $p(s)$ that is dependent on the number of shared other connections $s$:
$p(s)$ = probability of a shared edge given $s$ mutual connections to other nodes
To illustrate:
for $n = 2$ and $s_{12} = 2$:
$p_n = p(s_{12})$

for $n = 3$:

$p_n = (p(s_{12}))(p(s_{13}))(p(s_{23}))$
for $n = 4$:
$p_n = (p(s_{12}))(p(s_{13}))(p(s_{14}))(p(s_{23}))(p(s_{24}))(p(s_{34}))$
etc.
$p(s)$ values would have to be determined through an analysis of your particular network- (what is the probability of two nodes sharing an edge given that they share connections to $s$ other nodes?) as would $p$ in the original case.
