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

Question

我正在研究大规模神经元网络的模拟，为此我需要生成代表网络拓扑的随机图。

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

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

理想情况下，随机图应该从满足这些用户指定标准的所有可能图集中统一绘制。

目前，我正在使用一种非常粗糙的随机扩散方法，我从一个鄂尔多斯仁义随机网络开始，具有所需的大小和全局连接概率，然后在每一步上，我随机重新连接一些边。如果重新布线使我更接近所需的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

有人能提出一个有效的方法吗？

Answer 1

我提出了一个图生成模型，可以很容易地生成约10000个节点和更多节点的连接随机图，这些图遵循规定的度和（局部）聚类系数分布，可以选择这样的分布，以获得任何所需的全局聚类系数。你可以在这里找到一个简短的描述。顺便说一下，你可以在参考资料中找到你的问题（这一个）。

Answer 2

在阅读了一点之后，看起来最好的解决方案可能是本文中提出的格里森算法的广义版本。然而，我仍然不太明白如何实现它，所以目前我一直在研究班萨尔等人的算法。

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

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

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

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

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

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

我刚刚想出了如何推广Bansal方法来保留有向图的度内和度外序列。诀窍是选择要交换的两个向外边方向相反的主题（{x，y1}和{x，y2}之间的边的方向无关紧要）：

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

Answer 3

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

基于transitivity_undirected和维基百科聚类系数的文档，听起来可以在图中本地进行更改，同时知道对全局连接和全局聚类的确切影响。

全局聚类系数基于三组节点。三元组由三个节点组成，它们通过两个（开放三元组）或三个（封闭三元组）无向连接线连接。三角形由三个闭合的三元组组成，其中一个以每个节点为中心。全局聚类系数是闭合三元组（或3个三角形）的数量超过三元组总数（开放和闭合）。

（*编辑*）根据我对ali_m引用的论文的阅读，下面的方法可能会在低度聚类上花费太多的边，导致一个图无法达到所需的聚类系数，除非它非常低（无论如何可能都不会有用）。因此，万一有人真的使用它，您将希望识别要添加边的高阶簇，以便快速提高聚类系数，而不需要添加大量边。

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

如果我理解正确，您可以执行以下操作：

>

计算并跟踪：

• p_剩余跟踪需要在其他位置添加或删除以保持连接的边数
• cc_top，cc_btm跟踪聚类系数

迭代地（不完全地）选择随机对并连接或断开它们，以单调地接近您想要的聚类系数，同时保持您已经拥有的连接性（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要好。