Хабрахабр

Алексей Савватеев: Модели интернета и социальных сетей

«Единственный смысл существование экономики — это воодушевление математиков на новые подвиги.»

image

Я нашел эту тему очень любопытной и незаслуженно забытой. В 2013 году Алексей Савватеев прочитал несколько лекций по моделям соцсетей и интернета. А ещё мне интересно узнать, как изменилась ситуация с тех пор и какие полезные публикации есть в этой области. Попробуем разобраться в вопросе.

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

(Пост выглядит как набор слайдов с цитатами лектора, связать всё в единый и прилизанный текст у меня не хватает способностей к русскому языку и математике, но тема очень важная, поэтому хочу опубликовать.)
Социальная сеть состоит из: Ниже приводится скомпилированная выжимка из трёх видеозаписей лекций, само видео есть в конце.

  • Агентов
  • Связей между агентами

Связи могут быть двусторонние (друзья, соавторство), а могут быть односторонние (подписчики). Социальные существовали всегда, но изучать их на макро уровне стало возможным только с появлением онлайн-сетей. Человечество за последние 10 лет совершило качественный скачок. Оно научилось исследовать всё себя целиком. Может оцифровать. Собрать о себе информацию.

Но нам до этого как до Луны. Было бы честно строить модель взвешенных графов, когда указаны коэффициенты «силы связи».

image

image

image

Галерея

image

Гипотезу, которую вы могли бы выдвинуть, после просмотра картинки может оказаться очевидно абсурдной. На картинки полезно смотреть.

галерея 13 слайдов

Кому полезно изучать соцсети

image

Экономика: Есть предположение, что микро и макро уровень в экономике связаны через «сеть»
Политология: Есть предположение, останется ли режим или поменяется, зависит от того, у кого будут более сильные специалисты по сетям.

image

Пример аналитики соцсетей.

Численные характеристики социальных сетей

  • Расстояние
  • Диаметр
  • Степень вершины
  • Распределение степеней вершины
  • Меры центральности узла
  • Распределение меры центральности
  • Коэффициент кластеризации
  • Коэффициент ассортативности

Расстояние — сколько рёбер минимально нужно пройти, чтобы попасть от одной вершины к другой.

Диаметр — максимальное расстояние в графе.

Степень вершины — количество рёбер у вершины.

Теория шести рукопожатий

Любой социальный граф имеет очень низкий средний диаметр (Теория шести рукопожатий). Причем существует очень плотное ядро. Я «знаком» с каким-нибудь африканцем, через своего президента, который жал руку африканскому президенту.

Мы смотрим всех соседей человека, «к» штук. Локальный коэффициент кластеризации. Мы смотрим на фактическое число ребер и делим на этот максимум. Максимум ребер — к(к-1)/2.

Сколько «треугольников» по сравнению с «галочками». Глобальный коэффициент кластеризации.

Какой % вершин имеет степени меньше 1000? Распределение степеней вершины. Выясняется что у интернета степенная природа. Природа распределения экспоненциальная или степенная?

Вершин, степень которых равна «х», будет N/х2. Коэффициент равен «2». Тысяча тысячников. Проверяем, в ЖЖ миллиард пользователей, тысячников должно быть миллиард разделить на тысячу в квадрате.

Это очень медленно убывающая штука.

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

Берем человека, считаем для него следующую величину. Центральность узла для социальной сети. Может быть несколько кратчайших путей и некоторые из них содержат нашего человека, тогда ставим ему %. Перебираем все пары остальных людей (N-1)(N-2)/2 и в каждом случае спрашиваем, ближайший путь знакомств в графе, проходит ли через этого человека? Для распространения эпидемий, общественных мнений. Это важнейшая характеристика в социальных сетях. Это то что надо измерять.

image

image

image

Особенности социальных сетей:

  • Маленький диаметр и среднее расстояние между вершинами
  • Степенной закон распределения степеней вершин и betweenness centrality
  • Высокий коэффициент кластеризации
  • Ассортативность
  • Наличие тесно связанного ядра

Первые три уже представляют непреодолимую сложность на данный момент времени. Задача — создать модель, которая охватывает первые три свойства (а желательно и последние два). На 2013 год не существует такой модели.

Перейдем к описанию моделей случайных графов которые существовали.

Модели

image

image

image

image

image

image

Модели бывают:

  • Технические (ребра получаются случайным образом)
  • Теоретико-игровые (когда это кому то выгодно)
  • Без структуры (просто множество вершин)
  • Структурные (вершины являются точками метрического пространства или имеют веса, на множестве вершин имеется структура)

image

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

Всё это делается для одной цели — бороться со спамом.

Интернет можно представить как сложную сеть на нескольких уровнях:

  • Технологический уровень. Вершинами и рёбрами являются узлы и линии связи.
  • Гипертекстовый уровень. Вершинами являются сайты или страницы, а рёбрами — гиперссылки.
  • Социальный уровень. Вершинами являются пользователи, а рёбрами – те или иные связи между ними: дружба в социальных сетях, подписка на блоги, совместная работа в распределённых проектах (напр., википедия) и т.п.

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

Выясняется, что для интернет-сетей характерен ряд особенностей:

  • паретто-распределение степеней,
  • высокий коэффициент кластеризации,
  • положительная ассортативность,
  • маленький диаметр.

Конечной целью моделирования интернет-сетей является построения модели с теми же особенностями.

