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



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

Определение

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

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

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

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

    Примеры

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

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

  • деление единичного квадрата на k × k {displaystyle k imes k} блоки и
  • параметр W {displaystyle W} равный p l m {displaystyle p_{lm}} на ( l , m ) th {displaystyle (l,m)^{ ext{th}}} блокировать,

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

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

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

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

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

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