<p>Kolda et al. proposed the <a href="https://arxiv.org/pdf/1302.6636.pdf" rel="nofollow noreferrer">BTER model</a> (2013) that can generate random graphs with prescribed degree and clustering coefficient distribution (and thus prescribed global clustering index). It seems a bit more complicated than my model (see above), but maybe it's faster or generates less biased graphs. (But to be honest, I assume that my model doesn't generate severely biased graphs, neither, but essentially random graphs.)</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>