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

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

    image

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

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

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

    Социальная сеть состоит из:

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

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

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

    image

    image

    image

    Галерея


    image

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

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



























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


    image

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

    image

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

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


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


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

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

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



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


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







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

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





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

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

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













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





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

    image

    image

    image



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

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


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

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

    Модели


    image

    image

    image

    image

    image

    image

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

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


    image

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

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

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

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


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

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

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


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

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


    image


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

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

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

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

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


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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

    image

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

    image

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

    image

    image

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

    image

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



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

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















    image

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

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

    image

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

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


    Выводы


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

    image

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

    Источники








    P.S.


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

    P.P.S.


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

    Комментарии 21

      +2
      В одной из предыдущих лекций мы узнали, что Савватеев живет в мире, в котором «в Москве, все милиционеры получили нарукавные номера и нашивки с фамилиями».
      Теперь мы узнали, что это, оказывается, в математике вся сила, когда можно любого просто так «на сколько надо арестовать, чтобы ничего не было». (Жаль не раскрыто, как бедняжка Сталин справлялся без математиков с компьютерами, считающими ядра графов по соцсетям.)
      Даже интересно, о чем нам поведают в следующей лекции?
        –1
        Просьба комментировать «по математическому» содержанию лекции.
          +7
          Если указанные цитаты не касаются математики, зачем вы их вставили в пересказы лекций?
          Просьба конспектировать лекции «по математическому» содержанию.
            –1
            Они иллюстрируют практическое применение матмоделей
              0
              Нет. Это не практические примеры, а фантазии. На что и было указано.
                0
                А я лично видел подтверждения (ФИО и порядковые номера полицейских, меня проверяли в метро 3 месяца назад).
                И кто там что-то «указывает» — не истина в последней инстанции, а повод для сомнения и перепроверки.

                Еще раз прошу, вопросы по содержанию ЭТОЙ лекции.
                  +1
                  Говорят, что апелляция к своему опыту сильным аргументом быть не может, но я отвечу подобным на подобное: 10-го числа я не видел никаких номеров и нашивок на космонавтах в масках, а насколько я понимаю, эти люди как раз полицейскими («милиционерами» в терминологии Савватеева) и являются.

                  При всем уважении к Савватееву-математику, многие его высказывания на другие темы не могут быть предметом серьезного дискурса (вспомнить хотя бы его приязнь к гомеопатии).
                    0
                    Не всех полицейских надо маркировать. Это всё равно что маркировать разведчиков. Одно дело повседневность, другое — полувоенное положение. А ещё тогда бы по-хорошему, и демонстрантов промаркировать :)))

                    А про «гомеопатию», если вы внимательно его слушали/читали, он не сторонник, а хочет именно разобраться в феномене, а не принимать чью-либо сторону. 100% с ним согласен.

                    Давайте обсуждать математику, блин.
                      0
                      сложно обсуждать экономические модели без привязке к реальному миру, с учетом того, что основой для их создания является факт того, что предыдущие модели не достаточно хорошо этот реальный пример описывают.
                      Ну и на самом деле именование полицейских (даже если оно есть). Пример не очень хороший, потому-что в отличии от таможни, у вас нет выбора, с каким полицейским «работать», следовательно теоретикоигровое содержание персонификации теряется, просто становится проще если что найти => увеличивается отрицательная полезность не удачного исхода.

                      P.S. У меня есть математически содержательный (надеюсь) вопрос, но не смог найти некоторые доступные контакты Алексея (кроме фб и инстаграмма, что довольно странно и там не сижу). Если у вас есть что-то в духе почты, то не могли бы вы поделиться, пожалуйста?
                      P.P.S. Вопрос заключается в том, что задача создания подобного графа по сути дела является задачей оптимизации нескольких параметров и должна неплохо считаться генетикой (оптимизация, понятна фитнесс-функция, понятно скрещивание, почти понятна мутация). Какие продвижения в этом направлении и почему это не используется?
                        0
                        Я передам.
                        И надеюсь, что скоро затащу его сюда комментировать.
          –2
          Савватеев молодец, делом занимается, решения ищет, дачи за распилы не строит. К нему претензий нет. Есть претензии к критикам, которые гнобят всех подряд. Вот конкретно вы, smrl, что для нашей страны сделали, что даёт вам право говорить, что Савватеев не достаточно хорош для вас? Чего вы пытаетесь добиться этой критикой, чтобы талантливые люди уезжали из нашей страны потому, что здесь люди агрессивные?
            –1
            Коллеги, мы обсуждаем не людей, а идеи.
            Прошу высказываться по математической составляющей вопроса.
              –1
              Савватеев отличный популяризатор для дошкольников. Но когда он начинает натягивать, как сову на глобус, очень простые схемы теории игр на очень сложные, многофакторные реальные проблемы, при этом привирая в фактической стороне, чтобы легче натягивалось, — что же в этом хорошего? Это называется научная нечистоплотность.
              Что еще хуже: конкретный пример с выбором пути реформирования полиции, ко всему прочему, не мелкий частный случай, а реальная большая проблема. (Я сейчас даже не о митингах последних дней, а о работе полиции в целом, по чисто «бытовым» вопросам.) Я бы, может, даже и поспорил — с математической точки зрения, — но с кем? Статью ведь выложил не Савватеев. А выложивший, увы, не различает кванторы всеобщности и существования, судя по его комментариям.

              Что же до гениев, которые сбегают из страны — а может, пусть иногда лучше сбегают? И мирно возятся в каком-нибудь центре Гельмгольца или Калтехе, чем за колючкой в Сарове лепят (предположительно) рутениевые РИТЭГи для разных «Буревестников», из-за которых каждые пару лет то на Урале выброс, то на Беломорье.
                0
                Я сейчас в Штатах живу, так тут дороги не чинены, зато треть бюджета на авиансоцы тратят. Так что не надо про Буревестники, в России всё очень правильно делают. Только в сказки верят.
                  –2
                  Коллеги, обсуждаем тему публикации, а не фигню.
                    –1
                    Настолько правильно, что из десятка упоминаемых в статье фамилий ученых — ни одной отечественной.
                      –1
                      В России 140 миллионов человек, в мире 7 миллиардов. Многого хотите от страны, развалившейся 30 лет назад. Но мы стараемся.
                    –1
                    У вас есть что сказать по поводу «Моделей интернета и соцсетей»?
                    Если нет, то, пожалуйста, не флудите.
                +1
                Вот еще видос 2013 года примерно в эту же тему
                  0
                  Оффтоп
                  Честно говоря, от графа с hackdiary.com я ожидал что в середине окажется Гитлер.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое