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.

  • $\begingroup$ @j.c. Sorry, I formulated the question badly, edited it now. $\endgroup$ – David Hammer May 8 '15 at 13:57

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.

  • 1
    $\begingroup$ Though the OP did not specify a model, I think there is a natural one to consider: the uniform (labeled) graph on $n$ vertices with $e={n\choose 2} p_2$ edges and $t={n\choose 3} p_3$ triangles -- just as the Erdős Rényi graph (or rather, a slight variant) is the uniform graph on $n$ vertices with $e$ edges. Surprisingly, I was not able to find any reference in the literature to such a model. The closest I could find was dx.doi.org/10.1103/PhysRevE.82.066118 which is not quite it. $\endgroup$ – Yoav Kallus May 8 '15 at 16:01
  • $\begingroup$ @YoavKallus Well the generative model is indeed a simple ER graph. The main difference is that the number of triangles has been observed and is thus known. So if the number of triangles is higher than the expected value this changes the expected frequency of higher order groups. $\endgroup$ – David Hammer May 8 '15 at 22:48

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.

  • $\begingroup$ How would you choose $\theta_E$ and $\theta_T$in the exponential model? according to a mean constraint? And can you please elaborate on why (in the large $n$ limit) can't we get the number of triangles and edges we wanted? $\endgroup$ – MathGirl88 Mar 19 at 11:27
  • $\begingroup$ @MathGirl88, yes, choose the parameters to achieve the prescribed mean number of edges and triangles. $\endgroup$ – Yoav Kallus Mar 21 at 0:43
  • $\begingroup$ Thank you for your answer. A follow-up question: In this case (exponential with prescribed mean) can we prove that if I'm drawing from this distribution, I am most likely to get a graph with the prescribed number of edges and triangles? I mean, compare to any other specific pair $E,T$, and not compare to the probability not to get such graph. $\endgroup$ – MathGirl88 Mar 22 at 6:14
  • $\begingroup$ @MathGirl88 No, that would not be the case in general. This is because the entropy density is not concave as a function of the edge density and the triangle density (see arxiv.org/abs/1302.3531), so to achieve a certain mean density the exponential graph ensemble you generate will be some mixture low density and high density graph instead of the typical graph being the desired density. $\endgroup$ – Yoav Kallus Mar 22 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.