<p>Having done a bit of reading, it looks as though the best solution might be the generalized version of Gleeson's algorithm presented in <a href="http://arxiv.org/abs/1301.6802" rel="nofollow noreferrer">this paper</a>.  However, I still don't really understand how to implement it, so for the time being I've been working on <a href="http://dx.doi.org/10.1186/1471-2105-10-405" rel="nofollow noreferrer">Bansal et al's algorithm</a>.</p>

<p>Like my naive approach, this is a Markov chain-based method that uses random edge swaps, but unlike mine it specifically targets 'triplet motifs' within the graph for rewiring:</p>

<p><img src="https://i.stack.imgur.com/8SfLA.png" alt="enter image description here"></p>

<p>Since this will have a greater tendency to introduce triangles, it will therefore have a greater impact on the clustering coefficient. At least in the case of undirected graphs, the rewiring step is also guaranteed to preserve the degree sequence. Again, on every rewiring iteration the new global clustering coefficient is measured, and the new graph is accepted if the GCC got closer to the target value.</p>

<p>Bansal et al actually <a href="http://sbansal.com/ClustRNet/" rel="nofollow noreferrer">provided a Python implementation</a>, but for various reasons I ended up writing my own version, <a href="https://gist.github.com/alimuldal/c7e2905f455cac3f01ed" rel="nofollow noreferrer">which you can find here</a>.</p>

<h2>Performance</h2>

<p>The Bansal approach takes just over half the number of iterations and half the total time compared with my naive diffusion method:</p>

<p><img src="https://i.stack.imgur.com/CAKDB.png" alt="enter image description here"></p>

<p>I was hoping for bigger gains, but a 2x speedup is better than nothing.</p>

<h2>Generalizing to directed graphs</h2>

<p>One remaining challenge with the Bansal method is that my graphs are directed, whereas Bansal et al's algorithm is only designed to work on undirected graphs. With a directed graph, the rewiring step is no longer guaranteed to preserve the in- and out-degree sequences.</p>

<hr>

<h2>Update</h2>

<p>I've just figured out how to generalize the Bansal method to preserve both the in- and out-degree sequences for directed graphs. The trick is to select motifs where the two outward edges to be swapped have opposite directions (the directions of the edges between {x, y1} and {x, y2} don't matter):</p>

<p><img src="https://i.stack.imgur.com/Tychd.png" alt="enter image description here"></p>

<p>I've also made some more optimizations, and the performance is starting to look a bit more respectable - it takes roughly half the number of iterations and half the total time compared with the diffusion approach. I've updated the graphs above with the new timings.</p>
Efficiently generating random graphs with a user-specified global clustering coefficient
<p>I'm working on simulations of large-scale neuronal networks, for which I need to generate random graphs that represent the network topology.</p>

<p>I'd like to be able to specify the following properties of these graphs:</p>

<ul>
<li>Number of nodes, <em>N</em> (~=1000-10000)</li>
<li>Average probability of a connection between any two given nodes, <em>p</em> (~0.01-0.2)</li>
<li>Global clustering coefficient, <em>C</em> (~0.1-0.5)</li>
</ul>

<p>Ideally, the random graphs should be drawn uniformly from the set of all possible graphs that satisfy these user-specified criteria.</p>

<p>At the moment I'm using a very crude random diffusion approach where I start out with an Erdos-Renyi random network with the desired size and global connection probability, then on each step I randomly rewire some fraction of the edges. If the rewiring got me closer to the desired <em>C</em> then I keep the rewired network into the next iteration.</p>

<p>Here's my current Python implementation:</p>

<pre><code>import igraph
import numpy as np

def generate_fixed_gcc(n, p, target_gcc, tol=1E-3):
    """
    Creates an Erdos-Renyi random graph of size n with a specified global
    connection probability p, which is then iteratively rewired in order to
    achieve a user- specified global clustering coefficient.
    """

    # initialize random graph
    G_best = igraph.Graph.Erdos_Renyi(n=n, p=p, directed=True, loops=False)

    loss_best = 1.
    n_edges = G_best.ecount()

    # start with a high rewiring rate
    rewiring_rate = n_edges
    n_iter = 0

    while loss_best &gt; tol:

        # operate on a copy of the current best graph
        G = G_best.copy()

        # adjust the number of connections to rewire according to the current
        # best loss
        n_rewire = min(max(int(rewiring_rate * loss_best), 1), n_edges)
        G.rewire(n=n_rewire)

        # compute the global clustering coefficient
        gcc = G.transitivity_undirected()
        loss = abs(gcc - target_gcc)

        # did we improve?
        if loss &lt; loss_best:

            # keep the new graph
            G_best = G
            loss_best = loss
            gcc_best = gcc

            # increase the rewiring rate
            rewiring_rate *= 1.1

        else:

            # reduce the rewiring rate
            rewiring_rate *= 0.9

        n_iter += 1

    # get adjacency matrix as a boolean numpy array
    M = np.array(G_best.get_adjacency().data, dtype=np.bool)

    return M, n_iter, gcc_best
</code></pre>

<p>This is works OK for small networks (<em>N</em> &lt; 500), but it quickly becomes intractable as the number of nodes increases. It takes on the order of about 20 sec to generate a 200 node graph, and several days to generate a 1000 node graph.</p>

<p>Can anyone suggest an efficient way to do this?</p>