Probability of relations in network Imagine, i have a predicate $\text{friends}(x_1, x_2)$ and I know that $p(\text{friends}(x_1, x_2)) = p_2$. If I generate a world of $n$ people ($x_1$ to $x_n$), I expect there to be $\binom{n}{2}p_2$ friends. Now, imagine, I count the number of times that 3 people are all friends of each other in this world: $\binom{n}{3} p_3$. I expect the probability of three random people being friends to be $p_3$. ($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 key thing is to be precise about what model is used to generate your random graphs.  It's typically not enough to pick out some set of events and specify that they hold with particular probabilities.
The most studied random graph model is the Erdős-Rényi or binomial random graph in which each edge appears independently with a fixed probability $p$.  It then follows that each triangle appears with probaility $p^3$, each set of four vertices is connected completely with probability $p^{\binom 4 2} = p^6$ and so on.  In particular, there is no room in this model to freely specify both the probability that any pair of vertices is connected and the probability that any three vertices form a triangle.
This model has various drawbacks for modelling real-life networks.  For example, in your friendship example you might expect two of your friends to be more likely to be friends than two random people off the street.  In order to model these types of networks other models of random graphs have been proposed.  One such model is the hyperbolic geometric graph: you select some random points in the hyperbolic plane, then join those that are within some specified (hyperbolic) distance of each other.  This model has been shown to have some properties shared by real world networks.
So I suspect that what you are interested in is different models of random graphs.  Gil Kalai asked recently for a list of models of random graphs useful for modelling real world netwoks.  You might find that a useful starting point.  You might also get more accurate suggestions if you say a bit about where your interest in this comes from.
A: It turns out that this problem is rather ill-posed and badly behaved. If you follow the maximum entropy principle, you will be led to want to sample from the set of labeled graphs with probability $p(G) = \exp[\theta_E |E(G)| + \theta_T |T(G)|]/Z$, where $E(G)$ and $T(G)$ are the edges and triangles of $G$ respectively, and $Z$ is the normalization. However, whenever $Z<\infty$, this distribution approaches, in the large $n$ limit, the Erdős-Rényi distribution, so you can never get the number of triangles and edges you wanted. It turns out that graphs with $p_3\neq p_2^3$ are just exceptionally more rare than ones with $p_3=p_2^3$.
One way to interpret your question that leads to a concrete answer is the following. Take the Erdős-Rényi distribution on labeled graphs on $n$ vertices with parameter $p_2$, and condition it on the event of having $p_3 {n \choose 3}$ traingles. What is this conditional probability? According to these notes (see also the reference on the last page), it exhibits a phase transition: for some values of $p_2$ and $p_3$, the distribution approaches the Erdős-Rényi distribution with the parameter $p_3^{1/3}$ instead of $p_2$. For other values, you approach the distribution giving a complete graph on a subset of the vertices.  
EDIT: I just came across this MO question of Gil Kalai's, which has a good general discussion of this very kind of problem.
