Как найти, кто является самым важным человеком в сети, использующим networkx в python?

Question

Я использую набор данных оснастки facebook и строю график на нем, используя networkX на python. Но не удалось найти самое важное или, можно сказать, самое связанное в сети.

Код, который я использую, я делаю график в наборе данных моментальных снимков 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()

Результат, который он дает, таков:

Ссылка на набор данных здесь

Источник набора данных здесь

Но вопрос в том, как мне найти самого важного человека в этой сети?

Answer 1

Одним из способов определения "важности" является центральность между людьми. Центральность промежуточности - это мера того, сколько кратчайших путей проходит через конкретную вершину. Чем больше кратчайших путей проходит через вершину, тем центральнее вершина находится в сети.

Потому что кратчайший путь между любой парой вершин может быть определен независимо от любой другой пары вершин. Для этого мы будем использовать объект Pool из библиотеки многопроцессорной обработки и библиотеки itertools.

Первое, что нам нужно сделать, это разделить вершины сети на n подмножеств, где n зависит от числа процессоров, к которым у нас есть доступ. Например, если мы используем машину с 32 ядрами, мы разделяем сеть Facebook на 32 блока, каждый из которых содержит 128 вершин.

Теперь вместо одного процессора, вычисляющего промежуточность для всех 4039 вершин, у нас может быть 32 процессора, вычисляющих промежуточность для каждой из 128 вершин параллельно. Это значительно сокращает время работы алгоритма и позволяет масштабировать его до более крупных сетей.

Код, который я использовал, это:

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 самых высоких показателей центральности в сети. Как видите, вершины, которые в основном либо находятся в центре концентратора, либо действуют как мост между двумя концентраторами, имеют более высокую центральность между ними. Вершины моста имеют высокую промежуточность, потому что все пути, соединяющие концентраторы, проходят через них, а вершины центра втулки имеют высокую промежуточность, потому что все пути внутри хаба проходят через них.