UK 
EnglishТипова
Polski🌐 Випадковий граф — гігантська компонента та фазовий перехід
Будуйте граф Ердеша-Реньї G(n,p): коли середній ступінь <k>=(n-1)p перетинає 1, раптово виникає гігантська компонента — різкий фазовий перехід у мережі.
Про цю симуляцію
Ця симуляція будує випадковий граф Ердеша–Реньї G(n,p): для кожної пари з n вершин ребро додається незалежно з імовірністю p. Далі пошук у ширину розбиває граф на зв'язні компоненти, забарвлюючи найбільшу з них у червоний колір, а силовий (force-directed) макет — пружинне притягання вздовж ребер та електростатичне відштовхування між усіма вершинами — розташовує граф так, щоб його структура стала візуально очевидною. Графік у реальному часі відстежує частку гігантської компоненти залежно від p і позначає теоретичний критичний поріг pc = 1/(n−1) пунктирною лінією, тож ви можете спостерігати фазовий перехід наживо, а не просто читати про нього.
🔬 Що показано
Коли ви піднімаєте p вище критичного порогу pc = 1/(n−1), численні малі деревоподібні компоненти раптово зливаються в одну гігантську зв'язну компоненту, що охоплює макроскопічну частку всіх n вершин. HUD у реальному часі показує середній ступінь <k> = (n−1)p, кількість окремих компонент, розмір гігантської компоненти та її частку від усього графа, а графік у нижньому лівому куті порівнює виміряну частку гігантської компоненти з теоретичною кривою S = 1 − exp(−<k>S).
🎮 Як користуватися
Перетягніть повзунок n (20–200), щоб задати кількість вершин, і повзунок p (0–1), щоб задати ймовірність ребра. Повільно змінюйте p через позначений поріг, щоб побачити, як ізольовані кластери зливаються в єдину гігантську компоненту, виділену червоним. Пауза заморожує силовий макет, щоб можна було роздивитися поточне розташування, а Скинути генерує новий випадковий граф із тими самими n і p.
💡 Чи знали ви?
Перехід до гігантської компоненти математично є тим самим явищем, що й перколяція зв'язків (bond percolation) на повному графі, і трапляється далеко за межами теорії графів: епідемія стає самопідтримуваною, щойно її репродуктивне число R₀ перетинає 1 — точнісінько та сама порогова умова, що й перетин <k> через 1 тут.
Часті запитання
Яку модель випадкового графа використовує ця симуляція?
Вона реалізує класичну модель Ердеша–Реньї G(n,p). За наявності n вершин кожне з n(n−1)/2 можливих ребер додається незалежно з імовірністю p — це генерується одним циклом, який кидає випадкове число для кожної пари. Тут немає ані преференційного приєднання, ані перез'єднання — кожне ребро є незалежним підкиданням монети, і саме це робить поріг гігантської компоненти математично «чистим».
Як симуляція знаходить зв'язні компоненти?
Після генерації ребер код запускає пошук у ширину (BFS) з кожної ще не відвіданої вершини: він досліджує всі вершини, досяжні через наявні ребра, шар за шаром за допомогою черги, позначаючи кожну ідентифікатором компоненти. Повторення цього для кожної залишкової невідвіданої вершини розбиває весь граф на компоненти за час O(n + m). Найбільша з отриманих компонент виділяється червоним як гігантська компонента.
Що визначає, чи утвориться гігантська компонента?
Визначальною величиною є середній ступінь <k> = (n−1)·p, який показується наживо в HUD. Нижче критичного значення <k> = 1 (тобто коли p менше за pc = 1/(n−1)) граф залишається роздробленим на малі компоненти розміру O(log n). Вище цього значення виникає єдина гігантська компонента, частка якої S від усіх вершин задовольняє самоузгоджене рівняння S = 1 − exp(−<k>S); симуляція розв'язує це рівняння чисельно та відображає результат поряд із виміряними даними.
Що насправді робить силовий (force-directed) макет?
Це суто косметичний елемент, не частина самої моделі випадкового графа: кожна пара вершин відштовхується, немов заряджені частинки (відштовхування за законом оберненого квадрата), кожне ребро діє як пружина, що тягне свої два кінці до довжини спокою, а слабка сила притягує всі вершини до центру полотна. Ітерування цих сил щокадру дозволяє зв'язним кластерам відділятися від незв'язаних, тож гігантська компонента, що виникає, стає візуально очевидною, а не просто повідомляється числово.
Чи реалістична модель Ердеша–Реньї для реальних мереж?
Зазвичай ні. Реальні мережі — соціальні графи, веб, енергомережі — зазвичай мають розподіли ступенів із важким хвостом (степеневий закон), високу кластеризацію та спільнотну структуру, жодну з яких G(n,p) не відтворює, оскільки тут кожне ребро має точно однакову незалежну ймовірність. Більш реалістичні альтернативи включають модель преференційного приєднання Барабаші–Альберт та модель малого світу Уоттса–Строгаца, але Ердеша–Реньї залишається необхідним математичним базисом, з яким порівнюють ці багатші моделі.