14: Автоморфна еквівалентність
- Page ID
- 67533
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Автоморфна еквівалентність не настільки вимоглива до визначення подібності, як структурна еквівалентність, але більш вимоглива, ніж регулярна еквівалентність. Існує ієрархія трьох понять еквівалентності: будь-яка сукупність структурних еквівалентів також є автоморфними та регулярними еквівалентами. Будь-яка сукупність автоморфних еквівалентів також є регулярними еквівалентами. Не всі регулярні еквіваленти обов'язково автоморфні або структурні; і не всі автоморфні еквіваленти обов'язково структурні.
- 14.1: Визначення автоморфної еквівалентності
- Актори автоморфічно еквівалентні, якщо ми можемо перемикати графік таким чином, що обмін двома акторами не впливає на відстані між усіма акторами на графіку. Якщо ми хочемо оцінити, чи два актори автоморфічно еквівалентні, ми спочатку уявляємо обмін своїми позиціями в мережі. Потім ми дивимося і бачимо, чи, змінивши деяких інших акторів, ми можемо створити графік, в якому всі актори знаходяться на тій же відстані, що вони були один від одного в оригінальному графіку.
- 14.2: Використання концепції
- Структурна еквівалентність фокусує нашу увагу на парних порівняннях акторів. Намагаючись знайти акторів, яких можна поміняти місцями один на одного, ми дійсно звертаємо увагу на позиції акторів в тій чи іншій мережі. Ми намагаємося знайти акторів, які є клонами або замінниками.
- 14.3: Пошук наборів еквівалентності
- При двійкових даних числові алгоритми використовуються для пошуку класів акторів, що задовольняють математичним визначенням автоморфної еквівалентності. В основному, вузли графіка обмінюються, а відстані між усіма парами акторів на новому графіку порівнюються з вихідним графіком. Коли новий графік і старий граф мають однакові відстані між вузлами, графіки ізоморфні, а «обмін», який був зроблений, ідентифікує ізоморфні підграфи.
- 14.S: Автоморфна еквівалентність (резюме)
- Вид еквівалентності, виражений поняттям автоморфізму, знаходиться між структурною та регулярною еквівалентністю, у певному сенсі. Структурна еквівалентність означає, що окремі суб'єкти можуть бути замінені один на інший. Автоморфна еквівалентність означає, що підструктури графів можуть бути замінені один на одного. Як ми побачимо далі, регулярна еквівалентність йде далі і прагне мати справу з класами або типами акторів - де кожен член будь-якого класу має подібні відносини з іншими членами.