Модель Эрдёша — Реньи

image

Модели названы именами математиков Пала Эрдёша и Альфреда Реньи, которые первыми представили одну из моделей в 1959 году. Модель Эрдёша — Реньи — это одна из двух тесно связанных моделей генерации случайных графов. Исследовали граф знакомств.

Потенциальных рёбер — N*(N-1)/2. Рассмотрим N точек. Вероятность того, что ребро случилось — р. Для каждого ребра мы проводим случайное испытание. Поводим «испытания», получается граф. Что не случилось — (1-р). Чтобы проявилось свойство «разреженности», р должно быть очень маленьким, порядка 1/N, а тогда диаметр будет очень большим. Но есть несколько проблем.

Любой исследователь, который услышит, что интернет описывается как случайный граф по модели Эрдёша — Реньи будет ржать.

Интересный эффект — при преодолении некоего порога вероятности, граф становится связным.

Модель Боллобаши

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

Но эта модель не срабатывает с кластеризацией.

Есть два конкурирующих подхода, которые работают с кластеризацией.

Геометрический подход

Предположение берется с потолка. В основе графа интернет лежит метрическое пространство. Пространство вкусов, интересов, предпочтений. Насколько люди друг другу интересны. Насколько близки по духу, по взглядам. Если люди близки, они друг на друга ссылаются.

Здесь появляется огромное количество параметров. Мы берем и накидываем в это пространство 1010 точек. Огромное.

Противоречие. Кластеризация отличная, но убывание вершин — экспоненциальное.

Этот метод страшно простой и алгоритмы делаются «на авось».

Теоретико-игровой подход Чайес-Боргса

Знали ли вы, что во времена фон Неймана было объявлено, что теория игр будет оружием нового поколения против Советского Союза?

Мы исходим из того, что люди принимают решения общаться с друг другом или нет.

Событие — это список приглашенных гостей, а так же его «интенсивность».
Издержки = Интенсивность * (константа + K*(количество приглашенных)). Организуем встречи/события. Бывают дни рождения, а бывают походы. Я должен потратить ресурсы, чтобы мероприятие «продавить» и должен потратить ещё на каждого участника. Интенсивность знакомства. Появляется коэффициент «П», который маленький для дня рождения и большой для похода.

Другие делают так же. Человек может организовать несколько событий с интенсивностями П1, П2… Пn.

Есть мои действия по налаживанию социальных связей, а есть чужие.

Функция выигрыша = (количество людей с которыми ты стал достаточно хорошо знаком) — издержки

Причем не важно, кто организовывал событие. «Достаточно хорошо знаком» — значит сумма интенсивностей всех событий где вы были вместе, больше некоторого порогового значения.

Ребра проводятся для достаточно хороших знакомств.

image

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

image

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

image

image

Считать, что люди живут в метрическом пространстве, а когда организуют события, или участвует в событии, коэффициенты издержек, интенсивности и пороговое значение зависят от «близости». Есть идея совместить два подхода. Это пятое поколение моделей.

image

Дифференцированные издержки

Одних проще пригласить, чем других. Варианты — сделать дифференцированные издержки и дифференцированные выигрыши. Знакомство с одним выгоднее, чем знакомство с другим.

7 слайдов без комментрариев

image

И вам пригласить дешевле того, кто ближе. Допустим, мы расположим всех людей равномерно по окружности. Каждый пригласит некоторую окрестность, правда? Как будет выглядеть равновесие? Такого равновесия не существует. Не правда.

Предположим, что оно существует, тогда близкие друг к другу люди уже приглашены на много разных собраний. Доказательство. Существование этого равновесия входит в противоречие с существованием этого равновесия. Тогда ему нет нужды приглашать этого близкого.

image

Каждый приглашает окрестность, которая лежит по (или против) часовой стрелки на некотором расстоянии от него и некоторой длины. Чистое равновесие существует, оно найдено, оно единственное.

( — Это образование галактик!)
( — Это спонтанное нарушение симметрии!)

Выводы

Пелевин как то написал, что «смысл русского бытия в неспешном золочении безмерного иконостаса». Вот смысл математики — в том же самом. Только иконостас — научный.

image

Высшее, насколько можно себе представить. Это в высшей степени мультидисциплинарное исследование.

Источники

P.S.

Я сразу предупредил, что буду говорить неприятные вещи. «Однажды меня позвали в клуб к Навальному, там какая-то молодежь, энтузиасты, которые ему помогают. Молодежь Навального ни в зуб ногой, я им рассказывал про такие модели, но они не понимают, они даже интегрировать не умеют — только бегают и орут где-то. Революция побеждает в том случае, если математики, которые за революцию, сильнее, чем те, которые против. Они говорят: „Мы децентрализованы — конкретно Навальный ничего не означает, есть несколько важных лидеров“. А против них сидит сильный институт с серьезными людьми во главе, который по заказу Кремля говорит, кого конкретно и на сколько надо арестовать, чтобы ничего не было. Блокируешь кого нужно на несколько дней — и нет никакой революции. А потом приходит математик и считает, что централизация 90% у этой сети. Побеждает математика.»
— Алексей Савватеев, «Революция побеждает, если у нее хорошие математики»

P.P.S.

Кто знает, какие ещё интересные работы (статьи, лекции) работы есть в области соцсетей и их практической пользы, прошу поделиться.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть