С графами
сегодня можно работать в большом количестве программ. Как правило, начинают с UCINET, Gephi, ORA. В них просто рассчитать описательную статистику и нарисовать красивые сети.
Однако основные программы, которые позволяют делать с графами более сложные
вещи — это R и Python. Мы привыкли работать в R, но недавно решили
подробнее изучить сетевые пакеты в Python.
Один их самых известных пакетов в Python - это networkx. Что обещает networkx? Большинство
стандартных сетевых метрик, работа с различными типами связей и узлов, а самое главное - весь функционал, простоту и
скорость Python'a. Что не может дать? Хорошую визуализацию графов.
Мы взяли набор больших сетевых данных и проанализировали его в Python 3, используя пакет networkX. Для этого поста мы использовали материалы этой лекции, а также документацию самого пакета.
In [ ]:
### Установка NetworkX
# Для начала, нужно установить этот пакет.
# Это можно сделать несколькими способами с этого сайта:
# https://networkx.github.io/download.html
# Один из самых простых, на наш взгляд, - это набрать в терминале pip install networkx
In [ ]:
### Импорт NetworkX в Python
# Если все прошло успешно, то импортируем NetworkX в Python:
import networkx
from networkx import *
In [ ]:
### Найдем базу данных
# Для примера будем использовать одну из баз данных Ю. Лесковца по сетям в Фейсбуке.
# Зайдем на эту страницу: https://snap.stanford.edu/data/egonets-Facebook.html
# Скачаем оттуда файл "facebook_combined.txt.gz"
# Как понятно из описания, это дружеские сети пользователей Фейсбука
# Это 10 эго-сетей, соединенных в одну большую сеть
In [ ]:
# Если разархивировать файл и посмотреть в любом текстовом редакторе,
# мы увидим, что данные представлены как edgelist.
# Первые 5 строк выглядят так:
# 0 1
# 0 2
# 0 3
# 0 4
# 0 5
# В первом и втором столбце узлы
# Мы видим, что узел "0" связан с узлами "1", "2", "3", "4", "5"
In [ ]:
### Распакованный файл положим туда, где у нас рабочая директория
import os
os.getcwd()
Out[ ]:
In [ ]:
### Прочитаем наш файл и назовет граф "g"
g = read_edgelist("facebook_combined.txt")
In [ ]:
# Посмотрим на количество узлов в графе
g.number_of_nodes()
Out[ ]:
In [ ]:
# Посмотрим на количество связей в графе
g.number_of_edges()
Out[ ]:
In [ ]:
# Можно посмотреть список всех узлов, набрав g.nodes(),
# А список связей между ними - набрав g.edges()
# Не будем этого здесь делать, потому что 4 тысячи узлов и их связи занимают много места :)
In [ ]:
### Визуализация графа
# Сами авторы пишут, что их пакет плохо предназначен для визуализации графов
# Поэтому используются другие пакеты из группы научных пакетов Python'a
# Импортируем для этих целей пакет "pylab"
import pylab as plt
# Если его нет - то можно его поставить, например, отсюда:
# https://pypi.python.org/pypi/pylab
# Matplotlib напишет, что ему нужно время подумать...
In []:
# Нарисуем граф и сохраним его в .png. Он должен сохраниться в нашей рабочей директории
nx.draw(g)
plt.savefig('graph.png')
plt.close()
# У меня получился такой красный человек-птица-цветок
In [ ]:
### Описательная статистика графа
## Степень
# Можно посмотреть степень каждого узла, набрав "g.degree()"
# Первые 5 строк огромного output'а выглядят примерно так:
# {u'1200': 4,
# u'3162': 57,
# u'4026': 9,
# u'1869': 15,
# u'4024': 1,...}
In [ ]:
## Посмотрим на распределение степени на графике
degree = g.degree()
degree_values = sorted(set(degree.values()))
hist = [degree.values().count(x) for x in degree_values]
plt.figure()
plt.plot(degree_values, hist,'ro-')
plt.legend(['Degree'])
plt.xlabel('Degree')
plt.ylabel('Number of nodes')
plt.title('Facebook Graph')
plt.savefig('facebook_degree_plot.png')
plt.close()
# Получившийся график должен появиться в рабочей директории
# Выглядит он так:
In [ ]:
# Как обычно, мы видим, что у нас очень большое количество узлов имеют малую степень,
# а очень малое количество - большую степень
In [ ]:
### Центральности
# Так как наш граф ненаправленный, мы можем проделать не так много всего.
# Посчитаем 3 стандарные меры центральностей: betweenness, closeness, eigenvector
# На моем компьютере это заняло достаточно длительное время,
# networkx правда не идеален для таких больших графов.
# Betweenness centrality, или посредничество
# Эта мера показывает, насколько узел связывает несколько несвязанных сообществ,
# или занимает позицию "между"
bet_centr = nx.betweenness_centrality(g)
# Closeness centrality
# Эта мера показывает, насколько узел близок ко всем остальным узлам в сети
clo_centr = nx.closeness_centrality(g)
# Eigenvector centrality
# Эта мера показывает, насколько узел связан с узлами,
# которые сами имеют большое количество связей
eig_centr = nx.eigenvector_centrality(g)
# Получаем индидивидуальные меры посредничества, близости и eigenvector для каждого узла
print bet_centr
print clo_centr
print eig_centr
In [ ]:
### Сохраним полученные меры центральностей в таблицу
# Файл должен появиться в рабочей директории
results = [(k,bet_centr[k],clo_centr[k],eig_centr[k])
for k in g]
f = open('facebook_graph_results.txt','w')
for item in results:
f.write(','.join(map(str,item)))
f.write('\n')
f.close()
Помимо networkx, основные пакеты для сетевого анализа в Python — это igraph и graphtool. Igraph является уже привычным, он также есть в R (и в С/C++). В нем можно считать многие все сетевые статистики и визуализировать графы. Graphtool обещает очень высокую скорость, особый подход к большим графам и качественную визуализацию.
В целом, в чем преимущество Python’a перед R, например? Python намного лучше справляется с большими графами, а также с его помощью намного проще выгружать данные из онлайн сетей. Про получение данных из онлайна рекомендуем книгу Mining the Social Web. В ней много Python’овских скриптов и понятных объяснений того, как получить данные из Facebook, Twitter, LinkedIn, Google+, электронной почты и интернета в целом. Книгу можно скачать бесплатно, все скрипты лежат на GitHub’e автора, и на любой вопрос по этой книге можно найти ответ в форумах.
