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

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

Определение

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

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

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

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

Примеры

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

Если вместо этого мы начнем с кусочно-постоянного графона:

деление единичного квадрата на $k\times k$ блоки и
параметр $W$ равный $p_{lm}$ на $(l,m)^{\text{th}}$ блокировать,

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

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

Понятия сходимости

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

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

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

Литература

Orbanz, P. (2015). “Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures”. IEEE Transactions on Pattern Analysis and Machine Intelligence. 37 (2): 437—461. arXiv:1312.7857. DOI:10.1109/tpami.2014.2334607. PMID 26353253.
Chung, Fan R. K.; Graham, Ronald L.; Wilson, R. M. (1989). “Quasi-random graphs”. Combinatorica. 9 (4): 345—362. DOI:10.1007/BF02125347.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Orbanz:Roy:2015-1] Orbanz, P. (2015). “Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures”. IEEE Transactions on Pattern Analysis and Machine Intelligence. 37 (2): 437—461. arXiv:1312.7857. DOI:10.1109/tpami.2014.2334607. PMID 26353253.

[qrandom-2] Chung, Fan R. K.; Graham, Ronald L.; Wilson, R. M. (1989). “Quasi-random graphs”. Combinatorica. 9 (4): 345—362. DOI:10.1007/BF02125347.