并行介数中心性

使用Python标准库中的multiprocessing模块实现介数中心性的并行示例。

函数betweenness centrality接受一组节点，并计算这些节点对整个网络介数中心性的贡献。这里我们将网络分成多个节点块，并计算它们对整个网络介数中心性的贡献。

注意：下面的示例输出显示非并行实现更快。这是我们CI/CD流水线在单核上运行的限制。

根据您的设置，您可能会观察到加速。

Computing betweenness centrality for:
Graph with 1000 nodes and 2991 edges
        Parallel version
                Time: 0.4064 seconds
                Betweenness centrality for node 0: 0.10186
        Non-Parallel version
                Time: 1.1611 seconds
                Betweenness centrality for node 0: 0.10186

Computing betweenness centrality for:
Graph with 1000 nodes and 4979 edges
        Parallel version
                Time: 1.0115 seconds
                Betweenness centrality for node 0: 0.00097
        Non-Parallel version
                Time: 1.5840 seconds
                Betweenness centrality for node 0: 0.00097

Computing betweenness centrality for:
Graph with 1000 nodes and 2000 edges
        Parallel version
                Time: 0.4173 seconds
                Betweenness centrality for node 0: 0.00712
        Non-Parallel version
                Time: 1.1020 seconds
                Betweenness centrality for node 0: 0.00712

from multiprocessing import Pool
import time
import itertools

import matplotlib.pyplot as plt
import networkx as nx


def chunks(l, n):
    """将节点列表 `l` 分成 `n` 个块"""
    l_c = iter(l)
    while 1:
        x = tuple(itertools.islice(l_c, n))
        if not x:
            return
        yield x


def betweenness_centrality_parallel(G, processes=None):
    """并行介数中心性函数"""
    p = Pool(processes=processes)
    node_divisor = len(p._pool) * 4
    node_chunks = list(chunks(G.nodes(), G.order() // node_divisor))
    num_chunks = len(node_chunks)
    bt_sc = p.starmap(
        nx.betweenness_centrality_subset,
        zip(
            [G] * num_chunks,
            node_chunks,
            [list(G)] * num_chunks,
            [True] * num_chunks,
            [None] * num_chunks,
        ),
    )

    # 减少部分解决方案
    bt_c = bt_sc[0]
    for bt in bt_sc[1:]:
        for n in bt:
            bt_c[n] += bt[n]
    return bt_c


G_ba = nx.barabasi_albert_graph(1000, 3)
G_er = nx.gnp_random_graph(1000, 0.01)
G_ws = nx.connected_watts_strogatz_graph(1000, 4, 0.1)
for G in [G_ba, G_er, G_ws]:
    print("")
    print("Computing betweenness centrality for:")
    print(G)
    print("\tParallel version")
    start = time.time()
    bt = betweenness_centrality_parallel(G)
    print(f"\t\tTime: {(time.time() - start):.4F} seconds")
    print(f"\t\tBetweenness centrality for node 0: {bt[0]:.5f}")
    print("\tNon-Parallel version")
    start = time.time()
    bt = nx.betweenness_centrality(G)
    print(f"\t\tTime: {(time.time() - start):.4F} seconds")
    print(f"\t\tBetweenness centrality for node 0: {bt[0]:.5f}")
print("")

nx.draw(G_ba, node_size=100)
plt.show()