Як мережева математика може допомогти вам знаходити друзів

Вивчення структури існуючих дружніх зв’язків у вашому оточенні може допомогти вам найкращим чином формувати нові зв’язки при створенні нового кола друзів

Переходячи в нову школу, на нову роботу, переїжджаючи в новий місто – як ви заводите нових друзів? Можна підійти до питання активно, сформувати стратегічно корисні зв’язки з популярними хлопцями. Або можна залишити все на волю випадку, покладаючись на випадкові групи і зв’язку. У будь-якому підході розуміння структури існуючих дружніх зв’язків в новому оточенні може допомогти вам сформувати найкращі нові зв’язку, що в підсумку визначить ваш коло знайомств.

Уявіть собі переїзд в новий незвичайний місто, Регулярск, в якому є дивне правило: у кожної людини може бути не більше чотирьох друзів, але при цьому кожен хоче максимізувати кількість своїх зв’язків. Як буде виглядати структура зв’язків Регулярска? Щоб вивчити це питання, ми використовуємо математичний об’єкт під назвою мережу.

Простіше кажучи, мережа – це набір об’єктів під назвою «вузли», і зв’язків між ними. Мережі – поняття математично гнучке. Вони можуть позначати комп’ютери і зв’язують їх кабелі, авторів та їх помічників, стану кубика Рубіка і трансформації, що дозволяють переходити між ними – по суті, будь-який тип зв’язків, реальних або абстрактних. Щоб вивчити дружні зв’язки в Регулярске, ми створимо мережу, в якій вузлами будуть люди, а зв’язками – дружба між ними.

Позначаючи мережа, корисно буде представити вузли у вигляді точок, а зв’язки – у вигляді ліній, які ми також можемо називати ребрами. Така діаграма мережі може допомогти нам усвідомити її структуру. Так як же буде виглядати мережу дружніх зв’язків Регулярска? У якийсь момент часу вона може виглядати так:

Кожна людина буде намагатися знайти чотирьох друзів, і нові люди, які приїжджають в місто, будуть шукати тих, у кого поки менше чотирьох друзів. Ця мережа буде з часом рости, і постійно розширюватися з додаванням нових вузлів. (Можливо формування незалежних груп, але в даному прикладі ми ними знехтуємо).

Діаграми мереж можуть допомагати розбиратися в них, відображаючи чітку структуру. Але коли мережі розростаються, або не виявляють такої регулярної структури, як мережа Регулярска, діаграми можуть стати менш корисними. У цьому випадку корисно виробити різні способи аналізу структури мережі. Один з них – оцінити поширення ступенів вершин.

У мережі кількість зв’язків певного вузла називається його ступенем. Вузол з високим ступенем пов’язаний з багатьма іншими; вузол з низьким ступенем пов’язаний з меншою кількістю інших вузлів.


Зліва – вузол зі ступенем 8, праворуч – зі ступенем 3

Ступінь вузлів – важлива характеристика мережі, але локальна: вона описує структуру мережі тільки в рамках одного вузла. Але якщо охопити мірою всіх вузлів відразу, можна створити корисний інструмент для вивчення глобальної мережі.

В нашій мережі друзів ступінь кожного вузла – це кількість друзів однієї людини. У Регулярске у більшості людей є чотири одного, тому в більшості вузлів ступінь дорівнює 4. Ні в кого не буде більше друзів, проте у кого-то їх буде менше, тому будуть існувати вузли зі ступенями 3, 2 або 1. Підсумувати розподіл ступенів можна наступним чином:

Читайте також  Пасхалка-текстова RPG в коді пошуковика Google

Дана гістограма передає важливу інформацію про структуру нашої мережі. У цьому простому прикладі вона може і не донести до нас стільки, скільки повна діаграма мережі, але ми побачимо, як розподіл ступенів може дуже стати в нагоді дл вивчення різних мереж.

Переїдемо в інше місто. У Беспорядовке знайомства заводяться випадковим чином. Оскільки випадковість – штука хитра, давайте чітко обговоримо рамки: кожен житель міста позначається вузлом мережі, а кожне можливе ребро – це дружня зв’язок. Для створення випадкової зв’язку ми виберемо одне з цих можливих ребер випадковим чином, і намалюємо його, створивши таким чином зв’язок між двома вузлами, і, отже, дружбу між двома людьми.

Як буде виглядати мережа Беспорядовки? Якщо припустити, що ми почали з декількох вузлів і випадковим чином додали кілька ребер, картина може вийти такий:

