그래폰

그래프 이론과 통계에서 그래폰(그래프 한계라고도 함)은 촘촘한 그래프를 연구하는 데 중요한 대칭 측정 가능한 $함수{\displaystyle }$ W${\displaystyle }$:${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$→${\displaystyle }$[${\displaystyle 0}$, ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle W:[0,1]^{2}\}\to$ [$0,$1$]\}\}$이다$.$그래프는 밀도가 높은 그래프 시퀀스의 한계에 대한 자연스러운 개념과 교환 가능한 랜덤 그래프 모델의 근본적 정의 객체 둘 다에서 발생한다.그래폰은 다음과 같은 관측 쌍에 의해 밀도 그래프에 묶여 있다: 그래폰에 의해 정의되는 랜덤 그래프 모델은 거의 확실히 밀도 그래프를 만들어 내고, 규칙성 보조정리법에 의해 그래폰은 임의의 큰 밀도 그래프의 구조를 포착한다.

통계적 공식화

graphon은 대칭 $측정{\displaystyle }$가능한${\displaystyle }$함수 ${\displaystyle \mathrm{W}}$: [ ${\displaystyle 0{}^{}}$ ${\displaystyle {1\mathrm{}}^{}]}$ 2 → [ ${\displaystyle 0}$, 1$$ {\$displaystyle W:[0,1]^{2}\to$ [0$,1].$ 일반적으로 graphon은 다음과 같은 방식에 따라 교환 가능한 랜덤 그래프 모델을 정의하는 것으로 이해된다$.$

1. 그래프의$$ 각 꼭지점 $j{\displaystyle }$ ${\displaystyle j}$에는 개별 랜덤 값 ${\displaystyle u_{}}$ j ~${\displaystyle {}_{}U}$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle u_\sim U[0,1]}$이(가) 할당된다.
2. Edge$({\displaystyle i}$, ${\displaystyle j}$) ${\displaystyle(i,j)}$은(는) 확률 $W{\displaystyle (u_{}}$ i ,${\displaystyle {}_{}{}_{}}$ ${\displaystyle j_{}}$) ${\displaystyle W(u_{i},u_{j$과(와) 함께 그래프에 독립적으로 포함된다.

랜덤 그래프 모형은 이러한 방식으로 a(임의의 가능성이 있는) 그래폰 단위로 정의할 수 있는 경우에만 교환 가능한 랜덤 그래프 모델이다.고정 그래프온 $W{\displaystyle }$ ${\displaystyle W}$에 기반한 모델은 랜덤 그래프의 Erdds-Rény 모델과 $유사$하게${\displaystyle }$G (${\displaystyle n}$ ${\displaystyle ,W}$ )$${\$displaystyle \mathb {G}$ ($n,W)$로 표시되기도$$ 한다$.$이러한 방식으로$$ 그래프온 $W{\displaystyle }$ ${\displaystyle W}$에서 생성된 그래프를 $W{\displaystyle }$ ${\displaystyle W}$ -random$$ 그래프라고 한다.

만약 $W{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle 0}$ {\$displaystyle W\neq$ 0$}$이(가$)$ 있다면 교환 가능한 랜덤 그래프 모델은 거의 확실히 밀도가 높다는 것은 이 정의와 큰 숫자의 법칙에서 따온 것이다.^[1]

예

The simplest example of a graphon is ${\displaystyle W(x,y)\equiv p}$ for some constant ${\displaystyle p\in [0,1]}$. In this case the associated exchangeable random graph model is the Erdős–Rényi model ${\displaystyle G(n,p)}$ that includes each edge independently with probability ${\displaystyle p}$$(\backslash$$displaystyle p)$

대신 다음과 같이 조각이 일정한 그래프로 시작하는 경우:

1. 단위 정사각형을 $k{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle k}$ ${\displaystyle k\put$ k$}$ 블록으로 나누고$$,
2. $W{\displaystyle }$ ${\displaystyle W}$을$({\displaystyle }$를$)$ ${\displaystyle p_{}}$$$l ${\displaystyle m_{}}$ {\$displaystyle$$$p_{$lm}$과(를) 같게$$ 설정($l$ 블록$$,

결과적으로 교환 가능한 랜덤 그래프 모델은 Erdds-Rényi 모델의 일반화인 $k{\displaystyle }$ ${\displaystyle k}$ 커뮤니티$$ 확률 블록 모델이다.우리는 이것을$$ 각각 ${\displaystyle p_{}}$ $l{\displaystyle {}_{}}${\$displaystyle p_{l}$ 파라미터를 $가진{\displaystyle }$ k${\displaystyle$ p_{l}로 구성된$$ 랜덤 그래프 모델로 해석할 수 있으며$,{\displaystyle }$ 블록(${\displaystyle l}$ ${\displaystyle ,}$ l${\displaystyle }$) ${\$$displaystyle(l,l)$과${\displaystyle }$(${\displaystyle m}$, ${\displaystyle m}$ ) $displaystystyle (m,m)$ 사이의 가능한 각 가장자리가 포함되는$$ 곳에 큰 글자가 있다.확률 $p{\displaystyle {}_{}}$ l ${\displaystyle m_{}}$ ${\$과(와) 독립적으로$.$

다른 많은 인기 있는 무작위 그래프 모델은 일부 그래프톤에 의해 정의된 교환 가능한 랜덤 그래프 모델로 이해할 수 있으며, 자세한 조사는 오르반즈와 로이에 포함되어 있다.^[1]

공동 교환 가능한 인접 행렬

$n{\displaystyle }$ 크기 ${\displaystyle n}$의 랜덤 그래프는 ${\displaystyle \mathrm{랜덤}}$ $n{\displaystyle }$ ${\displaystyle \times }$ n ${\displaystyle$ n$\times n}$ 인접$$ 행렬로 나타낼 수 있다$$.크기가 다른 랜덤 그래프 사이에 일관성을 부여하기 위해(프로젝트성의 의미) ${\displaystyle \mathrm{일부}}$ 무한 변수의 왼쪽 상단 $n{\displaystyle }$ ${\displaystyle \times }$ n ${\displaystyle n\times n}$ 하위$$ 매트릭스로 발생하는 인접 매트릭스의 순서를 연구하는 것이 자연스럽다. 이를 통해 ${\displaystyle {Gn}_{}}$ ${\$를 생성할 수 있다. n -${\displaystyle {}_{}}$1 ${\$}에 노드를 추가하고$$ j< n ${\displaystyle j<n}$에 대한 에지$({\displaystyle j}$, n${\displaystyle }$) ${\displaystyle(j,n)}$을 샘플링함으로써 이러한 관점에서 랜덤 그래프는 랜덤 무한 대칭 어레이$({\displaystyle {\mathrm{Xi}}_{}}$ j${\displaystyle {}_{}}$) ${\displaystyle (X_{ij})$로 정의된다$.$

고전적 확률에서 교환 가능한 시퀀스의 근본적인 중요성에 따라, 무작위 그래프 설정에서 유사한 개념을 찾는 것은 당연하다.그러한 개념 중 하나는 공동으로 교환할 수 있는 행렬(즉, 충족되는 랜덤 행렬)에 의해 제시된다.

${\displaystyle (X_{ij}\\\\{d}{=}\,(X_{\sigma (i)\sigma (j)}}}}$

모든 순열 ${\displaystyle \sigma }$의 경우, ${\displaystyle \stackrel{}{\mathrm{여기}}}$서${\displaystyle \stackrel{}{}}$= d ${\$d}{d$}}}$은 분포가 같다는 것을 의미한다$$.직관적으로 이 조건은 무작위 그래프의 분포가 정점의 재표시에 의해 변경되지 않는다는 것을 의미한다. 즉, 정점의 라벨은 정보를 전달하지 않는다.

교환 가능한 시퀀스에 대한 데 피네티의 표현 정리와 유사하게, 공동으로 교환할 수 있는 무작위 인접 행렬에 대한 표현 정리가 있다.이것은 알두스-의 특수한 경우다.공동 교환 가능한 어레이에 대한 후버 정리 및 이 설정에서 랜덤 매트릭스$({\displaystyle {\mathrm{Xi}}_{}}$ j${\displaystyle {}_{}}$) ${\displaystyle(X_{ij})$는 다음에 의해 생성된다고 주장한다.

1. ${\displaystyle \mathrm{샘플}}$ $u{\displaystyle {}_{}}$ ${\displaystyle j_{}}$~ U${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle u_{j}\sim U[0,1]}$ 독립적으로$$ 샘플 u j [0,1]}
2. ${\displaystyle X_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$= X ${\displaystyle j_{}}$ ${\displaystyle i_{}}$= ${\displaystyle 1}$ ${\displaystyle X_{ij}=X_{ji}=1}$ 확률$$ $W{\displaystyle ({}_{}}$ ${\displaystyle i_{}}$ ,${\displaystyle {}_{}{}_{}}$ ${\displaystyle j_{}),}$ ${\displaystyle W(u_{i},u_{j}),},}$

여기서 $W{\displaystyle }$:${\displaystyle }$[ ${\displaystyle 0,}$ 1 ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$→${\displaystyle }$[ 0${\displaystyle ,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle W:[0,1]^{2}\to [0,1]}}$은(임의의미) 그래폰이다.즉, 랜덤 그래프 모형은 어떤 그래폰의 관점에서 정의된 공동 교환 가능한 랜덤 그래프 모델인 경우에만 공동 교환 가능한 인접 행렬을 가진다.

그래폰 추정

식별성 문제로 인해 그래폰 $함수{\displaystyle }$ W ${\displaystyle W}$ 또는$$ 노드 잠자리 ${\displaystyle u_{}}$ i${\displaystyle {}_{}}$, ${\displaystyle u_{i}}$을(를) 추정할 수 없으며$$, 그래폰 추정의 주요 방향은 두 가지다.한 방향은 $W{\displaystyle }$ ${\displaystyle W}$을(를) 동등성 등급까지 추정하거나 ^[2][3]$W{\displaystyle }$ ${\displaystyle W}$에 의해 유도된 확률 행렬을 추정하는 것을 목표로 한다$.$^[4][5]

분석제형

Any graph on ${\displaystyle n}$ vertices ${\displaystyle \{1,2,\dots ,n\}}$ can be identified with its adjacency matrix ${\displaystyle A_{G}}$. This matrix corresponds to a stepfunction ${\displaystyle W_{G}:[0,1]^{2}\to [0,1]}$, defined by partitioning ${\displaystyle }$${\displaystyle [}$ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,1]$ 간격 ${\displaystyle I_{}}$, ${\displaystyle {I\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle I_{}}$ n ${\$dots$,I_{n$}}}, I_{n}}, 이렇게 $하여$ I ${\displaystyle j_{}}$ ${\$에 내부가 있다$$.

and for each ${\displaystyle (x,y)\in I_{i}\times I_{j}}$, setting ${\displaystyle W_{G}(x,y)}$ equal to the ${\displaystyle (i,j)^{\text{th}}}$ entry of ${\displaystyle A_{G}}$. This function ${\displaystyle W_{G}}$ is the associated gr$그래프{\displaystyle }$ G ${\displaystyle G}$의 진폰$.$

일반적으로 ${\displaystyle {Gn}_{}}$ ${\$의 정점 수가 무한대로 가는$$ 그래프$$$){\displaystyle (G_{n}})$의 시퀀스가 있다면 함수$({\displaystyle {}_{}}$ $){\displaystyle (W_{G_{n$의 제한 동작을 고려하여 시퀀스의 제한 동작을 분석할 수 있다.진딧물은 수렴한다(일부 적절한 수렴 정의에 따라), 그러면 우리는 이러한 그래프의 한계가 이러한 관련 함수의 한계에 해당할 것으로 예상한다.

이것은 그래프 시퀀스 제한의 개념을 포착하는$$ 대칭 측정 $함수{\displaystyle }$ W${\displaystyle }$:${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle {1\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ 2${\displaystyle {}^{}}$→${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle W:[0,1]^{2}\}\to [0,1]}$의 정의에 동기를 부여한다.밀도가 높은 그래프 시퀀스의 경우 몇 가지 분명한 수렴 개념은 동일하며 그 모든 개념 아래에서 자연 한계 객체는 그래폰이다.^[6]

예

상수 그래프온

Take a sequence of ${\displaystyle (G_{n})}$ Erdős–Rényi random graphs ${\displaystyle G_{n}=G(n,p)}$ with some fixed parameter ${\displaystyle p}$. Intuitively, as ${\displaystyle n}$ tends to infinity, the limit of this sequence of graphs is determined solely by edge density of these graphs. 그래폰의 공간에서는 그러한 시퀀스가 $상수{\displaystyle }$ W (${\displaystyle x}$, ${\displaystyle y}$ )$$ ${\displaystyle p}$ $displaystyle W (x,y)\equiv p$로 거의 확실하게 수렴되어 위의 직관을 포착하는 것으로 나타난다.

하프 그래폰

Take the sequence ${\displaystyle (H_{n})}$ of half-graphs, defined by taking ${\displaystyle H_{n}}$ to be the bipartite graph on ${\displaystyle 2n}$ vertices ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$ and ${\displaystyle v_{1},v_{$${\displaystyle 2}$$},\dots,v_{n}},$${\displaystyle }$${\displaystyle u_{}}$ i$${\$displaystyle u_{i$}가 $v{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle v_{j}$에 정확히 인접하는$$ 경우$$$,$ 정점이 제시된 순서대로 나열되면 인접 행렬 $A{\displaystyle {}_{}}$ ${\displaystyle {H_{}}_{}}$ ${\displaystyle {n{}_{}}_{}}$ ${\$$H_{n}}}$은(는) "반사각형" 블록 행렬의 두 모서리가 하나씩 채워져 있으며$$, 나머지 항목은 0이 된다.예를$$ 들어 H ${\displaystyle {3\mathrm{}}_{}}$ ${\$의 인접 행렬은 다음과 같다.

$n{\displaystyle }$ ${\displaystyle n}$이(가) 커짐에$$ 따라 이 모서리는 "매끈매끈하게" 펴진다.Matching this intuition, the sequence ${\displaystyle (H_{n})}$ converges to the half-graphon ${\displaystyle W}$ defined by ${\displaystyle W(x,y)=1}$ when ${\displaystyle x-y \geq 1/2}$ and ${\displaystyle W(x,y)=0}$ otherwise.

완전한 초당적 그래프온

크기가 동일한 전체 초당적 그래프의${\displaystyle {시퀀스}_{}{\mathrm{Kn}}_{}}$ ,$$n ) {\$displaystyle(K_{n,$n$$})를 취하십시오.모든 정점을 시작 부분에 한 부분에 배치하고 끝 부분에 다른 부분의 정점을 배치하여 정점을 주문하면${\displaystyle }$(${\displaystyle {Kn}_{}}$,${\displaystyle {}_{}{n}_{}}$ $){\displaystyle (K_{n,n})$의 인접 행렬은 1블록 2블록과 0블록 2블록으로 되어 있는 블록 오프 대각 행렬처럼 보인다$$.예를$$ 들어 $K{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle 2_{}}$ ${\$의 인접 행렬은 다음과 같다.

As ${\displaystyle n}$ gets larger, this block structure of the adjacency matrix remains constant, so that this sequence of graphs converges to a "complete bipartite" graphon ${\displaystyle W}$ defined by ${\displaystyle W(x,y)=1}$ whenever ${\displaystyle \min(x,y)\leq 1/2}$ and( , )> / ${\displaystyle \max(x,y)>1/2$}및 $설정{\displaystyle }$ W${\displaystyle (x,}$ y${\displaystyle }$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle W(x,y)=0}$ 다른 경우$$

${\displaystyle {\mathrm{대신}}_{}}$ K ${\displaystyle n_{}}$, n ${\$의 정점을 부품끼리$$ 교대로 주문하면 인접 행렬은 0과 1의 체스판 구조를 갖는다.예를 들어, 이 순서에서는 $K{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}}$2 ${\$2,$2}}$의 인접 행렬이 다음과 같이 주어진다$$.

$n{\displaystyle }$ ${\displaystyle n}$이(가) 커질수록$$ 인접 행렬은 더욱 정교하고 정교한 체스판이 된다.이러한 동작에도 불구하고$,{\displaystyle }$ 우리는 여전히 (${\displaystyle {\mathrm{Kn}}_{}}$, n$){\displaystyle (K_{n,n})$의 한도가 고유하여$$ 예제 3의 그래프를 생성하기를 원한다.이것은 우리가 공식적으로 일련의 그래프에 대한 정합성을 정의할 때, 한계의 정의는 정점의 라벨링에 무관해야 한다는 것을 의미한다.

W-랜덤 그래프 한계

Take a random sequence ${\displaystyle (G_{n})}$ of ${\displaystyle W}$-random graphs by drawing ${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$ for some fixed graphon ${\displaystyle W}$. Then just like in the first example from this section, it turns out that ${\displ$$aystyle (G_{n})$은 $거의$ 확실히 W ${\displaystyle$ W$}$에 $수렴$된다.

그래프에서 그래프 매개 변수 복구

그래프 $G{\displaystyle }$ ${\displaystyle$ $G$$}$과(와) 연관된 그래프 $W{\displaystyle }$${\displaystyle }$= ${\displaystyle W_{}}$ ${\displaystyle {}_{}}$ ${\$ $W_$${G$$}$의 변환을 $통합$하여$$G {\$displaystyle$ G}의 $그래프{\displaystyle }$ 이론적 속성과 파라미터를 복구할 수 있다$.$ 예를 들어, 에지 밀도(평균도를 정점 수로 나눈 값) $G{\displaystyle }$$.$${\displaystyle G}$은(는) 적분자에 의해 제공됨$$

This is because ${\displaystyle W}$ is ${\displaystyle \{0,1\}}$-valued, and each edge ${\displaystyle (i,j)}$ in ${\displaystyle G}$ corresponds to a region ${\displaystyle I_{i}\times I_{j}}$ of area ${\displaystyle 1/n^{2}}$ where ${\displaystyle$$W}$은(는) $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$이다$.$

유사한 추론을 통해 $G{\displaystyle }$ ${\displaystyle G}$의 삼각형 수가

가능성의

두 그래프 사이의 거리를 측정하는 방법에는 여러 가지가 있다.우리가 그래프의 극단적 속성을 "보존"하는 지표에 관심이 있다면, 무작위 그래프를 유사한 것으로 식별하는 지표로 주의를 제한해야 한다.예를 들어, 일부 고정 $p{\displaystyle }$ ${\displaystyle p}$에 대해 Erdds-Rény $모델{\displaystyle }$ G (${\displaystyle n}$ ${\displaystyle ,}$p${\displaystyle }$) ${\displaystyle G(n,p)}$에서 독립적으로 두 개의 그래프를 그리는 경우$,$ "합리적" 메트릭에 따른 이 두 그래프 사이의 거리는 $큰{\displaystyle }$ n ${\displaystystyle n}$에 대해 높은 확률로 0에 가까워야 한다$.$

순진하게, 동일한 정점에 있는 두 개의 그래프를 볼 때, 한 그래프에서 다른 그래프로 이동하기 위해 추가하거나 제거해야 하는 가장자리 수, 즉 편집 거리로 정의할 수 있다.그러나 편집 거리는 무작위 그래프를 유사한 것으로 식별하지 않는다. 실제로 $G{\displaystyle }$ ${\displaystyle (n,}$ ${\displaystyle \frac{1}{}}$ ${\displaystyle 2\frac{\mathrm{}}{}}$) ${\displaystyle G(n,{\tfrac{1}{2}}:}$에서 독립적으로 그려진 두 개의 그래프는$$ 예상(정상화된) 편집 거리를 1 ${\displaystyle \frac{2}{}}$ ${\$2$\}\}.$

우리가 원하는 의미에서 밀도 높은 무작위 그래프에서 잘 작동하는 두 가지 자연 지표가 있다.첫 번째는 샘플링 메트릭인데, 두 개의 그래프가 서브그래프의 분포가 가까우면 가깝다는 것이다.두 번째는 에지 불일치 메트릭인데, 두 그래프의 에지 밀도가 모든 해당 정점 하위 집합에서 가까울 때 두 그래프가 가깝다는 것이다.

기적적으로, 일련의 그래프들이 정확히 한 메트릭스에 대해 수렴될 때 다른 메트릭스에 대해 수렴된다.또한 두 메트릭스 아래의 제한 개체는 그래폰으로 판명된다.이 두 가지 정합화 개념의 등가성은 퀘이란돔 그래프의 다양한 개념들이 얼마나 등가인지를 반영한다.^[7]

두 그래프 $G{\displaystyle }$ ${\displaystyle G}$과(와) $H{\displaystyle }$ ${\displaystyle H}$ 사이의 거리를 측정하는 한 가지 방법은 상대적인 하위 그래프 수를 비교하는 것이다$$.That is, for each graph ${\displaystyle F}$ we can compare the number of copies of ${\displaystyle F}$ in ${\displaystyle G}$ and ${\displaystyle F}$ in ${\displaystyle H}$. If these numbers are close for every graph ${\displaystyle F}$, then intuitively ${\displaystyle G}$ and ${\disp$$레이스타일 H}$은(는) 비슷하게 생긴 그래프다$$.그러나 서브그래프를 직접 다루기보다는 그래프 동형성(homorphism)으로 작업하는 것이 더 쉬운 것으로 나타났다.이 시나리오에서는 서브그래프의 수와 고정 그래프의 그래프 동형성의 수가 점증적으로 동일하기 때문에 크고 밀도가 높은 그래프를 다룰 때 이것은 괜찮다.

Given two graphs ${\displaystyle F}$ and ${\displaystyle G}$, the homomorphism density ${\displaystyle t(F,G)}$ of ${\displaystyle F}$ in ${\displaystyle G}$ is defined to be the number of graph homomorphisms from ${\displaystyle F}$ to ${\displaystyle G}$. In other words, ${\displaystyle t(}$${\displaystyle F}$, ${\displaystyle G}$) ${\displaystyle t(F,G)}$은 $F{\displaystyle }$ ${\$displaystyle G}의$$정점에서 G ${\$$displaystyle$ $G$$}$의 $정점$까지 임의로 선택한$$ 지도가 F {\$displaystyle$ G}의 $인접{\displaystyle }$ 정점에 $인접$ 정점을 보낼 확률이다$.$

그래폰은 동형성 밀도를 계산하는 간단한 방법을 제공한다.실제로 그래프 G ${\displaystyle G}$과(와) 연결된 그래프 $W{\displaystyle }$ $G{\displaystyle {}_{}}$ ${\$ 및 다른$$ $F{\displaystyle }$ ${\displaystyle F}$을$($를) 볼 때

여기서 적분은 다차원이고, 단위 하이퍼큐브$[{\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ V $){\$ 이는 관련 그래프의 정의에서 따르며, 위의 적분도가 $1{\displaystyle \mathrm{}}$ ${\displaystyle$ 1$}$과 같음을 고려한다$.$ 그런 다음 동형성 밀도의 정의를 임의 그래폰으로 확대할 수 있다.${\displaystyle W}$ ${\displaystyle$ W$\},$ 동일한 적분을 사용하고 정의

모든 $그래프{\displaystyle }$ F ${\displaystyle F}$에 대해$.$

이 설정을 고려할 때, 모든 고정 $그래프{\displaystyle }$ F$$${\$$displaystyle F}$에$$대해 동형성 밀도의 순서${\displaystyle (t}$ ${\displaystyle ({}_{}}$ , ${\displaystyle {Gn}_{}}$)$${\$displaystyle \left(t,G_{n}\n$$}$오른쪽$)$가 수렴되는$$ 경우 그래프$({\displaystyle {Gn}_{}}$)의 시퀀스는 좌뇌 컨버전트라고$$ 말한다.정의만으로는 분명하지 않지만$,{\displaystyle }$ (${\displaystyle {Gn}_{}}$) ${\displaystyle (G_{n})$이 이러한 의미에서 수렴된다면$$, 모든 그래프 $F{\displaystyle }$ ${\displaystyle F}$에 대해 그래폰 $W{\displaystyle }$ ${\displaystyle W}$이(가) 항상 존재하게 된다$.$

동시에

절단 거리

$동일$한 꼭지점에서$$ $G{\displaystyle }$ ${\displaystyle G}$ 및$$ H ${\displaystyle H}$ 두 개의 그래프를 취하십시오.Because these graphs share the same vertices, one way to measure their distance is to restrict to subsets ${\displaystyle X,Y}$ of the vertex set, and for each such pair subsets compare the number of edges ${\displaystyle e_{G}(X,Y)}$ from ${\displaystyle X}$ to ${\displaystyle Y}$ in ${\d$$isplaystyle G}$ to the number of edges ${\displaystyle e_{H}(X,Y)}$ between ${\displaystyle X}$ and ${\displaystyle Y}$ in ${\displaystyle H}$. If these numbers are similar for every pair of subsets (relative to the total number of vertices), then that suggests ${\displaystyle G}$ and ${\displaystyle H}$${\displaystyle H}$도 비슷한$$ 그래프다.

이러한 거리 개념을 예비 공식화한 것으로서, ${\displaystyle 크기}$가 V =${\displaystyle n}$ ${\displaystyle V =n}$인 $동일$한 꼭지점에 있는$$ $그래프{\displaystyle }$ $G{\displaystyle }$ ${\displaystyle G$$}$ 및$$ H ${\displaystyle$ H$}$ 쌍에 $대해{\displaystyle }$ G ${\displaystyle G}$과 $H{\displaystyle }$ ${\displaystystyle H}$ 사이의 레이블로 표시된 절단 거리를 정의한다$.$e

In other words, the labeled cut distance encodes the maximum discrepancy of the edge densities between ${\displaystyle G}$ and ${\displaystyle H}$. We can generalize this concept to graphons by expressing the edge density ${\displaystyle {\tfrac {1}{n^{2}}}e_{G}(X,Y)}$ in terms of the associated graphon $W{\displaystyle {}_{}}$ ${\displaystyle G_{}}$ ${\$ 동일성을 부여함

$여기$서 I ${\displaystyle X_{}}$, I ${\displaystyle Y_{}}$ ${\displaystyle {}_{}}$[ 0${\displaystyle }$, ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle I_{X},I_{Y}\subseteq [0,1]}$은(는) $X{\displaystyle }$ ${\displaystyle$ X$}$ $및{\displaystyle }$ Y$$ ${\displaysty Y}$의 정점에 해당하는 구간의 결합이다$.$ 비교 중인 그래프가 정점을 공유하지 않더라도 이 정의는 여전히 사용될 수 있다.이것은 다음과 같은 보다 일반적인 정의에 동기를 부여한다.

정의 1.모든 대칭 함수 $f{\displaystyle }$:${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle 2\mathbb{}{}^{}}$→ ${\displaystyle {R\mathrm{}}^{}}$ ${\$에 $대해{\displaystyle }$ f$${\$displaystyle f$}의 절단 규범을 수량으로 정의하십시오$$.

$${\displaystyle \lVert \lBert _{\square }=\sup_{S,T\subseteq [0,1]}\왼쪽 \int _{S}f(x,y)\;\mathrm {d}x\,\mathrmatrm {d} y\right}$$

단위 간격의$$ 모든 측정 가능한 하위 집합 $S{\displaystyle }$ ,${\displaystyle T}$ ${\displaystyle$ S$,T}$을(를) 인수한다.^[6]

labeled${\displaystyle {}_{}}$ ${\displaystyle G_{}}$- ${\displaystyle {}_{}}$ ${\displaystyle H_{}}$ ${\displaystyle {\Vert }_{}{}_{}}$ =${\displaystyle {}_{}}$d${\displaystyle {}_{}g}$ ( ${\displaystyle G}$ ,${\displaystyle }$H${\displaystyle }$)$${\$displaystyle \lVert W_{G$}-$W_{H$}\$rVert$_{\$square }d_{\square }{}}}}}(G$H$)$가 같기 때문에 라벨이 붙은 절단 거리에 대한 초기 개념을 포착했다.

이 거리 측정은 두 개의 이형성 그래프에 0이 아닌 거리를 지정할 수 있다는 한 가지 큰 한계가 있다.이소형 그래프의 거리가 0인지 확인하기 위해, 우리는 정점의 가능한 모든 "릴레이벨링"에 대해 최소 절단 규범을 계산해야 한다.이것은 절단 거리에 대한 다음의 정의를 동기부여한다.

정의 2.그래폰 $U{\displaystyle }$ ${\displaystyle U}$ $및$ W ${\displaystyle W}$ 쌍에 대해 절단 거리를 다음과 같이 정의하십시오$.$

$${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}}}}}}}}}}}}}}"$$

where ${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$ is the composition of ${\displaystyle W}$ with the map ${\displaystyle \varphi }$, and the infimum is taken over all measure-preserving bijections from the unit interval to itself.^[8]

두 그래프 사이의 절토 거리는 연관된 그래프온 사이의 절토 거리로 정의된다.

이제 우리는 일련의 그래프$){\displaystyle (G_{n}})$가 절삭거리 ${{\$ Δ 아래의 Cauchy 시퀀스라면 절삭거리 아래에서 수렴된다고 말한다$$$.$ 정의의 직접적인 결과는 아니지만, 그러한 그래프 시퀀스가 Cauchy라면 항상 어떤 gra로 수렴된다.$음성{\displaystyle }$ W ${\displaystyle W$

정합성 등가

밝혀진 바와 같이, 그래프$({\displaystyle {Gn}_{}}$) ${\displaystyle (G_{n}})$의 모든 시퀀스에 대해$,$ 왼쪽 수렴은 절단 거리 아래의 수렴과 동일하며, 나아가, 한계 그래프 $W{\displaystyle }$ ${\displaystyle W}$도 동일하다$$.우리는 또한 동일한 정의를 사용하는 그래폰 자체의 수렴을 고려할 수 있으며, 동일한 동등성이 참이다.사실, 수렴의 두 개념은 소위 "카운팅 레마"라고 불리는 것을 통해 더욱 강하게 연관되어 있다.^[6]

보조마 세는 중.$모든{\displaystyle }$ 그래폰$$U {\$displaystyle$ $U$}$$및 W {\$displaystyle W}$에 대해$,$

$$\displaystyle t(F,U)-t(F,W) \leq e(F)\delta _{\square }(U,W)}$$

모든 $그래프$에 대해 F ${\displaystyle$ F$\}.$

"카운팅 보조정리"라는 이름은 이 보조정리기가 그래프의 서브그래프 카운트와 유사한 동형성 $밀도{\displaystyle }$ t${\displaystyle }$(${\displaystyle F}$, ${\displaystyle W}$ )${\디스플레이$ 스타일 t$(F,W$에 대해 주는 경계에서 유래했다.이 보조정리기는 정규성 칸막이 분야에 나타나는 그래프 계수 보조정리기를 일반화한 것으로, 절삭거리 아래의 수렴이 좌융합을 함축하고 있음을 바로 알 수 있다.

역 카운팅 보조정리. 실수 > 0 ${\displaystyle \epsilon >0$에 대해, 실수 >0 {\$displaystyle \eta$>$0$$}$과(와$$)의 임의 $쌍$의 그래폰$$U {\$displaystyle U}$ 및 W ${\displaystystyle W}$이 있다.

$$\displaystyle t(F,U)-t(F,W) \leq \eta }$$

${\displaystyle v}$(${\displaystyle F}$) ${\displaystyle \le }$ k ${\displaystyle v(F)\leq k}$을$($를) 만족하는 모든 $그래프{\displaystyle }$ F ${\displaystyle$ v()\leq k$}$에 대해 (, W)< ${\delta _{\square$ _$}(U,W)\psilon }$이 있어야 한다

이 보조정리기는 좌-융합이 절삭거리 아래의 수렴을 함축한다는 것을 보여준다.

그래폰의 공간

We can make the cut-distance into a metric by taking the set of all graphons and identifying two graphons ${\displaystyle U\sim W}$ whenever ${\displaystyle \delta _{\square }(U,W)=0}$. The resulting space of graphons is denoted ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$, and t$\Delta {\displaystyle {}_{}}$Δ${\$}}이(가) 있는 ogether는 미터법 공간을 형성한다$$.

이 공간은 컴팩트하게 되었다.또한 연관된 그래프로 표현되는 모든 유한 그래프의 집합을 밀도 있는 부분 집합으로 포함하고 있다.이러한 관측을 통해 그래프의 공간이 절단 거리에 대한 그래프 공간의 완성임을 알 수 있다.이것의 즉각적인 결과는 다음과 같다.

코롤러리 1.모든 실수 ϵ<>를 사용하여 들어 0{\displaystyle \epsilon>0},이 있는 정수 N{N\displaystyle}가 매일 graphon W{W\displaystyle}은 그래프 G{G\displaystyle}로 대부분의 N{N\displaystyle}vertices가δ◻(WWG)<>ϵ{\displaystyle \delta_{\square. }(W,W_{G$}<\epsilon$

이유를 보려면 $G{\displaystyle \mathcal{}}$ ${\$을(를) 그래프 집합으로 설정하십시오$$.각 그래프가 G∈ G{\displaystyle G\in{{G\mathcal}}}◻(G, ϵ){\displaystyle B_{\square}(G,\epsilon)}모든 graphons W포함하는 열린 공 B를 생각해 보자{W\displaystyle}가δ◻(WWG)<>ϵ{\displaystyle \delta_{\square}(W,W_{G})<, \epsilon}. 그 세트에 대한 열린 공들을 모든 graphscovers ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$, so compactness implies that there is a finite subcover ${\displaystyle \{B_{\square }(G,\epsilon )\mid G\in {\mathcal {G}}_{0}\}}$ for some finite subset ${\displaystyle {\mathcal {G}}_{0}\subset$${\mathcal{G$ 이제 G ${\displaystyle 0_{\mathrm{}}}$ ${\$의 그래프 중에서 가장 많은 수의 정점이 $되도록$ N$${\$displaystyle$N}을(를) 취할 수 있다$.$

적용들

규칙성 보조정리

그래폰 공간$({\displaystyle {\stackrel{}{\mathcal{}}}_{}}$~ ${\displaystyle 0_{\mathrm{}}}$ ,${\displaystyle {}_{}{}_{}}$ $){\displaystyle({\widetile {\mathcal {\w}}_{0},\delta _${\$square }}}})$의 압축성은 스제메레디의 규칙성 보조정리 분석적 공식으로 생각할 수 있는데$$, 사실 원래의 보조정리보다 강한 결과였다.^[9]세메레디의 규칙성 보조마사는 다음과 같이 그래폰 언어로 번역할 수 있다.Define a stepfunction to be a graphon ${\displaystyle W}$ that is piecewise constant, i.e. for some partition ${\displaystyle {\mathcal {P}}}$ of ${\displaystyle [0,1]}$, ${\displaystyle W}$ is constant on ${\displaystyle S\times T}$ for all ${\displaystyle S,T\in {\mathcal$${P$ 그래프 $G{\displaystyle }$ ${\displaystyle G}$에 규칙성 파티션이 있다는$$ 문장은 연관된 그래프온 $W{\displaystyle {}_{}}$ ${\displaystyle G_{}}$ ${\$가 단계$$ 기능에 가깝다는 것과 같다.

컴팩트함을 증명하기 위해서는 약한 규칙성 보조정리만 필요하다.

그래폰의 약한 정규성 보조정리.모든 graphon W{W\displaystyle}과ϵ<>를 사용하여 들어 0{\displaystyle \epsilon>0}astepfunction W′가장에 ⌈ 41/ϵ 2⌉{\displaystyle \lceil 4^{1/\epsilon ^{2}}\rceil}과{\displaystyle W의} 밟는다가‖ W− W′‖ ◻ ≤ ϵ{\displaystyle\lVert W-W'\rVert_{\square}\leq \eps 있다.ilon$}$.

그러나 그것은 강한 규칙성 보조정리처럼 더 강한 규칙성 결과를 증명하는데 사용될 수 있다.

그래폰의 강력한 정규성 보조정리.For every sequence ${\displaystyle \mathbf {\epsilon } =(\epsilon _{0},\epsilon _{1},\dots )}$ of positive real numbers, there is a positive integer ${\displaystyle S}$ such that for every graphon ${\displaystyle W}$, there is a graphon ${\displaystyle W'}$ and a stepfunction ${\displaystyle U}$${\displaystyle U}$ with ${\displaystyle k<S}$ steps such that ${\displaystyle \lVert W-W'\rVert _{1}\leq \epsilon _{0}}$ and ${\displaystyle \lVert W'-U\rVert _{\square }\leq \epsilon _{k}.$$}$

강한 규칙성 보조정리 증명은 위의 Corolary 1과 개념적으로 유사하다.It turns out that every graphon ${\displaystyle W}$ can be approximated with a stepfunction ${\displaystyle U}$ in the ${\displaystyle L_{1}}$ norm, showing that the set of balls ${\displaystyle B_{1}(U,\epsilon _{0})}$ cover ${\displaystyle {\widetilde {\mathcal {$$W}}_{0$이러한 세트는 $\Delta {\displaystyle {}_{}}$ Δ ${\displaystyle {◻}_{}}$ ${\$ 메트릭에서는$$ 열리지 않지만, 약간 확대하여 열 수 있다.이제 우리는 유한한 서브커버를 가져갈 수 있고, 원하는 조건이 뒤따른다는 것을 보여줄 수 있다.

시도렌코의 추측

그래폰의 분석적 특성은 동형성 관련 불평등을 공격하는 데 있어 더 큰 유연성을 허용한다.

예를 들어, Sidorenko의 추측은 극단적 그래프 $이론$의 주요 개방적인 문제로서, $평균{\displaystyle }$ 도 $p{\displaystyle }$ ${\displaystyle n}$ ${\displaystyle pn}$의 정점$$($$일부 $p{\displaystyle }$ ${\displaystyle \in }$[ ${\displaystyle 0}$, ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle p\in [0,1$과 양분 그래프 $H{\displaystyle }$ ${\displaystystyle H}$에 대해 주장한다.H{H\displaystyle}G{G\displaystyle}에서 V{\displaystyle v}vertices과 e{\displaystyle e}가장자리, homomorphisms의 번호는 최소한 penv{\displaystyle p^{e}n^{v}}.[10]이기 때문에 수량은 기대 수의 표시 subgraphs의 H{H\displaystyle}에서 무작위로 추출한 그래프이다.${\displaystyle G}$( ${\displaystyle n}$, ${\displaystyle p}$) ${\displaystyle G(n,p$ 추측으로 해석할 수 있는 것은, 모든 양립자 $그래프{\displaystyle }$H {\$displaystyle$ H$\}$에 대해, 임의 그래프는 일정한 에지 밀도를 가진 모든 그래프에 $대해$ H ${\displaystyle H}$의 최소 복사 수를 달성(기대)한다는 주장으로 해석할 수 있다.

Sidorenko의 추측에 대한 많은 접근방식은 문제를 그래폰의 본질적인 불평등으로서 공식화하며, 이것은 다른 분석적 접근방식을 사용하여 문제를 공격할 수 있게 한다.^[11]

일반화

그래폰은 자연적으로 밀도가 높은 간단한 그래프와 연관되어 있다.조밀한 방향 가중 그래프에 대한 이 모델의 확장자가 있으며, 이를 흔히 장식된 그래프라고 한다.^[12]또한 랜덤 그래프 모델과 그래프 한계 이론의 양쪽 관점에서 희소 그래프 체계에 대한 최근의 확장도 있다.^[14][15]

참조