Скандалы, интриги, расследования и степенной закон

Есть вещи, за которыми можно наблюдать бесконечно. Течение ручья, пламя костра, скандалы, интриги, расследования вокруг степенного закона в сетях. Итак, напомним, чем закончилась предыдущая серия нашего шоу. В начале 2018 года Анна Бройдо и Аарон Клаузет публикуют на arxiv препринт “Scale-free network are rare”. В этой статье на обширном эмпирическом материале они показывают, что на самом деле степени центральности у сетей обычно распределены лог-нормально, а не в соответствии со степенным законом. Иными словами, модель безмасштабных сетей, разработанная А.-Л. Барабаши и Р. Альтерт, может быть ошибочной.
Реакция общественности была разная. Кто-то посчитал это важным эмпирическим результатом, кто-то посетовал на недостаточное количество хороших исследований по сетям и жажду хайпа, а Альберт-Ласло Барабаши призвал коллег думать не об эмпирических подтверждениях, а о механизмах, формирующих социальные системы. Обсуждения в Твиттере были такими жаркими и насыщенными, что ученые уже не казались отстраненными обитателями башни из слоновой кости. Это была практически дуэль в прямом эфире!

Разница между случайными и реальными (например, социальными) сетями. В случайных сетях (слева) у каждого узла примерно одинаковое количество связей. В реальных сетях (справа) есть небольшая группа узлов с очень большим количеством связей, однако большинство узлов имеют достаточно малое количество связей. Источник изображения.

Прошел год, но интерес к теме не утихает. Наконец, статья Бройдо и Клаузет вышла в Nature Communications. Петер Холм в своем комментарии для Nature Communications постарался увязать между собой и теоретическую модель Барабаши-Альберт, и эмпирические результаты Бройдо и Клаузета. При этом в конце 2018 подоспела статья (пока тоже на arxiv) про то, что “scale-free network well done”. Не будем удивляться, что большинство авторов статьи из Northeastern University, где работает и Барабаши, один из основателей модели безмаштабных сетей.
И вот, анализируя то, что происходит, хочется задать вопрос - почему это распределение вызывает столько дебатов? Ведь подавляющее большинство исследователей охотятся не за распределениями, а за объяснением того, что за механизм лежит в основе этих распределений. Барабаши и Альберт не открывали Америку, механизм предпочтительного присоединения в социальных науках известен давно. Это эффект Матфея, по которому распределение благ происходит неравномерно. В случае сетей - популярные люди с течением времени становятся все более популярными. И если эффект Матфея работает и в случае социальных, и других типов сетей, то это важный механизм. Однако могут ли какие-то отдельные особенности распределения и его хвостов опровергнуть этот эффект? В общем, продолжаем следить за сериалом и размышляем, будет ли в результате этой дискуссии выявлен еще какой-то интересный содержательный результат или все же нет. Не хотелось бы, чтобы именитые ученые тратили бы ресурсы на борьбу за амбиции.

Что делать с графами в Python: пример в NetworkX

С графами сегодня можно работать в большом количестве программ. Как правило, начинают с 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[ ]:

'/home/diliara'

In [ ]:

### Прочитаем наш файл и назовет граф "g"
g = read_edgelist("facebook_combined.txt")

In [ ]:

# Посмотрим на количество узлов в графе
g.number_of_nodes()

Out[ ]:

4039

In [ ]:

# Посмотрим на количество связей в графе
g.number_of_edges()

Out[ ]:

88234

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 автора, и на любой вопрос по этой книге можно найти ответ в форумах.