В такій діаграмі складно побачити структуру. Однак нам багато повідомить розподіл ступенів в цій мережі. Його складно підрахувати безпосередньо, але можна представити за допомогою кількох важливих властивостей і на простому прикладі.

Припустимо, ви – один з десяти жителів Беспорядовки. Скільки в ній може існувати ймовірних дружніх зв’язків? Кожен з десяти жителів може бути пов’язаний з дев’ятьма іншими, тому, в принципі, можливо намалювати 10 × 9 = 90 ребер. Але такий підрахунок враховує кожну зв’язок двічі – по одному разу для кожного з двох друзів. Тому насправді загальна кількість зв’язків має бути 90 / 2 = 45.

Тепер, припустимо, ми випадковим чином вибираємо дружній зв’язок – тобто, одне з 45 можливих ребер. Яка ймовірність того, що ребро з’єднається з вами? Від вас можуть відходити дев’ять ребер, до одного з решти дев’яти вузлів. Оскільки дев’ять з 45 можливих ребер ведуть до вас, то ймовірність того, що випадково обране ребро з’єднається з вами, дорівнює 9 / 45 = 1 / 5, чи 20%.

Але той же самий аргумент застосуємо і до Беспорядовке, тому біля кожного вузла буде 20% імовірність з’єднатися з випадково вибраними ребром. Із збільшенням кількості ребер і вузлів ці ймовірності будуть трохи змінюватися, але в довгостроковій перспективі залишаться приблизно на одному рівні. Тобто, дружні зв’язки будуть приблизно порівну розподілені по Беспорядовке. Подекуди будуть спостерігатися невеликі відхилення, але ймовірність того, що у людини буде занадто багато або занадто мало дружніх зв’язків, буде мала. У Беспорядовке, швидше за все, у більшості жителів кількість друзів буде близько до середнього.

Ці особливості відносяться до “биномиальному розподілу” ступенів типовою випадкової мережі.

Маючи доступ тільки до розподілу ступенів в мережі, ми вже можемо виявити в ній певну рівномірність: велика частина вузлів за показником зв’язності відноситься до середніх, і дуже мала частина вузлів знаходиться в крайніх положеннях. Ця інформація корисна для розуміння структури мережі. З додаванням вузлів, тобто, з прибуттям в місто нових людей, розподіл буде трохи змінюватися, зберігаючи при цьому основні риси.

Читайте також  Як створити надійну ігрову механіку, користуючись тільки Excel: моделювання та оптимізація рішень

Але жоден з цих прикладів – не більше чотирьох друзів у Регулярске або випадково з’являється дружба в Беспорядовке – не є реалістичною моделлю дружніх зв’язків. У людей може бути більше чотирьох друзів, а наявність великої кількості знайомих – зовсім не така рідкість, як в биномиальном розподілі. Яка ж буде більш реалістична модель дружби?

При побудові зв’язків з друзями та друзями друзів структура ваших дружніх зв’язків, швидше за все, буде нагадувати інші мережі реального світу – харчові мережі, білок-білкові взаємодії або інтернет. Їх властивості характеризують так звані безмасштабные мережі – така модель зв’язності домінує в науці про мережах вже більше 20 років. Дослідники з математики, фізики, економіки, біології та соціальних наук спостерігали характерні ознаки наявності безмасштабных мереж в своїх областях досліджень.


Складна безмасштабная мережа соціальної мережі

Структура безмасштабной мережі залежить від простого принципу «бажаних зв’язків». Бажана зв’язок – це правило «багаті багатіють», що відноситься до зростання мереж. У сайту з великою кількістю існуючих зв’язків набагато більше ймовірність роздобути нові зв’язки, ніж у вузла з невеликою кількістю. Нові зв’язки демонструють тяжіння до сайтів з великою кількістю зв’язків.

Чи має це сенс в контексті формування дружніх зв’язків? В принципі, розумно припускати, що людина з великою кількістю друзів з більшою ймовірністю буде заводити нових. Оскільки він вже зв’язаний з великою кількістю людей, ймовірність зустріти нових людей завдяки існуючим зв’язкам, висока. Чим більше друзів, тим більше можливостей заводити нових друзів. А те, що у них і так вже є багато друзів, каже, що у них є якась можливість або схильність до дружби. Це з більшою ймовірністю буде залучати до них інших, точно так само, як популярні сайти привертають посилання з інших сайтів і блогів, а розвинені міста породжують створення нових залізниць і повітряних маршрутів.

