Графон (теория графов)

Графон — модель случайного графа, обобщение модели Эрдеша — Реньи. Графоны возникают естественным образом при изучении предельного поведения последовательности графов.

Графон — симметричная измеримая функция ${\displaystyle W:[0,1]^{2}\to [0,1]}$.

Обычно графон понимается как модель случайного графа по следующей схеме:

1. Каждая вершина ${\displaystyle j}$ графа — независимое случайное значение ${\displaystyle u_{j}\in [0,1]}$;
2. Ребро ${\displaystyle (i,j)}$ независимо включается в граф с вероятностью ${\displaystyle W(u_{i},u_{j})}$ .

Модель на основе графона ${\displaystyle W}$ иногда обозначается ${\displaystyle \mathbb {G} (n,W)}$, по аналогии с моделью случайных графов Эрдёша — Реньи. Граф, созданный из графона ${\displaystyle W}$ таким образом называется ${\displaystyle W}$-случайный граф.

Простейший пример графона: ${\displaystyle W(x,y)\equiv p}$ для некоторой постоянной ${\displaystyle p\in [0,1]}$. В этом случае ассоциированной заменяемой моделью случайного графа является модель Эрдёша — Реньи ${\displaystyle G(n,p)}$ который включает каждое ребро независимо с вероятностью ${\displaystyle p}$.

Если вместо этого мы начнём с кусочно-постоянного графона, получаемого следующим образом:

1. разделим единичный квадрат на ${\displaystyle k\times k}$ блоков и
2. установим параметр ${\displaystyle W}$ равным ${\displaystyle p_{lm}}$ на блоке с индексами ${\displaystyle (l,m)}$,

то полученная в результате модель случайного графа является ${\displaystyle k}$ стохастическим блочным обобщением модели Эрдёша — Реньи. Мы можем интерпретировать её как модель случайного графа, состоящую из ${\displaystyle k}$ различных графов Эрдёша — Реньи с параметрами ${\displaystyle p_{ll}}$ соответственно, с биграфами между ними, где каждое возможное ребро между блоками ${\displaystyle (l,l)}$ а также ${\displaystyle (m,m)}$ включается независимо с вероятностью ${\displaystyle p_{lm}}$ .

Многие другие модели случайных графов могут быть определены неким графоном.^[1]

Есть много разных способов измерить расстояние между двумя графами. Если нас интересуют метрики, которые сохраняют экстремальные свойства графов, то мы должны ограничить наше внимание метриками, которые идентифицируют случайные графы как близкие. Например, если мы случайным образом построим два графа независимо используя модель Эрдёша — Реньи ${\displaystyle G(n,p)}$ для фиксированного ${\displaystyle p}$, то расстояние между этими двумя графами при разумной метрике должно быть близко к нулю с большой вероятностью для больших ${\displaystyle n}$.

В этом смысле есть две естественные метрики, которые хорошо себя ведут на случайных графах. Первая — метрика выборки, которая говорит, что два графа близки, если их распределения подграфов близки. Вторая — метрика расхождения ребер, которая говорит, что два графа близки, когда их плотности ребер близки на всех соответствующих им подмножествах вершин.

Чудесным образом последовательность графов сходится относительно одного расстояния тогда, и только тогда когда сходится относительно другого. Более того, предельные объекты в обоих метриках оказываются графонами. Эквивалентность этих двух понятий сходимости отражает эквивалентность различных понятий квазислучайных графов.^[2]

• Л. Н. Корельяно, А. А. Разборов. Семантические пределы плотных комбинаторных объектов (рус.) // УМН. — 2020. — Т. 75, № 4(454). — С. 45–152. — doi:10.4213/rm9956.