使用用户指定的全局聚类系数有效生成随机图

Question

我正在研究大规模神经网络,我需要生成代表网络拓扑的随机图.

我希望能够指定这些图的以下属性:

• 节点数,N(〜= 1000-10000)
• 任意两个给定节点之间连接的平均概率,p(~0.01-0.2)
• 全局聚类系数,C(~0.1-0.5)

理想情况下,应从满足这些用户指定标准的所有可能图形的集合中均匀地绘制随机图.

目前我正在使用一种非常粗略的随机扩散方法,我开始使用具有所需大小和全局连接概率的Erdos-Renyi随机网络,然后在每一步中我随机重新连接一部分边缘.如果重新布线使我更接近所需的C,那么我将重新布线的网络保持在下一次迭代中.

这是我当前的Python实现:

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 > 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 < 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

这适用于小型网络(N <500),但随着节点数量的增加,它很快变得难以处理.生成200节点图需要大约20秒,生成1000节点图需要几天.

有谁能建议一个有效的方法来做到这一点？

Answer 1

阅读了一些内容后，看起来最好的解决方案可能是本文中提出的格里森算法的通用版本。不过我还是不太明白如何实现，所以暂时就在研究Bansal等人的算法。

就像我的天真的方法一样，这是一种基于马尔可夫链的方法，使用随机边缘交换，但与我的方法不同，它专门针对图形中的“三元组图案”进行重新布线：

由于这将更容易引入三角形，因此对聚类系数的影响也更大。至少在无向图的情况下，重新布线步骤也保证保留度序列。同样，在每次重新连线迭代中，都会测量新的全局聚类系数，如果 GCC 更接近目标值，则接受新图。

Bansal 等人实际上提供了一个 Python 实现，但由于各种原因我最终编写了自己的版本，您可以在这里找到。

表现

与我的朴素扩散方法相比，Bansal 方法只需要一半以上的迭代次数和一半的总时间​​：

我希望获得更大的收益，但 2 倍加速总比没有好。

推广到有向图

Bansal 方法剩下的一个挑战是我的图是有向的，而 Bansal 等人的算法仅设计用于无向图。对于有向图，重新布线步骤不再保证保留入度和出度序列。

更新

我刚刚弄清楚如何推广 Bansal 方法来保留有向图的入度和出度序列。诀窍是选择要交换的两个向外边缘具有相反方向的图案（{x, y1} 和 {x, y2} 之间的边缘方向无关紧要）：

我还做了一些更多的优化，并且性能开始看起来更可观——与扩散方法相比，它大约需要一半的迭代次数和一半的总时间​​。我已经用新的时间更新了上面的图表。