Графіки, що підпорядковуються силі: побудова мережі за допомогою фізичного моделювання

Визначення графа як фізичної задачі

Граф — вузли та з’єднання між ними — не має вродженого 2D-розташування; той самий граф може бути намальований сотню різних способів, більшість із яких є нечитабельним сплутуванням. Розмітка за допомогою сили переводить проблему, уникаючи комбінаторики пошуку гарного малюнка, у фізичне моделювання: розглядайте кожен вузол як заряджену частинку, яка відштовхується від кожної іншої частининки, і кожне з’єднання як пружину, що тягне два пов’язані вузли разом. Запустіть симуляцію вперед і дозвольте їй стабілізуватися в низькоенергійному стані, і отримане розміщення схильно читабельне майже випадково — з’єднані вузли опиняються близько один до одного, нез’єднані вузли розкидані, а симетричні підструктури графа часто виробляють візуально симетричні розміщення, все без того, щоб алгоритм ніколи не отримував жодної інформації про естетику.

Fruchterman-Reingold: стандартна формулювання

Найбільш поширеною версією є те, що розроблено Fruchterman та Reingold (1991), яка визначає дві сили з одного характеристичного відстані k (приблизно ідеальна довжина ребра, часто встановлена ​​з площі макету поділеної на кількість вузлів):

відштовхуюча сила (кожна пара вузлів): Fr(d) = k^2 / d

притягуюча сила (тільки пари ребер): Fa(d) = d^2 / k

d = відстань між двома вузлами

Відштовхування змушує кожну пару вузлів віддалятися один від одного силою, яка зростає, коли вони наближаються (d у знаменнику), щоб запобігти вузлам ніколи не стикатися. Притягування притягує пов’язані вузли разом силою, яка зростає, чим далі вони розходяться один від одного (d у чисельнику), як пружина, яку тягнуть. При характеристичній відстані k ці дві сили приблизно збалансовані, тому що k діє як цільова довжина ребра: збільште її і весь макет розгортається, зменшіть її і вузли щільніше укладаються.

repulsive force (every node pair):   Fr(d) = k^2 / d
attractive force (edge pairs only):  Fa(d) = d^2 / k

d = distance between the two nodes

Симулювання графіків, що підпорядковуються силі (Force-Directed Graph Layout)

Ліворуч ітерується з повною силою назавжди, вузли можуть коливатися навколо своєї рівноваги замість того, щоб встановлюватися та відскакувати назад і вперед, оскільки дві сили перекористуються одна одною. Стандартне рішення - симульоване annealing: обмежте, наскільки далеко може рухатися вузол за один крок («температура» верхня межа), і поступово зменшуйте цю межу протягом запуску, щоб ранні ітерації робили великі, грубі перестановки, а пізніші - невеликі, точні коригування — саме та сама схема охолодження, що використовується в оптимізації симульованого annealing загалом. Обчислювально відштовхування між кожною парою вузлів коштує O(n^2) на ітерацію, що добре для графіків кількох сотень вузлів, але стає вузьким місцем для тисяч; виробничі двигуни просторових механізмів використовують стиль Barnes-Hut, щоб групувати віддалені кластери вузлів у єдисне приблизне джерело відштовхування, що зменшує вартість приблизно до O(n log n).

Симуляція графіків, що підпорядковуються силі (Force-Directed Graph Layout)

Візуальний характер макету на основі сили визначає не лише структуру графа, але й алгоритм. Випадковий граф Ердоша-Ренні (всі можливі ребра включені незалежно з фіксованим рівнем ймовірності p) зазвичай розкладається як відносно однорідний, бездиференційований об’єкт, оскільки він не має переважної структури для зосередження навколо. Граф Барабаші-Альберта, побудований на основі переважного приєднання, де нові вузли більш ймовірно з’єднуються з вже популярними вузлами, створює невелику кількість вузлів із високим ступенем — і ці вузли помітно тягнуть велику кількість вузлів із низьким ступенем в обертання навколо них під дією сил пружини, оскільки вузол з багатьма ребрами відчуває багато привабливих тяглових сил, що сходяться до нього. Граф «малого світу» Ватса-Строгацького — кільцевий ланцюг із випадковим перепідключенням кількох ребер — розкладається як локально кластеризоване кільце з рідкісними довгими міжвузловими ребрами, що помітно прорізають макет, прямий візуальний підпис властивості «малого світу» (коротша середня відстань шляху незважаючи на високу локальну кластеризацію), яку модель призначена для виробництва.

Вивчення встановленого макету

Після того, як симуляція охолоне, кілька структурних властивостей стають візуально очевидними для вільного перегляду. Щільно пов'язані спільноти тягнуться одна до одної в тісні, чітко відрізняються кластери (оскільки внутрішні ребра постійно тягнуть, а порівняно мало тягне їх до інших кластерів). Міжвузлові зв’язки та міжвузлові з’єднання, що з’єднують два кластери, стають помітно розтягнутими, оскільки вони борються з тягою двох окремих кластерів одночасно. Ступінь вузла корелює в міру слабкості з центральністю положення, оскільки високопов’язаний вузол одночасно притягується до багатьох інших і схильний до перетягування до центру маси макету. Жожчого з цього не програмується явно – це побічний ефект мінімізації тієї ж енергетичної функції, яка спочатку розмістила кожен вузол.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Force-Directed Graph і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.