І хоча на зростання безмасштабных мереж впливає кілька чинників, багато вважають кращі зв’язку найбільш важливим. А ще він справляє дивовижний вплив на розподіл ступенів в мережі.

Воно передбачає появу розподілу «з товстим хвостом». Велика частина вузлів в мережі буде мати невелику ступінь, але будуть існувати і вузли з дедалі більшими ступенями. Це сильно відрізняється від дружніх мереж Регулярска і Беспорядовки, в яких вузлів з великими ступенями дуже мало або зовсім немає.

Ці вузли з великими ступенями, працюють, як хаби мереж і є критично важливою характеристикою безмасштабных мереж. Вони являють собою соціальних метеликів в мережах друзів, банки в центрі економік, централізовані роутери, пропускають крізь себе регіональні інтернет-з’єднання, Кевинов Бейконов акторського світу. Хаби можуть забезпечити відчуття тісного світу у величезній мережі – наприклад, два будь-яких випадковим чином обраних людини з 2 мільярдів
користувачів Facebook в середньому знаходяться від одного не далі, ніж у чотирьох дружніх зв’язках. Кількість і різноманітність хабів надає безмасштабным мереж стійкість до певного типу розривів. Наприклад, навіть при відмові безлічі інтернет-з’єднань, повідомлення все одно зможуть доходити, зокрема тому, що все одно залишиться безліч способів дістатися до багатьох хабів до багатьох інших хабів.

Читайте також  Тестовий сервер для команди розробників

І хоча багато хто погоджуються з тим, що безмасштабные мережі і їх корисні властивості, у цій області досліджень є свої протиріччя. Точні математичні характеристики такого розподілу ступенів іноді складно інтерпретувати. У книзі «Пов’язані: нова наука мереж» [Linked: The New Science of Networks] піонер дослідження мереж і фізик Альберт-Лазло Барабаси пише, що в мережах, демонструють кращі зв’язку, розподіл ступенів буде слідувати степеневим законом. Степеневі розподілу часто зустрічаються у багатьох фізичних ситуаціях – наприклад, в законі зворотних квадратів для гравітації або електричних полів. Їх можна представити як функції, мають вигляд
Їх графіки зазвичай виглядають ось так:

У статечних розподілів дійсно є «товсті хвости». Але наскільки товсті? Скільки хабів певною мірою повинно знайтися в такій мережі? У дослідженні, опублікованому в цьому році, було вивчено понад 1000 реальних мереж, та з’ясовано, що лише у третини з них розподіл ступенів можна описати степеневим законом. У багатьох мереж розподіл ступенів більш точно можна було б описати, як експоненційна або логнормальний. У них, можливо, і є високорівневі властивості безмасштабных мереж, але чи можна їх вважати такими, якщо мірою в них розподіляються не так, як очікувалося? І чи має це взагалі значення?

Це має значення, якщо ми хочемо зв’язати наші теорії з нашими даними. Є бажана зв’язок основним чинником формування безмасштабных мереж? Є інші чинники, які грають важливу роль, і здатні повести розподіл ступенів в іншу сторону? Відповівши на ці питання і зрозумівши, які запитання слід задавати далі, ми реально будемо краще розуміти природу і структуру мереж, то, як вони розвиваються і еволюціонують.

Ці суперечності також нагадують нам про те, що математика, як і мережі, теж являє собою набір розвиваються зв’язків. Сучасні дослідження кидають виклик 20-річним гіпотез у відносно новій галузі дослідження мереж. Нові ідеї, приєднуючись до мережі, пов’язують всіх нас з математикою як минулого, так і майбутнього. Так що в математичних питаннях, як і в області дружби, корисно буде знайти хаби і максимізувати свою ступінь.

Вправи

 

  • Як буде виглядати мережа друзів, якщо у кожної людини буде рівно за два друга?
  • У Регулярске кожна людина може заводити до чотирьох друзів. Там можливе існування окремих груп, в яких у кожної людини є рівно за чотири друга. Скільки людей може входити в таку групу? (Підказка: відповідь пов’язаний з правильними многогранниками).
  • Наші мережі засновані на тому, що дружба – поняття симетричне. Якщо A дружить з Б, то Б дружить з А. Як можна підправити нашу модель мережі, щоб до неї могли входити несиметричні зв’язку, в яких А може дружити з Б, а Б не дружити з А?
  • У Дружищах кожен житель дружить з усіма іншими. Якщо в Дружищах живе n людей, скільки там сформовано дружніх зв’язків?

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

Вам також сподобається...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *