如何在 python 中使用 networkx 找出谁是网络中最重要的个体？

Question

我正在使用 facebook 快照数据集，并在 python 上使用 networkX 在其上制作图表。但是找不到最重要的或者你可以说是网络中连接最多的一个。

我在 facebook 快照数据集上制作图表时使用的代码在这里：

import networkx as nx
import matplotlib.pyplot as plt


'''Exploratory Data Analysis'''
g = nx.read_edgelist('facebook_combined.txt', create_using=nx.Graph(), nodetype=int)
print nx.info(g)

'''Simple Graph'''
sp = nx.spring_layout(g)
nx.draw_networkx(g, pos=sp, with_labels=False, node_size=35)
# plt.axes("off")
plt.show()

它给出的结果是这样的：

数据集的link是here

数据集的来源是here

但问题是我怎样才能找到这个网络中最重要的人？

Answer 1

定义 "importance" 的一种方法是个体的中介中心性。介数中心性衡量有多少条最短路径通过特定顶点。通过该顶点的最短路径越多，该顶点对网络的影响就越大。

因为任何一对顶点之间的最短路径可以独立于任何其他一对顶点来确定。为此，我们将使用 multiprocessing library and the itertools 库中的 Pool 对象。

我们需要做的第一件事是将网络的顶点划分为 n 个子集，其中 n 取决于我们可以访问的处理器数量。例如，如果我们使用具有 32 个内核的机器，我们将 Facebook 网络划分为 32 个块，每个块包含 128 个顶点。

现在我们可以让 32 个处理器并行计算 128 个顶点中的每一个顶点的介数，而不是一个处理器计算所有 4,039 个顶点的介数。这大大降低了算法的 run-time 并允许它扩展到更大的网络。

我使用的代码是这样的：

import networkx as nx
import matplotlib.pyplot as plt


'''Exploratory Data Analysis'''
    g = nx.read_edgelist('facebook_combined.txt', create_using=nx.Graph(), nodetype=int)
print nx.info(g)

'''Parallel Betweenness Centrality'''
from multiprocessing import Pool
import itertools

spring_pos = nx.spring_layout(g)


def partitions(nodes, n):
    # '''Partitions the nodes into n subsets'''
    nodes_iter = iter(nodes)
    while True:
        partition = tuple(itertools.islice(nodes_iter,n))
        if not partition:
            return
        yield partition


def btwn_pool(G_tuple):
    return nx.betweenness_centrality_source(*G_tuple)


def between_parallel(G, processes=None):
    p = Pool(processes=processes)
    part_generator = 4 * len(p._pool)
    node_partitions = list(partitions(G.nodes(), int(len(G) / part_generator)))
    num_partitions = len(node_partitions)

    bet_map = p.map(btwn_pool,
                    zip([G] * num_partitions,
                        [True] * num_partitions,
                        [None] * num_partitions,
                        node_partitions))

    bt_c = bet_map[0]
    for bt in bet_map[1:]:
        for n in bt:
            bt_c[n] += bt[n]
    return bt_c


bt = between_parallel(g)
top = 10

max_nodes = sorted(bt.iteritems(), key=lambda v: -v[1])[:top]
bt_values = [5] * len(g.nodes())
bt_colors = [0] * len(g.nodes())
for max_key, max_val in max_nodes:
    bt_values[max_key] = 150
    bt_colors[max_key] = 2

plt.axis("off")
nx.draw_networkx(g, pos=spring_pos, cmap=plt.get_cmap("rainbow"), node_color=bt_colors, node_size=bt_values,
                 with_labels=False)

plt.show()

它给出的输出：

现在，让我们看一下网络中具有前 10 个最高介数中心性度量的顶点。如您所见，主要位于集线器中心或充当两个集线器之间桥梁的顶点具有更高的介数中心性。桥顶点具有高介数，因为连接枢纽的所有路径都经过它们，而枢纽中心顶点具有高介数，因为所有 intra-hub 路径都经过它们。

如何在 python 中使用 networkx 找出谁是网络中最重要的个体？

How to find who is the most important individual in the network using networkx in python?

python

facebook

dataset

networkx

network-analysis