Как сетевая математика может помочь вам находить друзей
Переходя в новую школу, на новую работу, переезжая в новый город – как вы заводите новых друзей? Можно подойти к вопросу активно, сформировать стратегически полезные связи с популярными ребятами. Или можно оставить всё на волю случая, полагаясь на случайны группы и связи. В любом подходе понимание структуры существующих дружеских связей в новом окружении может помочь вам сформировать наилучшие новые связи, что в итоге определит ваш круг знакомств.
Представьте себе переезд в новый необычный город, Регулярск, в котором есть странное правило: у каждого человека может быть не более четырёх друзей, но при этом каждый хочет максимизировать количество своих связей. Как будет выглядеть структура связей Регулярска? Чтобы изучить этот вопрос, мы используем математический объект под названием сеть.
Проще говоря, сеть – это набор объектов под названием «узлы», и связей между ними. Сети – понятие математически гибкое. Они могут обозначать компьютеры и связывающие их кабели, авторов и их помощников, состояния кубика Рубика и трансформации, позволяющие переходить между ними – по сути, любой тип связей, реальных или абстрактных. Чтобы изучить дружеские связи в Регулярске, мы создадим сеть, в которой узлами будут люди, а связями – дружба между ними.
Обозначая сеть, полезно будет представить узлы в виде точек, а связи – в виде линий, которые мы также можем называть рёбрами. Такая диаграмма сети может помочь нам осознать её структуру. Так как же будет выглядеть сеть дружеских связей Регулярска? В какой-то момент времени она может выглядеть так:
Каждый человек будет пытаться найти четырёх друзей, и новые люди, приезжающие в город, будут искать тех, у кого пока меньше четырёх друзей. Эта сеть будет со временем расти, и постоянно расширяться с добавлением новых узлов. (Возможно формирование независимых групп, но в данном примере мы ими пренебрежём).
Диаграммы сетей могут помогать разбираться в них, отображая чёткую структуру. Но когда сети разрастаются, или не проявляют такой регулярной структуры, как сеть Регулярска, диаграммы могут стать менее полезными. В этом случае полезно выработать различные способы анализа структуры сети. Один из них – оценить распространение степеней вершин.
В сети количество связей определённого узла называется его степенью. Узел с высокой степенью связан со многими другими; узел с низкой степенью связан с меньшим количеством других узлов.
Слева – узел со степенью 8, справа – со степенью 3
Степень узлов – важная характеристика сети, но локальная: она описывает структуру сети только в рамках одного узла. Но если охватить степени всех узлов сразу, можно создать полезный инструмент для изучения глобальной структуры сети.
В нашей сети друзей степень каждого узла – это количество друзей одного человека. В Регулярске у большинства людей есть четыре друга, поэтому у большинства узлов степень равна 4. Ни у кого не будет больше друзей, однако у кого-то их будет меньше, поэтому будут существовать узлы со степенями 3, 2 или 1. Суммировать распределение степеней можно следующим образом:
Данная гистограмма передаёт важную информацию о структуре нашей сети. В этом простом примере она может и не донести до нас столько, сколько полная диаграмма сети, но мы увидим, как распределение степеней может очень пригодиться для изучения различных сетей.
Переедем в другой город. В Беспорядовке знакомства заводятся случайным образом. Поскольку случайность – штука хитрая, давайте чётко оговорим рамки: каждый житель города обозначается узлом сети, а каждое возможное ребро – это дружеская связь. Для создания случайной связи мы выберем одно из этих возможных рёбер случайным образом, и нарисуем его, создав таким образом связь между двумя узлами, и, следовательно, дружбу между двумя людьми.
Как будет выглядеть сеть Беспорядовки? Если предположить, что мы начали с нескольких узлов и случайным образом добавили несколько рёбер, картина может получиться такой:
В такой диаграмме сложно увидеть структуру. Однако нам многое сообщит распределение степеней в этой сети. Его сложно подсчитать напрямую, но можно представить при помощи нескольких важных свойств и на простом примере.
Допустим, вы – один из десяти жителей Беспорядовки. Сколько в ней может существовать вероятных дружеских связей? Каждый из десяти жителей может быть связан с девятью другими, поэтому, в принципе, возможно нарисовать 10 × 9 = 90 рёбер. Но такой подсчёт учитывает каждую связь дважды – по разу для каждого из двух друзей. Поэтому на самом деле общее количество связей должно быть 90 / 2 = 45.
Теперь, допустим, мы случайным образом выбираем дружескую связь – то есть, одно из 45 возможных рёбер. Какова вероятность того, что ребро соединится с вами? От вас могут отходить девять рёбер, к одному из оставшихся девяти узлов. Поскольку девять из 45 возможных рёбер ведут к вам, то вероятность того, что случайно выбранное ребро соединится с вами, равняется 9 / 45 = 1 / 5, или 20%.
Но тот же самый аргумент применим и к Беспорядовке, поэтому у каждого узла будет 20% вероятность соединиться со случайно выбранным ребром. С увеличением количества рёбер и узлов эти вероятности будут немного меняться, но в долгосрочной перспективе останутся примерно на одном уровне. То есть, дружеские связи будут примерно поровну распределены по Беспорядовке. Кое-где будут наблюдаться небольшие отклонения, но вероятность того, что у человека будет слишком много или слишком мало дружеских связей, будет мала. В Беспорядовке, скорее всего, у большинства жителей количество друзей будет близко к среднему.
Эти особенности относятся к «биномиальному распределению» степеней типичной случайной сети.
Имея доступ только к распределению степеней в сети, мы уже можем обнаружить в ней определённую равномерность: большая часть узлов по показателю связности относится к средним, и очень малая часть узлов находится в крайних положениях. Эта информация полезна для понимания структуры сети. С добавлением узлов, то есть, с прибытием в город новых людей, распределение будет немного изменяться, сохраняя при этом основные черты.
Но ни один из этих примеров – не более четырёх друзей в Регулярске или случайно появляющаяся дружба в Беспорядовке – не является реалистичной моделью дружеских связей. У людей может быть больше четырёх друзей, а наличие большого количества знакомых – вовсе не такая редкость, как в биномиальном распределении. Какова же будет более реалистичная модель дружбы?
При построении связей с друзьями и друзьями друзей структура ваших дружеских связей, скорее всего, будет напоминать другие сети реального мира – пищевые сети, белок-белковые взаимодействия или интернет. Их свойства характеризуют так называемые безмасштабные сети – такая модель связности доминирует в науке о сетях уже более 20 лет. Исследователи из математики, физики, экономики, биологии и социальных наук наблюдали характерные признаки наличия безмасштабных сетей в своих областях исследований.
Сложная безмасштабная сеть социальной сети
Структура безмасштабной сети зависит от простого принципа «предпочтительных связей». Предпочтительная связь – это правило «богатые богатеют», относящееся к росту сетей. У узла с большим количеством существующих связей гораздо больше вероятность заполучить новые связи, чем у узла с небольшим количеством. Новые связи демонстрируют тяготение к узлам с большим количеством связей.
Имеет ли это смысл в контексте формирования дружеских связей? В принципе, разумно предполагать, что человек с большим количеством друзей с большей вероятностью будет заводить новых. Поскольку он уже связан с большим количеством людей, вероятность встретить новых людей благодаря существующим связям, высока. Чем больше друзей, тем больше возможностей заводить новых друзей. А то, что у них и так уже есть много друзей, говорит, что у них имеется какая-то возможность или склонность к дружбе. Это с большей вероятностью будет привлекать к ним других, точно так же, как популярные сайты привлекают ссылки с других сайтов и блогов, а развитые города порождают создание новых железных дорог и воздушных маршрутов.
И хотя на рост безмасштабных сетей влияет несколько факторов, многие считают предпочтительные связи наиболее важным. А ещё он оказывает удивительное влияние на распределение степеней в сети.
Оно предсказывает появление распределения «с толстым хвостом». Большая часть узлов в в сети будет иметь небольшую степень, но будут существовать и узлы со всё большими степенями. Это сильно отличается от дружеских сетей Регулярска и Беспорядовки, в которых узлов с большими степенями очень мало или вовсе нет.
Эти узлы с большими степенями, работают, как хабы сетей и являются критически важной характеристикой безмасштабных сетей. Они представляют собой социальных бабочек в сетях друзей, банки в центре экономик, централизованные роутеры, пропускающие сквозь себя региональные интернет-соединения, Кевинов Бейконов актёрского мира. Хабы могут обеспечить ощущение тесного мира в огромной сети – к примеру, два любых случайным образом выбранных человека из 2 миллиардов пользователей Facebook в среднем находятся от друга не дальше, чем в четырёх дружеских связях. Количество и разнообразие хабов придаёт безмасштабным сетям устойчивость к определённого типа разрывам. К примеру, даже при отказе множества интернет-соединений, сообщения всё равно смогут доходить, в частности потому, что всё равно останется множество способов добраться до многих хабов до многих других хабов.
И хотя многие соглашаются с тем, что безмасштабные сети и их свойства полезны, в этой области исследований есть свои противоречия. Точные математические характеристики такого распределения степеней иногда сложно интерпретировать. В книге «Связанные: новая наука сетей» [Linked: The New Science of Networks] пионер исследования сетей и физик Альберт-Лазло Барабаси пишет, что в сетях, демонстрирующих предпочтительные связи, распределение степеней будет следовать степенному закону. Степенные распределения часто встречаются во многих физических ситуациях – например, в законе обратных квадратов для гравитации или электрических полей. Их можно представить, как функции, имеющие вид
Их графики обычно выглядят вот так:
У степенных распределений действительно есть «толстые хвосты». Но насколько толстые? Сколько хабов определённой степени должно найтись в такой сети? В исследовании, опубликованном в этом году, было изучено более 1000 реальных сетей, и выяснено, что только у трети из них распределение степеней можно описать степенным законом. У многих сетей распределение степеней более точно можно было бы описать, как экспоненциальное или логнормальное. У них, возможно, и есть высокоуровневые свойства безмасштабных сетей, но можно ли их считать таковыми, если степени в них распределяются не так, как ожидалось? И имеет ли это вообще значение?
Это имеет значение, если мы хотим связать наши теории с нашими данными. Является ли предпочтительная связь основным фактором формирования безмасштабных сетей? Есть ли другие факторы, играющие важную роль, и способные увести распределение степеней в другую сторону? Ответив на эти вопросы и поняв, какие вопросы следует задавать дальше, мы реально будем лучше понимать природу и структуру сетей, то, как они развиваются и эволюционируют.
Эти противоречия также напоминают нам о том, что математика, как и сети, тоже представляет собой набор развивающихся связей. Современные исследования бросают вызов 20-летним гипотезам в относительно новой области исследования сетей. Новые идеи, присоединяясь к сети, связывают всех нас с математикой как прошлого, так и будущего. Так что в математических вопросах, как и в области дружбы, полезно будет найти хабы и максимизировать свою степень.
Упражнения
- Как будет выглядеть сеть друзей, если у каждого человека будет ровно по два друга?
- В Регулярске каждый человек может заводить до четырёх друзей. Там возможно существование отдельных групп, в которых у каждого человека есть ровно по четыре друга. Сколько людей может входить в такую группу? (Подсказка: ответ связан с правильными многогранниками).
- Наши сети основаны на том, что дружба – понятие симметричное. Если A дружит с Б, то Б дружит с А. Как можно подправить нашу модель сети, чтобы в неё могли входить несимметричные связи, в которых А может дружить с Б, а Б не дружить с А?
- В Дружищах каждый житель дружит со всеми остальными. Если в Дружищах живёт n людей, сколько там сформировано дружеских связей?