ConfigModel_MCMC

它是什么？

ConfigModel_MCMC是一个从配置模型中采样网络的工具，给定一个网络和一个图空间。此代码包建立在 Fosdick 等人的 Double Edge Swap MCMC Graph Sampler 之上。[1]。它检测 Double Edge Swap MCMC 中的收敛性，并从 MCMC 的平稳分布中对网络进行采样，从而使样本是从配置模型中均匀随机抽取的。

可以在此处的 arXiv 上找到相应的论文。

[1] Bailey K. Fosdick、Daniel B. Larremore、Joel Nishimura、Johan Ugander（2018 年）配置具有固定度数序列的随机图模型。暹罗评论 60(2):315–355。

为什么使用 ConfigModel_MCMC？

Newman [2] 描述的随机存根匹配算法也由Python 中networkx包的configuration_model函数实现，仅适用于每个网络存根都有不同标签的循环多图空间。这是因为算法返回的图是伪图，即允许图同时具有自环和平行边（多边）。实践者经常去除自环并折叠函数返回的网络中的多边以获得简单的网络，但是这种修改改变了网络的度数序列。它还在网络生成过程中引入了偏差，因为与低度节点相比，高度节点更有可能附着自环和多边。因此，生成的网络是有偏差的样本。ConfigModel_MCMC包允许您在八个不同的图形空间上从配置模型中采样一个无偏样本，这些图形空间由自环/无自环、多边/无多边和存根标记/顶点标记参数化。

[2] MEJ Newman (2003)，“复杂网络的结构和功能”，SIAM REVIEW 45(2):167-256。

安装

pip install ConfigModel_MCMC

这个包已经用 Python=3.7 测试过，需要包 numpy>=1.17.1, networkx>=2.4, scipy>=1.4.1, numba==0.49.1, arch==5.0.1, igraph== 0.9.6 和 tq​​dm==4.62.2。这些依赖项会在安装包时自动安装。

确保已安装最新版本的软件包。要检查，请执行以下命令：

pip show ConfigModel_MCMC

将显示有关包的详细信息，包括摘要、版本、作者等。版本号应该是0.0.10。如果没有，请尝试再次卸载并安装该软件包，或执行以下命令：

pip install ConfigModel_MCMC==0.0.10

设置

arch 模块使用OpenBLAS 模块来估计 DFGLS 测试的模型参数。由于OpenBLAS单独使用多线程，建议在启动 Python 之前限制线程数，尤其是在高计算集群上运行此包时。

例如，如果您使用的是 Jupyter Notebook，请在启动 Jupyter 之前在终端中执行以下命令。

$ export MKL_NUM_THREADS=1
$ export OPENBLAS_NUM_THREADS=1
$ jupyter notebook

或者，如果您从终端运行名为 test.py 的脚本，则可以执行以下命令。

$ export MKL_NUM_THREADS=1
$ export OPENBLAS_NUM_THREADS=1
$ python test.py

这会将多线程限制为单个线程。您可以选择其他线程数，例如 2、4 等，具体取决于可用 CPU 内核的数量。在集群上，通常建议将其限制为每个进程 1 个线程。

例子

一个简单的例子。

这是一个基本的例子。

import ConfigModel_MCMC as CM
import networkx as nx

# An example network 
G = nx.gnp_random_graph(n = 100, p = 0.1)

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = CM.MCMC(G, allow_loops, allow_multi, is_vertex_labeled)

# Get a new graph (G2) from the Configuration model
G2 = mcmc_object.get_graph()

在上面的例子中，G_2从带有顶点标记的简单图空间中采样。图空间的指定取决于生成的网络是否允许有自环、是否有多重边以及是否带有存根标记或顶点标记。G_2具有与示例网络相同的度数序列G。有关如何为给定研究问题选择正确图空间的详细信息，请参阅[1] 。

如果未指定图空间，则默认选择简单的顶点标记图空间。在下面的示例中，图G_2是从简单的顶点标记图空间中获得的。

# An example network 
G = nx.gnp_random_graph(n = 100, p = 0.1)

# Specify the graph space and create a new object
mcmc_object = CM.MCMC(G)

# Get a new graph (G_2) from the Configuration model
G2 = mcmc_object.get_graph()

采样多个图表

也可以使用/不使用循环从配置模型中采样多个图。

# An example network 
G = nx.gnp_random_graph(n = 100, p = 0.1)

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = CM.MCMC(G, allow_loops, allow_multi, is_vertex_labeled)

# Get 5 graphs from the Configuration model over a loop and print their degree assortativity.
for i in range(5):
    G_new = mcmc_object.get_graph()
    print(round(nx.degree_pearson_correlation_coefficient(G_new),4), end = " ")
print()

# Get 5 more graphs using a single line.
list_of_graphs = mcmc_object.get_graph(count=5)
for each_graph in list_of_graphs:
    print(round(nx.degree_pearson_correlation_coefficient(each_graph),4), end = " ")
print()

输出：

-0.0564 -0.0177 -0.0583 0.027 0.0778 
-0.0405 -0.0276 -0.0053 0.016 -0.0153

在上面的代码中，前 5 个网络是通过循环生成的，而接下来的 5 个网络是使用单个命令通过指定count=5为函数的参数来生成的get_graph( )。平均而言，这两种方式同样有效。的默认值为count1。 打印生成的每个网络的度相配性值以供参考。

使用 igraph

