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

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

你是对的。这是一种非常昂贵的方法来实现你想要的。我只能推测是否有一种数学上合理的方法来优化并确保它接近均匀分布。我什至不确定您的方法是否会导致均匀分布，尽管看起来会这样。让我试试:

基于 the docs for transitivity_undirected和 wikipedia Clustering Coefficient ，听起来好像可以在图中进行局部更改，同时知道对全局连接和全局聚类的确切影响。

The global clustering coefficient is based on triplets of nodes. A triplet consists of three nodes that are connected by either two (open triplet) or three (closed triplet) undirected ties. A triangle consists of three closed triplets, one centred on each of the nodes. The global clustering coefficient is the number of closed triplets (or 3 x triangles) over the total number of triplets (both open and closed).

---

( * edit * ) 根据我对 ali_m 引用的论文的阅读，下面的方法可能会在低度聚类上花费太多边，导致图形无法达到所需的聚类系数，除非它非常低(无论如何这可能都没有用)。因此，如果有人实际使用它，您将希望识别更高度的聚类以添加边，以便快速提高聚类系数而无需添加大量边。

另一方面，下面的方法确实与研究论文中的方法一致，因此或多或少是一种合理的方法。

---

如果我没理解错的话，你可以这样做:

1. 像您所做的那样制作图表。

2. 计算和跟踪:

   • p_surplus 跟踪需要在其他地方添加或删除以保持连接的边缘数
   • cc_top, cc_btm 跟踪聚类系数

3. 迭代(不完全)选择随机对并将它们连接或断开以单调接近您想要的聚类系数 (cc)，同时保持您已有的连通性 (p)。

   伪代码:

   for random_pair in random_pairs:
   
       if (random_pair is connected) and (need to reduce cc or p):  # maybe put priority on the one that has a larger gap?
           delete the edge
           p_surplus -= 1
           cc_top -= broken_connected_triplets  # have to search locally
           cc_btm -= (broken_connected_triplets + broken_open_triplets)  # have to search locally
       elif (random_pair is not connected) add (need to increase c or p):
           add the edge
           p_surplus += 1
           cc_top += new_connected_triplets
           cc_btm += (new_connected_triplets + new_open_triplets)
   
       if cc and p are within desired ranges:
           done
   
       if some condition for detecting infinite loops:
           rethink this method
   

这可能不完全正确，但我认为这种方法会奏效。效率搜索本地三元组并始终向正确的方向移动参数会更好而不是复制图形并全局测量 cc 这么多次。