Оглавление
- 1 Графон
- 1.1 Определение графона
- 1.2 Статистическая формулировка
- 1.3 Примеры графонов
- 1.4 Совместно заменяемые матрицы смежности
- 1.5 Графическая оценка
- 1.6 Аналитическая формулировка
- 1.7 Примеры сходимости
- 1.8 Сходимость графов к графону
- 1.9 Восстановление параметров графов из графонов
- 1.10 Понятия конвергенции
- 1.11 Плотности гомоморфизма
- 1.12 Отрезанное расстояние
- 1.13 Определение расстояния разреза
- 1.14 Эквивалентность сходимости
- 1.15 Леммы о подсчете голосов и обратном подсчете
- 1.16 Пространство графонов
- 1.17 Приложения
- 1.18 Гипотеза Сидоренко
- 1.19 Обобщения
- 1.20 Общие настройки
- 1.21 Идентификаторы и блокировки
- 1.22 Корпусные и внешние настройки
- 1.23 Библиографическое описание и selflink
- 1.24 Дополнительные настройки
- 1.25 Полный текст статьи:
- 2 Графон
Графон
-
Определение графона
- Графон — симметричная измеримая функция W: [0,1]2 → [0,1], важная для изучения плотных графов.
- Графоны возникают как естественное понятие для ограничения последовательности плотных графов и как определяющие объекты взаимозаменяемых моделей случайных графов.
-
Статистическая формулировка
- Графон определяет взаимозаменяемую модель случайного графа, где каждая вершина получает случайное значение, а ребро включается с вероятностью W(u,u’).
- Модель случайного графа является взаимозаменяемой, если она может быть определена в терминах графона.
- Модель, основанная на фиксированном графоне W, обозначается G(n,W).
-
Примеры графонов
- Простейший пример графона — W(x,y) ≡ p для постоянной p ∈ [0,1].
- Модель Эрдеша–Реньи G(n,p) включает каждое ребро независимо с вероятностью p.
- Стохастическая блочная модель сообщества — обобщение модели Эрдеша–Реньи, где W(x,y) = p_lm на (ℓ,m)-м блоке.
-
Совместно заменяемые матрицы смежности
- Случайный граф может быть представлен как случайный n×n матрица смежности.
- Совместно заменяемые матрицы удовлетворяют условию, что распределение графа остается неизменным при перемаркировке вершин.
- Теорема представления утверждает, что случайная матрица (Xij) генерируется с помощью W(u,u’), где W — графон.
-
Графическая оценка
- Невозможно оценить ни функцию graphon, ни скрытые позиции узла.
- Основные направления оценки: оценка W до класса эквивалентности или оценка матрицы вероятностей, индуцированной W.
-
Аналитическая формулировка
- Любой граф может быть идентифицирован с помощью матрицы смежности A_BOS_G.
- Функция W_BOS_G определяется разбиением [0,1] на интервалы и равна (i,j)-му вхождению в A_BOS_G.
- Последовательности графов сходятся к графону, если их предельное поведение соответствует пределу функций W_G_n.
-
Примеры сходимости
- Последовательность случайных графов Эрдеша–Реньи сходится к постоянной W(x,y) ≡ p.
- Последовательность полуграфов сходится к полуграфону W(x,y) = 1 при |x-y| ≥ 1/2 и W(x,y) = 0 иначе.
- Последовательность полных двудольных графов сходится к полному двудольному графону W(x,y) = 1 при x ≠ y.
-
Сходимость графов к графону
- Последовательность графов сходится к графону W, если W(x,y) = 1 при min(x,y) ≤ 1/2 и max(x,y) > 1/2.
- Матрицы смежности становятся все более тонкими шахматной доской при увеличении n.
- Формальное определение сходимости должно быть независимым от перемаркировки вершин.
-
Восстановление параметров графов из графонов
- Плотность кромок и треугольника можно восстановить через интегралы по графону.
- Плотность кромок задается интегралом по единичному гиперкубу.
- Плотность треугольника задается интегралом по трем единичным гиперкубам.
-
Понятия конвергенции
- Существуют различные метрики для измерения расстояния между графиками.
- Выборочная метрика и показатель несоответствия ребер хорошо работают на плотных случайных графах.
- Последовательности графиков сходятся по обеим метрикам к графону.
-
Плотности гомоморфизма
- Плотность гомоморфизма t(F, G) определяется как число гомоморфизмов графов из F в G.
- Графоны предлагают простой способ вычисления плотностей гомоморфизма.
- Последовательность графиков левосторонне сходится, если для каждого фиксированного графа F, последовательность плотностей гомоморфизма сходится.
-
Отрезанное расстояние
- Обозначенное расстояние разреза между G и H определяется как максимальное расхождение плотностей кромок.
- Обозначенное расстояние разреза можно выразить через графоны.
- Норма среза для функции f определяется как максимальное расхождение интегралов по всем измеримым подмножествам единичного интервала.
-
Определение расстояния разреза
- Расстояние разреза определяется как минимальная норма разреза для всех возможных перемаркировок вершин.
- Расстояние между двумя графами определяется как расстояние между связанными с ними графонами.
-
Эквивалентность сходимости
- Сходимость по левому краю эквивалентна сходимости по расстоянию разреза.
- Предельный график всегда один и тот же.
-
Леммы о подсчете голосов и обратном подсчете
- Лемма о подсчете голосов показывает, что сходимость при расстоянии разреза подразумевает сходимость влево.
- Лемма об обратном подсчете показывает, что сходимость влево подразумевает сходимость при сокращенном расстоянии.
-
Пространство графонов
- Расстояние разреза можно преобразовать в метрику, образуя пространство графонов.
- Пространство графонов компактно и содержит множество всех конечных графов.
-
Приложения
- Лемма о регулярности может быть переведена на язык графонов.
- Лемма о слабой регулярности и лемма о строгой регулярности используются для доказательства более сильных результатов о регулярности.
-
Гипотеза Сидоренко
- Аналитическая природа графонов позволяет решать неравенства, связанные с гомоморфизмами.
- Гипотеза Сидоренко может быть истолкована как утверждение о минимальном количестве копий двудольного графа в случайном графе.
-
Обобщения
- Существуют расширения модели графонов для плотных ориентированных взвешенных графов и разреженных графов.
-
Общие настройки
- Проверка артикула MW-парсер-выход
- Настройка шрифта и переноса слов
- Настройка цвета фона для цитат
-
Идентификаторы и блокировки
- Идентификаторы для различных типов блокировок
- Ссылки на изображения для идентификации
- Настройка цвета и размера значков
-
Корпусные и внешние настройки
- Настройка внешнего вида для различных типов корпусов
- Настройка цвета и размера шрифта для различных медиа-экранов
-
Библиографическое описание и selflink
- Настройка шрифта для библиографического описания
- Настройка шрифта для selflink
-
Дополнительные настройки
- Настройка цвета для различных тем и цветовых схем