默认情况下，从配置模型中采样的网络是networkxGraph 对象。如果希望采样网络成为igraphGraph 对象，则可以将其指定为函数的return_type参数，get_graph( )如下所示。使用“igraph”通常比使用“networkx”快得多。当最终目标是计算采样图的一些网络统计数据时，这也很有帮助，因为igraph提供了几个广泛使用的网络统计数据的极其省时的实现。

# An example network 
G = nx.gnp_random_graph(n = 100, p = 0.1)

# Specify the graph space and create a new object (using default graph space here)
mcmc_object = CM.MCMC(G)

# Get 5 more graphs using a single line.
list_of_graphs = mcmc_object.get_graph(count=5, return_type = "igraph")

采样间隙启发式

如果网络不满足自动选择采样间隙的条件，将运行采样间隙算法。如果网络很大，此功能可能需要一段时间。

# read the Karate Club network
G = nx.karate_club_graph()

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = CM.MCMC(G, allow_loops, allow_multi, is_vertex_labeled)

# Obtain 5 graphs from the Configuration model
list_of_graphs = mcmc_object.get_graph(count=5)

输出：

The network does not satisfy the density criterion for automatic selection of sampling gap.
Running the Sampling Gap Algorithm. This might take a while for large graphs.....
----- Running initial burn-in -----
100%|████████████████████████████         | 78000/78000 [00:33<00:10, 229.00it/s]
----- Initial burn-in complete -----

上面的代码读取空手道俱乐部网络并从带有顶点标记的简单图空间中采样 5 个图。该网络不满足自动选择采样间隙所需的约束，因为它的密度相当高。所以调用了采样间隙算法。在 MCMC walk 的老化期间会显示一个进度条。该变量list_of_graphs包含从配置模型中采样的 5 个简单的顶点标记图。

verbose = False可以通过在创建 MCMC 对象时指定来静音输出中打印的消息。默认值为verbose = True。

# read the Karate Club network
G = nx.karate_club_graph()

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = CM.MCMC(G, allow_loops, allow_multi, is_vertex_labeled, verbose=False)

# Obtain 5 graphs from the Configuration model
list_of_graphs = mcmc_object.get_graph(count=5)

运行采样间隙算法

如果您想运行采样间隙算法来为您的图形获得定制的采样间隙，您可以执行以下操作：

# read the Karate Club network
G = nx.karate_club_graph()

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = CM.MCMC(G, allow_loops, allow_multi, is_vertex_labeled, verbose=False)

# run the Sampling Gap Algorithm
sampling_gap = mcmc_object.run_sampling_gap_algorithm()
print("Sampling gap obtained = ", sampling_gap)

输出：

Sampling gap obtained = 162

请注意，每次运行中获得的采样间隙可能会有所不同，尽管它在一个值附近大部分是稳定的。verbose = False同样，通过在创建 MCMC 对象时指定，此处的打印语句被静音。特别是采样间隙算法的打印语句可以使用以下代码静音，即使它在创建 MCMC 对象时没有静音。

# read the Karate Club network
G = nx.karate_club_graph()

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = MCMC(G, allow_loops, allow_multi, is_vertex_labeled)

# run the Sampling Gap Algorithm
sampling_gap = mcmc_object.run_sampling_gap_algorithm(verbose=False)
print("Sampling gap obtained = ", sampling_gap)

输出：

Sampling gap obtained = 159

自相关假设检验的默认显着性水平 = 0.04，并且为采样间隙算法运行的默认并行 MCMC 链数 = 10。但是，您可以通过将其指定为函数的参数来更改它们。例如，我们可以将显着性水平设置为 10%，并运行 20 个并行 MCMC 链，如下所示：

# read the Karate Club network
G = nx.karate_club_graph()

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = MCMC(G, allow_loops, allow_multi, is_vertex_labeled, verbose=False)

# run the Sampling Gap Algorithm
sampling_gap = mcmc_object.run_sampling_gap_algorithm(alpha = 0.1, D = 20)
print("Sampling gap obtained = ", sampling_gap)

输出：

Sampling gap obtained = 189

由于显着性水平和平行链的数量都增加了（分别从 0.04 到 0.1 和从 10 到 20），Sampling Gap 将比之前获得的更高，因为现在测试更加保守，并且 Sampling Gap在这种情况下，算法将需要更多时间来运行。

自定义采样间隙

sampling_gap您还可以使用函数参数指定要运行收敛检测测试的自定义采样间隙。

# read the Karate Club network
G = nx.karate_club_graph()

# Specify the graph space and create a new object
allow_loops = False
allow_multi = False
is_vertex_labeled = True
mcmc_object = MCMC(G, allow_loops, allow_multi, is_vertex_labeled, verbose=False)

# Specify the sampling gap 
gap = 100 # any user-defined value
list_of_graphs = mcmc_object.get_graph(count=5, sampling_gap = gap)
for each_graph in list_of_graphs:
    print(round(nx.degree_pearson_correlation_coefficient(each_graph),4), end = " ")

print()
print("User-defined sampling gap = ", mcmc_object.spacing)

输出：

-0.298 -0.2739 -0.3224 -0.3042 -0.2396
User-defined sampling gap =  100

笔记

该软件包不适用于加权网络、有向网络、超图或单纯复形。

反馈和错误

如果您发现错误或有任何反馈，请发送电子邮件至upasana.dutta@colorado.edu给我。

执照

GNU 通用公共许可证 v3