Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution

I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution.

The degree distribution is the relative frequency of vertexes in the original graph that have a certain degree.

The clustering coefficient distribution is the relative frequency for each vertex degree of two neighbours (of a vertex with that degree) to have a link between them.

Does anybody know any literature and algorithm to do this? The stuff I have found was always very theoretical..

Thanks!

• Google (Scholar) "random sampling". There's a bunch of literature on the topic. Unfortunately (and afaik), sampling graphs is a ficklish matter since you almost never know the proper model.
– Raphael
May 28, 2014 at 6:31
• @Raphael This is not sampling from a graph, this is generating a full new graph based on the properties of another graph. While in sampling you choose randomly a part of the original graph. May 28, 2014 at 8:18

You may want to have a look at the block two-level Erdos-Renyi model (BTER). The usual preferential attachment mechanism for generating scale-free networks doesn't capture the clustering coefficient right, and small-world networks aren't scale-free; the BTER model can capture both scale-free and clustering behavior. I think they have some way to make it work for an arbitrary degree distribution (not just scale-free). The link I gave above has code for generating BTER graphs too.

As far as I know, clustering coefficient determines the degree to which nodes in the graph tend to cluster together, and the degree shows how individuals behave for choosing their neighbors.

I usually use GTgraph to generate random graphs. You may use Erdos-Reyni graphs if the degree distribution matters or use SSCA graphs if you are looking for cliques and the nodes that are densely connected to each other.

• Generaly clustering coefficient (cc) is defined as you said but, there are many different ways to determine it. For this cc I based on this article from Leskovec et al. But isn't there a algorithm to generate a graph based on a known degree distribution and clustering coefficient? May 28, 2014 at 8:16
• Do you want a random graph generator that reflects the cc the best? May 28, 2014 at 9:39
• I want a random graph generator that reflects the cc and degree distribution the best May 28, 2014 at 9:56

Simulating random graphs with tunable clustering is non-trivial.

One method is that described by Newman. As you say there are various (conflicting) definitions of 'clustering coefficient'. Check the paper and see if it corresponds to yours. In any case you will need to compute an appropriate 'triangle corner' distribution.

Then to simulate the graph with $n$ vertices (which we label from $1$ to $n$):

1. Generate a sequence of independent random variables $D_1, \dots, D_n$ according to your target degree distribution. If the sum of the $D_i$ is odd then add $1$ to $D_1$, say. Now attach $D_i$ 'half-edges', or 'stubs' to vertex $i$. Pair up the half-edges/stubs uniformly.
2. Generate a sequence of independent random variables $T_1, \dots, T_n$ according to the triangle distribution. Adjust $T_1$ appropriately so that the $T_i$ sum to a multiple of $3$. Attach $T_i$ 'triangle corners' to vertex $i$, and repeatedly join $3$ corners together at random, till there are none remaining.
3. You have now generated a 'multigraph'– possibly there are multiple edges and loops. Keep repeating (1)–(2) until you obtain a genuine graph.

This is fairly greedy. It generates a random graph which matches your degree distributions and clustering coefficients. However, it may or may not be a good model for your data.

Edit: the above method is also discussed by Wang along with an alternative.