(очень) короткая заметка о том, как мы использовали машины, чтобы понять людей

Прошло почти столетие с тех пор, как Фригьес Каринти впервые ввел понятие степеней разделения, постулировав, что любой человек на Земле находится не более чем в шести шагах от любого другого человека. Сначала опровергнутая, затем скептически принятая и недавно доказанная, эта теория была частью гипотезы «сокращающегося мира», которая, как ни странно, была сформулирована до появления какой-либо крупномасштабной коммуникационной сети.

В wethepeople нас всегда интересовала концепция сообщества: что объединяет людей, почему и как. Вот почему мы с нетерпением ждали визита профессора Баллинга в программу анализа данных Гентского университета в начале прошлой недели и ухватились за возможность поучаствовать в неделе интенсивных исследований под его руководством.

Наша задача: составить карту сети

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

Задача состояла в том, чтобы использовать данные о последователях первой степени для выявления сообществ среди последователей второй степени. Как это работает? Давайте посмотрим на это графическое представление сети:

Наш эпицентр — в нашем случае белая точка — имеет четырех последователей: a, b, c и d. У всех из них есть подписчики: но хотя мы можем получить сами узлы (светло-голубые подписчики), мы не можем видеть связь между ними из-за их настроек конфиденциальности. Это типичный случай в социальных сетях (подумайте, как вы можете видеть полный профиль вашего друга, но не его друзей на Facebook), и он решается различными способами.

Задача для нас заключалась в том, как оценить эти связи второй степени и, что более важно, как сделать это с наименьшим возможным объемом вычислений.

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

С точки зрения непрофессионала, если я дружу с Анной, Бобом и Карлом, а вы дружите с Анной и Бобом, то есть довольно большой шанс, что мы сами можем быть друзьями. Итак, если мы возьмем приведенную выше сетевую матрицу A, где 1 обозначает связь между узлами строки и столбца, а 0 — не связь, и применим следующую формулу:

мы получаем эту матрицу смежности:

что позволяет сделать ряд соображений.

Во-первых, у автора самая высокая степень (оценка 3), что означает, что он является самым подключенным узлом в этой сети. Во-вторых, можно с уверенностью предположить, что читатель и автор связаны (оценка 2 на пересечении их строки и столбца), тогда как читатель и посторонний совершенно не связаны (оценка 0) друг от друга. Если бы мы формировали сообщество, мы бы рассматривали кластеризацию автора и читателя, и если бы мы затем хотели, скажем, распространить сообщение или рекламировать продукт, мы, вероятно, нацелились бы на автора.

Но что мы могли делать дальше?

Применение теории на практике

Основная проблема в реальном сценарии связана с проклятием размерности: легко получить информацию об ограниченном количестве узлов в сети и сохранить результирующую матрицу смежности; но когда мы развертываем систему в крупномасштабных условиях, все становится сложнее.

Это почему? Предположим, у каждого человека в нашей сети 200 подписчиков. Это означает, что наш эпицентр будет иметь 200 связанных узлов, и у каждого из этих узлов будет еще 200 последователей, что приведет к 40 000-гранной матрице смежности с одним миллиардом шестьсот миллионов элементов,каждый из которых мы приходится сканировать с помощью невыносимо медленного бесплатного Twitter API.

Мы устранили это узкое место несколькими способами, используя альтернативные оболочки для получения наших данных и в конечном итоге переключившись на сканирование идентификаторов пользователей (ограничение 5000 на пакетный запрос) вместо полных профилей (180 на запрос). Результаты? На самом деле неплохо.

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

пользователи, которых мы должны были идентифицировать, отмечены зелеными точками: они имеют самую высокую степень, что означает, что они очень тесно связаны со всеми другими узлами. Для этого мы сначала использовали визуальное представление — построили большие тепловые карты и искали яркие пятна, чтобы идентифицировать тех, кто оказывает большое влияние:

По мере того, как наша матрица смежности становилась все больше и больше, мы больше не могли идентифицировать эти узлы вручную. Мы написали ряд функций, которые позволили нам извлекать всех последователей с заданной степенью за разумное время. Получив полную сеть, мы в последний раз провели анализ, а затем наблюдали, как наша система выдает в общей сложности одиннадцать имен — наше основное сообщество в сети.
Мы молча смотрели на экран, а затем повернулись к Брэму — эпицентру нашей сети. Нам не нужно было слов — его лицо говорило все, что можно было сказать.

Когда теория встречается с практикой

Из этих двенадцати имен одно было городом, в котором мы все живем. Пять были людьми, которые вместе учились в старшей школе, восемь — группой лучших друзей, и все они были коллегами в Гентском университете. И вот они!

И оказывается, нам даже не нужна вся сеть, чтобы получить разумную оценку сообщества. кажется, что около 30% достаточно — и улучшения, как правило, выходят на плато после того, как было использовано около 50% от общего набора данных.

И если у нас есть предварительные знания о вовлеченных сообществах, это становится еще лучше. Когда мы используем известные сообщества для экстраполяции других сетевых кластеров, оказывается, что горстки пользователей (около 3% от всей сети) достаточно, чтобы спрогнозировать всю сеть с точностью 80% или более.

думать наперед

В среднем на написание исследовательской работы wethepeople уходит около месяца. На нашу интенсивную неделю с профессором Боллингсом у нас была десятая часть этого времени — всего три дня. В некотором смысле кажется, что мы даже не коснулись всего, что можно было бы сделать с помощью такого рода систем прогнозирования: выявление сообществ и кластеров взаимодействия может стать ключевым моментом будущей политики, городского планирования, рекламы, социальные вмешательства и экономические прогнозы.

Эволюционная психология устанавливает верхнюю границу среднего сообщества максимум в 50 человек. В последнее время демографический бум, интернет-революция и возросшая мобильность прошлого века столкнули нас с ограничениями наших инструментов: долгое время нам приходилось доверять интуиции и использовать обоснованные предположения, чтобы понять, как люди объединяются.

Это больше не так. Большая вычислительная мощность и настоящий поток данных дали нам достаточно, чтобы снова начать понимать людей. В ближайшие годы люди будут больше двигаться, больше общаться, больше собираться вместе. И все же я полностью уверен, что наше поколение сможет — впервые за долгое время — полностью понять эти потоки и действовать в соответствии с ними, чтобы создать лучшее, более рациональное и более взаимосвязанное будущее. И однажды мы просто сформируем одно большое связанное сообщество — без каких-либо степеней разделения.

без степеней разделения — это отчет об исследовании wethepeople, основанный на неделе интенсивного обучения, проведенной профессором Мишель Боллингс из Университета Теннесси, Ноксвилл, в Гентском университете.

Отчет основан на работах Федерико Торри, Маттиаса Баэтенса, Брэма Лавенса, Кевина де Бека и Натали ван Кенхове.