Some mathematicians like probability, and some mathematicians like graphs, so it’s only natural that some mathematicians like probabilistic graphs. That is, they like to generate graphs at random, and then ask all sorts of questions about them: What are the features of a random graph? Will it be connected? Will it contain many triangles? Will it be possible to color it with colors without coloring two adjacent vertices in the same color? Will it bring me tenure? They may also check if the graphs can be used in order to prove other theorems, or if they can represent real-world networks in some way.
The answers to all these very interesting questions (interesting to some of us, anyway) depend very much on what we mean when we say that we “generate a random graph”. In fact, for the phrase “generate a random graph” to be meaningful, you must tell me the distribution’s probability law; that is, you must tell me, for each graph, what is the probability of obtaining it. Only then can we carry out the calculations.
There are many ways of choosing such a law; in this series of posts I will present the random graphs commonly found in mathematics and network theory, and demonstrate some of their properties.
Last Time we discussed the Erdős–Rényi model for random graphs. It was a simple model, in which whether or not a given edge appears in the graph was independent from all other edges. This independence gave us an easy time both when generating the graph, and when analyzing some of its properties. However, this independence also made it inadequate for representing real-life networks. The model we will discuss now, exponential random graphs, denoted , allows for dependence between edges. It is easy to describe, but notoriously difficult to analyze. It goes as follows.
Let be the number of vertices we want there to be in the graph, and let be some function on graphs with vertices. For example, for a given graph , may count the number of triangles in ; it may return the size of the largest clique in ; or it may return 1 if is a tree and 17 otherwise. Borrowing from its physical origins, the function is often called the Hamiltonian of the model. Using , we define the following probability distribution on graphs with vertices:
where is a normalizing constant that is just there to make sure that the probabilities sum up to ; it may be written as
The important thing to take home is that the probability to get a graph is proportional to .
Ok, I admit, I haven’t actually told you anything when I wrote this equation, since was arbitrary, and with arbitrary Hamiltonians we can get arbitrary distributions. That is, for every probability distribution on -vertex graphs, we can always find an so that ; simply take
This means that in order to get any meaningful analysis, we must restrict ourselves to specific classes Hamiltonians; every different Hamiltonian we choose will probably lead to different behavior (which will probably require different analysis). The decision to have the probability be proportional to and not just is due to the statistical-mechanics and entropy origin of the formulation, which we won’t discuss here (but it’s also an easy way to keep the probabilities positive).
One very popular class of Hamiltonian are the subgraph-counting functions, which we will use for the rest of this post. These are functions which count how many times a given graph appears inside of . We may count edges, triangles, 27-spoked wheels, cliques, stars; anything really. For example, in the following graph, there are 15 edges, 0 triangles, 12 pentagons and 10 hexagons. However, there are no 27-spoked wheels.
More formally, let be fixed finite simple graphs, and denote by the number of copies of inside . A subgraph-counting function is then a function of the form
where are real constants called weights.
The main idea here is that using subgraph-counting functions, we can more-or-less control the number of subgraphs of different types in . Suppose that so that counts just a single subgraph with weight . If is a large positive number, then each time appears as a subgraph in , gets a strong boost. Graphs with lots of copies of then get a very large values, and will appear with higher probability than graphs without many copies of . On the other hand, if is a large negative number, then is heavily penalized each time appears as a subgraph in . Graphs with lots of copies of then get a very negative weight, and will appear with tiny probability compared to other graphs. Of course, in the general case, may count multiple subgraphs and give each one a different weight, complicating the matter very much: how will things behave if we give a large bonus to graphs with lots of 4-cliques, but at the same time penalize graphs with lots of triangles?
The relation to G(n,p)
The subgraph-counting exponential random graph model is agonizingly more complicated than the model we discussed last time. In fact, it strictly contains it! Here is a particular case of a subgraph-counting function which reproduces the distribution:
where is the number of edges in . This is indeed a subgraph-counting function: we have where is the edge graph, and . Under the exponential random graph model, the probability to obtain a graph with Hamiltonian is then just
The denominator should be such that the sum over all graphs equals 1. We will “guess” that
This is exactly the probability of obtaining a graph in the model! So the exponential random graph model is indeed stronger; we only need to count one tiny graph (an edge) to get .
On the other hand, counting pretty much anything else already sets up a dependence between the edges. For example, suppose that you generate a graph just by penalizing the number of triangles in it. Look at some three vertices , , . Conditioned on the event that the edges and exist in the graph, the probability that the graph contains the edge as well is lower than the probability that it doesn’t contain it, because its appearance would add another triangle and therefore give a smaller value. So the edge depends on the the two other edges and .
How to generate
Talking abstractly about probabilities is nice and all, but a good question to ask is how to actually generate an exponential random graph yourself on your computer. There are some good reasons for wanting to do so: For example, if you generate an exponential random graph by counting triangles, you can estimate the expected number of squares by simply generating many exponential graphs and counting the number of squares they contain. At the very least, this might give you some intuition as to the structure of these graphs. We’ll see some more uses up ahead.
This problem is known as “sampling”, and at first glance, doesn’t seem like too big of a deal: for every there is only a finite number of graphs on vertices, and our problem is to sample from a finite set with a given probability distribution. This can always be done as follows. First, generate a uniform random number between 0 and 1. Once we have that number, we go over the graphs one after the other in some order, and for each one calculate the probability of obtaining it. When the sum of probabilities of all the graphs we have seen so far exceeds , we output the last graph we saw, and we are done.
This approach can work well when is, say, 5. But the number of graphs on vertices is , which for all practical purposes can be treated as for all ; there are simply too many graphs to go over (). Further, we very casually glossed over another problem in the above paragraph: We don’t really know the probability of obtaining a graph under this model. Sure, we can calculate the numerator , but the normalizing constant again involves going over all graphs! It seems that in this naive approach, there is no avoiding iterating over all graphs.
What people usually do instead is to use a variety of algorithms falling under the name “Markov Chain Monte Carlo Method” (MCMCM). This is a neat class of techniques which use random processes in order to approximate probability distributions.
The general technique is to start with some graph on vertices, and then proceed in small, random steps. For example, at each step you might add or remove an edge from the graph according to some probability rule. The changes that are made to the graph, and the probability rule that governs them, are determined only by the graph you have in the current step, and not on the graph you started with or on anything else in the history of the computation. This is called a “Markov Chain”. The trick is to choose the changes and the probability of making them carefully, so that after many steps, you end up with a random graph whose distribution is very close to the distribution that you want to sample from. If each step takes only a small amount of time to carry out, and if it doesn’t take too many steps to get close to the original distribution, then this type of algorithm gives an efficient way to sample an exponential random graph!
Let’s see one specific algorithm from this class, called “Glauber dynamics”:
- Start with any graph ; for example, the empty graph.
- Pick two vertices uniformly at random from . These vertices might or might not be connected by an edge, which we denote .
- Denote by the graph that is identical to , except that it also contains , and by the graph that is identical to , except that it does not contain the edge .
- Add the edge to with probability proportional to (if already contains don’t do anything), and remove the edge from with probability proportional to (if doesn’t contain don’t do anything).
- Run steps (2)-(4) for time steps, then stop ( should be chosen beforehand so that the resulting distribution is close to ; we’ll talk about it later on).
Before we discuss the amount of time it takes to run this algorithm, we should verify that the Glauber dynamics indeed converge to the exponential random graph distribution. That is, we need to show that if we run this process for enough steps, then the graph will distribute approximately like . To do this, let’s first calculate the probabilities of adding / removing an edge.
Denote the probability of adding an edge by , and the probability of removing an edge by . First, we have that
since probabilities always sum up to 1. Second, we have that
since the probabilities are proportional to . Solving these two equations, we get
Already we are in a better condition than before: the probability to makes a move does not depend on the normalizing constant . All we have to do at each step is to calculate and . It is possible to do this in time that depends only polynomially on : if counts a graph on vertices, all we have to do is go over all ordered subsets of vertices of of size , and see whether or not they form the desired graph . This requires only about computations.
Now that we have calculated the probabilities, we can check that we indeed converge to the exponential random graph distribution. For this we will use a deus-ex-machina well known result about Markov chains. Observe that:
- At each step, we have a finite probability of not changing the graph at all.
- If we start with some graph , it is possible (by a miraculous stroke of luck) to obtain any other graph after steps: it could be that by chance our algorithm picked all the edges in which and differed and changed them.
- There are only a finite number of graphs on vertices.
These three properties imply that the Markov chain is “finite, irreducible and aperiodic”, and a theorem in Markov chain theory (which we won’t prove) states that such chains always converge to a single distribution called the stationary distribution.
Aha! A stationary distribution is a distribution over all possible graphs, so that if we randomly pick as our initial graph in the algorithm and we take a single step, then the new is still distributed as ! In other words, is preserved when applying the steps of the Markov chain. By the above theorem, the Glauber dynamics algorithm has a unique stationary distribution to which it converges. If we can show that the exponential random graph distribution is stationary, we are done!
So, suppose that we start with a graph that distributes according to . After one step of Glauber dynamics, what is the probability of obtaining some graph ? Since Glauber dynamics can change no more than one edge at a time, we need to go over all graphs which differ from by one edge, and calculate the transition probability. We also need to calculate the probability of starting at and staying there. We do this by going over the edges.
For each edge , there are two ways to get the graph : either we start with the graph without , which we denote , and add it; this happens with probability
or, we start with , pick , and choose to keep it; this happens with probability
Likewise, for each edge , there are again two ways to get the graph : either we start with the graph that has , which we denote , and remove it; this happens with probability
or we start with , pick , and choose not to keep it; this happens with probability
The probability of getting after one step is then (ok, you can skip this equation block if it makes you feel queasy)
Alright! The calculations are all in order. The nice thing about Glauber dynamics is that they can easily be simulated on a computer: we can start with any initial , choosing two vertices at random is easy, and calculating the value isn’t that hard either, as we saw above. Thus each step takes a polynomial time in the number of vertices , which falls under the category of “each step takes only a small amount of time to carry out”. The only problem left is to figure out what to take in step (5), that is, to know when to stop the algorithm.
Alas, this is a tricky thorn, for two reasons: first, precise analytical results on the rate of convergence for the Markov chain are scarce, and we often don’t really know when we should the stop the algorithm. Second (and worse), some of the results we do possess are quite depressing! For example, it was shown in Bhamidi, Bresler and Sly that if we count subgraphs with only positive weight, then under certain conditions, one of two things happen.
- The Markov chain converges really quickly to the stationary distribution; hurray! However, the stationary distribution in this case is actually pretty much just ! It turns out that sometimes exponential random graphs behave basically just like , even if you count more than just edges. So all the above machinery turns out to be quite an overkill.
- The Markov chain converges really slowly to the stationary distribution (which seems to behave like a mixture of ‘s). By “really slowly”, I mean a time that is exponential in the number of vertices. Wait, isn’t that what we wanted to avoid in the first place?
Luckily for us, this grim result doesn’t say anything about what happens when any one of the weights is negative. Maybe you, dear reader, are up to the challenge?
Real life and parameter estimation
So, do exponential random graphs have anything to do with real life apart from giving mathematicians a hard time? Many people, especially social scientists, think they do, and they try to “fit” exponential random graph parameters to observed networks. That is, given a real-life network, they try to guess what subgraphs are counted and with that weight . Once they have a good estimate for those parameters, they can generate more random graphs and try to learn something interesting about them, perhaps gaining knowledge about the original graph or about the social process that formed it by the way.
One natural way to fit an exponential random graph model to an existing network is as follows. Suppose you already have an observed graph . You notice that it contains very little triangles, but lots of squares; this makes you guess that there is some sort of mechanism that penalizes triangles but rewards squares. A candidate Hamiltonian function would then be one that counts triangles with a negative weight and counts squares with a positive weight . But what should the values of and be? Well, for every choice of weights, you can calculate the expected number of triangles and the expected number of squares. A likely choice for and is to pick them so that the expected number of triangles and squares in is equal to the number of triangles and squares you have in . In other words, if we denote to be the number of triangles in and to be the number of squares, you need to solve the two equations:
These are two non-linear equations in two variables ( and ), and you can hope that they have a solution of the type you are looking for. In any case, solving them won’t be easy: first, you again need to know the normalizing factor , and again there is a summation over all graphs on vertices; not a pretty sight. Second, how do you even solve such non-linear equations? How do you get guarantees on the solution?
The ability to sample graphs according to offers at least some condolences: we can enumerate over values of and which we deem worthy, generate many random graphs, and calculate the empirical average of the number of triangles and squares for those particular values. By the law of large numbers, these should converge to the true values, if we take enough samples (but then again, how many samples is “enough samples”?)
Actually, with regards to modeling the real world, we’ve only scratched the surface. Real networks sometimes have asymmetrical relations (i.e directed edges), they have different types of nodes which correspond to different types of real-life entities, and are in general hard to deal with. For an offbeat worked-out example of this sort of analysis on a modern social network, see this blog post.
A new hope
Luckily, there is still ongoing mathematical research in the field. My advisor and I have recently uploaded a paper to the arXiv which shows that exponential random graphs can actually be seen as a mixture of graphs with independent edges. We don’t know how those mixtures behave yet, but we do have something to say about how those independent edges look like. Generating and modeling graphs with independent edges is certainly easier than dealing with the straightforward exponential definition. And maybe if we put our minds to it, we’ll find out that exponential random graphs aren’t that unmanageable after all.