Erdős–Rényi model

그래프 이론의 수학 분야에서 Erd ős-Rényi 모델은 랜덤 그래프를 생성하거나 랜덤 네트워크의 진화를 위해 밀접하게 관련된 두 가지 모델 중 하나를 말합니다. 이 모델들은 1959년에 모델들 중 하나를 소개한 헝가리 수학자 폴 에르트 ő스와 알프레드 레니의 이름을 따서 지어졌습니다. Edgar Gilbert는 Erd ő와 Rényi와 동시에 독립적으로 다른 모델을 소개했습니다. Erd ő와 Rényi의 모형에서, 고정된 수의 간선을 갖는 고정된 정점 집합의 모든 그래프는 동등하게 가능성이 있습니다. Erd ős–Rényi–Gilbert 모델이라고도 불리는 Gilbert가 도입한 모델에서 각 간선은 다른 간선과 독립적으로 존재하거나 존재하지 않을 고정된 확률을 가집니다. 이러한 모델은 다양한 속성을 만족하는 그래프의 존재를 증명하거나 속성이 거의 모든 그래프에 대해 보유하는 것이 무엇을 의미하는지에 대한 엄격한 정의를 제공하기 위해 확률론적 방법에 사용될 수 있습니다.

정의.

Erd ő-Rényi 랜덤 그래프 모델에는 밀접하게 관련된 두 가지 변형이 있습니다.

$G(n,M)$ $G(n,M)$ ${\displaystyle$ G $(n,$ M $)}$ 모델에서는 $G(n,M)$ $n$ 의 $n$ 개의 $n$ 노드와 $M$ 의{\ $displaystyle$ M $}$ 개의 $M$ 간선을 갖는 모든 그래프의 집합에서 그래프가 임의로 균일하게 선택됩니다. 노드는 레이블로 지정된 것으로 간주되며, 이는 정점을 순열함으로써 서로에게서 얻은 그래프가 서로 구별되는 것으로 간주된다는 것을 의미합니다. 예를 들어, $G(3,2)$ 2 $G(3,2)$ ${\displaystyle$ G $(3, 2)}$ 모델에서는 $G(3,2)$ 레이블이 지정된 3개의 정점(2-edge 경로에서 중간 정점을 선택할 때마다 하나씩)에 3개의 2-edge 그래프가 있으며, 이 3개의 그래프 각각은 ${\tfrac {1}{3}}$ {\displaystyle ${\tfrac {1}{3}}$ 과 함께 포함됩니다 ${\tfrac {1}{3}}$
$G(n,p)$ $G(n,p)$ ${\displaystyle G(n,$ p $)}$ 모형에서는 $G(n,p)$ 레이블이 지정된 노드를 무작위로 연결하여 그래프를 구성합니다. 각 간선은 다른 모든 간선과 독립적으로 $p$ 확률 $p {\displaystyle$ p $}$ 인 그래프에 포함됩니다. 마찬가지로 $n$ 의 $n$ 개의 $n$ 노드와 $M$ 의 ${\displaystyle$ M $}$ 개의 $M$ 간선을 갖는 각 그래프를 생성할 확률은 $p^{M}(1-p)^{{n \선택 2}-M}$ $이$ 모델의 $p$ 파라미터 $p$ $p$ 는 가중치 함수로 생각할 수 있습니다. p $p$ 가 $0$ $0$ 에서 $0$ 1 ${\displaystyle$ 1 $}$ 로 증가함에 $p$ $1$ 따라 모델은 점점 더 많은 에지를 가진 그래프를 포함하고 더 적은 에지를 가진 그래프를 포함할 가능성이 점점 더 낮아집니다. 특히, $p={\tfrac {1}{2}}$ p = $p={\tfrac {1}{2}}$ {\ $displaystyle$ p = {\tfrac {1}{2}}는 n {\displaystyle n}개 정점의 2개(n 2) {\displaystyle 2^{\binom {n}{2}}개 그래프가 모두 동일한 확률로 선택된 경우에 해당합니다.

랜덤 그래프의 동작은 정점의 $n$ n {\ $displaystyle n}$ 이 무한대인 경우에 종종 연구됩니다. $p$ 경우 p ${\displaystyle$ $p$ $}$ 와 $M$ ${\displaystyle$ M $}$ 을(를) 고정할 수 있지만 $,$ n ${\displaystyle$ n}에 따라 함수가 $n$ 될 수도 있습니다. $예$ 를 들어 $G(n,2\ln(n)/n)$ $G(n,2\ln(n)/n)$ ( $G(n,2\ln(n)/n)$ 2 ln ⁡ $($ 2\ln(n))/n}의 거의 모든 그래프가 연결되어 있다는 문장은 다음을 의미합니다. $n$ $n$ 이 무한대로 갈수록 에지 $2\ln(n)/n$ 이 2 $2\ln(n)/n$ ⁡( $2\ln(n)/n$ ) / $n$ ${\displaystyle 2\$ ln(n)/n}인 $n$ ${\displaystyle$ n $}$ 정점의 그래프가 1 ${\displaystyle$ 1 $}$ 로 연결될 확률이 높습니다.

두 모형의 비교

G(n, p)의 예상 간선 수는 ${\tbinom {n}{2}}p$ ( ${\tbinom {n}{2}}p$ ${\tbinom {n}{2}}p$ p ${\tbinom {n}{2}}p$ 이며 ${\tbinom {n}{2}}p$ 큰 수의 법칙에 의해 G(n, p)의 그래프는 거의 틀림없이 이와 같은 수의 간선을 가질 것입니다(예상 간선 수가 무한대인 경우). 따라서 대략적인 휴리스틱은 pn → ∞이면 G(n, p)는 N이 $M={\tbinom {n}{2}}p$ 에 $M={\tbinom {n}{2}}p$ 따라 M = (n 2) p {\displaystyle M = {\tbinom {n}{2}}인 G( $M={\tbinom {n}{2}}p$ , M)와 유사하게 동작해야 한다는 것입니다.

많은 그래프 속성의 경우 이와 같습니다. 만약 P가 부분 그래프 순서와 관련하여 단조로운 그래프 속성이라면 (A가 B의 부분 그래프이고 B가 P를 만족하면 A도 P를 만족한다는 것을 의미함), "P는 G(n, p)의 거의 모든 그래프에 대해 성립한다."와 " $G(n,{\tbinom {n}{2}}p)$ 는 G $G(n,{\tbinom {n}{2}}p)$ ( $G(n,{\tbinom {n}{2}}p)$ ) $G(n,{\tbinom {n}{2}}p)$ p)의 거의 모든 그래프에 대해 성립한다." ${\display$ G $(n,$ ${\tbinom {n}{2$ 은(는) 동등합니다(제공된 pn $→$ $∞$ ). 예를 들어, P가 연결된 성질인 경우 또는 P가 해밀턴 사이클을 포함하는 성질인 경우 이 값은 성립합니다. 그러나 이것은 반드시 비모노톤 속성(예: 짝수 개의 모서리를 가지는 속성)에 대해서만 유지되는 것은 아닙니다.

실제로 G(n, p) 모델은 오늘날 더 일반적으로 사용되는 모델이며, 이는 부분적으로 모서리의 독립성에 의해 허용되는 분석의 용이성 때문입니다.

G(n, p)의 성질

위의 표기법을 사용하면 G(n, p)의 그래프는 평균적으로 ${\tbinom {n}{2}}p$ ${\tbinom {n}{2}}p$ ${\tbinom {n}{2}}p$ ${\displaystyle {\tbinom {n}{2}}개$ 의 $\tbinom{n}{2} p$ 모서리를 갖습니다. 특정 정점의 정도 분포는 이항입니다.^[5]

P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},

여기서 n은 그래프의 총 정점 수이다. 부터

P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\text{ as}}\n\text{ and }}np={\text{constant}}

이 분포는 큰 n과 np = const에 대한 포아송입니다.

1960년 논문에서 에르트 ő스와 레니는 다양한 p 값에 대한 G(n, p)의 행동을 매우 정확하게 설명했습니다. 그들의 결과는 다음과 같습니다.

np < 1인 경우, G(n, p)의 그래프는 O(log(n))보다 큰 크기의 연결 성분이 거의 확실하게 없습니다.
np = 1이면 G(n, p)의 그래프는 크기가 n인 가장 큰 성분을 가질 것이 거의 확실합니다.
np → c > 1(여기서 c는 상수)이면 G(n, p)의 그래프는 거의 확실하게 정점의 양의 비율을 포함하는 고유한 거대 성분을 가질 것입니다. 다른 구성 요소에는 O(log(n)개 이상의 정점이 포함되지 않습니다.
$p<{\tfrac {(1-\varepsilon )\ln n}{n}}$ < $p<{\tfrac {(1-\varepsilon )\ln n}{n}}$ ( $p<{\tfrac {(1-\varepsilon )\ln n}{n}}$ - $p<{\tfrac {(1-\varepsilon )\ln n}{n}}$ ε) $p<{\tfrac {(1-\varepsilon )\ln n}{n}}$ 이 n ${\displaystyle$ p<{\ $tfrac {(1-\varepsilon$ ln}{n $}}$ 인 경우, G(n, p)의 그래프는 거의 확실하게 고립된 정점을 포함하므로 연결이 끊어집니다.
$p>{\tfrac {(1+\varepsilon )\ln n}{n}}$ p $p>{\tfrac {(1+\varepsilon )\ln n}{n}}$ > ( $p>{\tfrac {(1+\varepsilon )\ln n}{n}}$ + $p>{\tfrac {(1+\varepsilon )\ln n}{n}}$ ε $p>{\tfrac {(1+\varepsilon )\ln n}{n}}$ $p>{\tfrac {(1+\varepsilon )\ln n}{n}}$ 이 $n$ {\ $displaystyle$ p>{\ $tfrac {(1+\varepsilon$ ln}{n}}일 때, G(n, p)의 그래프는 거의 확실하게 연결될 것입니다.

따라서 ${\tfrac {\ln n}{n}}$ ⁡ $n {\displaystyle {\tfrac {\ln$ }{n}}은 G(n, p)의 연결에 대한 날카로운 임계값입니다.

그래프의 추가 특성은 n이 무한대인 경향이 있기 때문에 거의 정확하게 설명할 수 있습니다. 예를 들어, K(n)(대략 2log₂(n))가 있으므로 G(n, 0.5)에서 가장 큰 클릭은 크기 k(n) 또는 k(n) + 1을 가질 수 있습니다.^[7]

따라서 그래프에서 가장 큰 클릭의 크기를 찾는 것이 NP-완전한 것임에도 불구하고, (이 모델에 따르면) "일반적인" 그래프에서 가장 큰 클릭의 크기는 매우 잘 알려져 있습니다.

Erdos-Renyi 그래프의 에지-듀얼 그래프는 정도 분포가 거의 비슷하지만, 정도 상관 관계가 있고 군집화 계수가 상당히 높은 그래프입니다.^[8]

침투와의 관계

침투 이론에서는 유한 또는 무한 그래프를 검사하고 가장자리(또는 링크)를 무작위로 제거합니다. 따라서 Erd ős-Rennyi 프로세스는 전체 그래프에서 실제로 가중치가 없는 링크 퍼콜레이션입니다. (하나는 노드 및/또는 링크가 가중치 퍼콜레이션으로 이질적인 가중치로 제거된 퍼콜레이션을 말합니다.) 퍼콜레이션 이론은 물리학에 많은 뿌리를 두고 있기 때문에 수행된 연구의 대부분은 유클리드 공간의 격자에 관한 것이었습니다. np = 1에서 거대 성분에서 작은 성분으로의 전이는 이러한 그래프에 대한 유사점을 갖지만 격자의 경우 전이점을 결정하기가 어렵습니다. 물리학자들은 종종 전체 그래프에 대한 연구를 평균 장 이론이라고 말합니다. 따라서 Erd ős-Rennyi 과정은 평균 필드 퍼콜레이션 사례입니다.

무작위 그래프에 대한 퍼콜레이션에 대해서도 몇 가지 중요한 작업이 수행되었습니다. 물리학자의 관점에서 이것은 여전히 평균 필드 모델일 것이므로 연구의 정당성은 종종 통신 네트워크로 간주되는 그래프의 견고성 측면에서 공식화됩니다. 평균 $차수$ ⟨ k ⟩가 ${\displaystyle$ \langle k\rangle }인 n개의 ≫ 1 노드의 랜덤 그래프가 주어졌을 때, 노드의 $일부$ 1 - $1-p'$ p' {\displaystyle 1-p'}를 $1-p'$ $p'$ 하고 네트워크에서 $일부$ p' {\displaystyle p'}만남깁니다. 임계 퍼콜레이션 임계값 $p'_{c}={\tfrac {1}{\langle k\rangle }}$ = $1$ ⟨ k ⟩ {\ $displaystyle$ p'_{c} = {\tfrac {1}{\langlek\rangle}} 아래에 있으며 pc' {\displaystyle p'_{c} 위에 연결된 거대한 구성 요소가 존재합니다. 거대 성분의 상대적인 크기인_∞ P는 다음과^[6]^[1]^[2]^[9] 같이 주어집니다.

P_{\infty}=p'[1-\exp (-\langlek\rangle P_{\infty})].\,

주의사항

G(n, p) 모델의 두 가지 주요 가정(엣지가 독립적이고 각 에지가 동등하게 가능성이 있음)은 특정 실제 현상을 모델링하는 데 부적절할 수 있습니다. Erd ő–Rennyi 그래프는 많은 소셜 네트워크와 달리 클러스터링이 낮습니다. 일부 모델 대안으로는 Barabási-Albert 모델과 Watts and Strogatz 모델이 있습니다. 이러한 대체 모델은 침투 과정이 아니라 각각 성장 및 재배선 모델을 나타냅니다. 많은 실제 현상을 재현할 수 있는 또 다른 랜덤 그래프 모델 제품군은 지수 랜덤 그래프 모델입니다.

역사

G(n, p) 모델은 위에서 언급한 연결 임계값을 연구하는 1959년 논문에서 Edgar Gilbert에 의해 처음 소개되었습니다.^[3] G(n, M) 모델은 Erd ő와 Rennyi가 1959년 논문에서 소개했습니다. Gilbert와 마찬가지로, 그들의 첫 번째 조사는 G(n, M)의 연결성에 관한 것이었고, 더 자세한 분석은 1960년에 이어졌습니다.

임계 G(n, p)의 연속체 한계 표현

A continuum limit of the graph was obtained when $p$ is of order $1/n$ .^[11] Specifically, consider the sequence of graphs $G_{n}:=G(n,1/n+\lambda n^{-{\frac {4}{3}}})$ for $\lambda \in \mathbb {R}$ . 한계 객체는 다음과 같이 구성할 수 있습니다.

먼저 확산 $W^{\lambda }(t):=W(t)+\lambda t-{\frac {t^{2}}{2}}$ λ(t $W^{\lambda }(t):=W(t)+\lambda t-{\frac {t^{2}}{2}}$ = W $W^{\lambda }(t):=W(t)+\lambda t-{\frac {t^{2}}{2}}$ ) + $W^{\lambda }(t):=W(t)+\lambda t-{\frac {t^{2}}{2}}$ λ t - t 22 ${\displaystyle$ W^{\lambda}(t): $=W(t$ )+\lambdat- ${\$ frac {t^{2}}{2}} 여기서 W {\displaystyle W}는 표준 브라운 운동입니다.
이 프로세스로부터 반사된 프로세스 $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$ λ(t $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$ = $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$ W $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$ λ( $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$ - $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$ ∈ [0, t] W $R^{\lambda }(t):=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}W^{\lambda }(s)$ λ $(s)$ {\displaystyle R^{\lambda}(t): $=W^{\lambda }(t)-\inf \limits _{s\in [0,t]}$ $W^{\lambda }(s)}$ . 이 과정은 많은 연속적인 여행(브라운 여행은 아님)을 포함하는 것으로 볼 수 있습니다. $W^{\lambda }$ λ ${\displaystyle$ W $^{\$ lambda }}의 드리프트는 - $-{\frac {t^{2}}{2}}$ t $22 {\displaystyle -{\frac {t^{$ 2 $-{\frac {t^{2}}{2}}$ 2}}에 $-{\frac {t^{2}}{2}}$ 지배되기 때문에 이러한 이동은 t $t\to +\infty$ → + $t\to +\infty$ ∞ {\ $displaystyle$ t\to +\infty}에 따라 점점 $t\to +\infty$ . 특히, 길이가 감소하는 순서로 정렬할 수 있습니다. R $\mathbb {R}$ 을 간격 $(C_{i})_{i\in \mathbb {N} }$ 으로 분할할 수 있습니다. ∈ N ${\displaystyle (C_{i})$ _{i $\in \mathbb$ {N}}}에서 길이가 $R^{\lambda }$ 하여 R λ ${\displaystyle$ R^{\lambda }}는 $Ci {\displaystyle$ C_{i}}로 $C_{i}$ 됩니다 $.$ $\mathbb$ {N}의 $임의의 i$ ∈ N ${\displaystyle$ i\에 대한 익스포크.
$(e(s))_{s\in [0,1]}$ ( $(e(s))_{s\in [0,1]}$ ( $(e(s))_{s\in [0,1]}$ 의 $(e(s))_{s\in [0,1]}$ ∈ [0 $(e(s))_{s\in [0,1]}$ 1] {\ $displaystyle (e(s))_{s\$ in $(e(s))_{s\in [0,1]}$ [0,1]}을 생각해 보십시오. 랜덤 그래프를 다음과 같이 구성합니다.
브라운 여행 $(e(t))_{t\in [0,1]}$ $(e(t))_{t\in [0,1]}$ ∈ $(e(t))_{t\in [0,1]}$ [0 $,$ 1] ${\displaystyle ($ e(t)) $_{t\in [0,1$ 여기서 프로세스 $\Xi$ $ξ$ ${\$ displaystyle \Xi}는 빨간색 점으로 표시된 단일 점이 있습니다. 빨간색 선은 연관된 트리 $T_{e}$ ${\$ 의 단일 내부 노드에 해당하고 $T_{e}$ 녹색 선은 $T_{e}$ ${\$ 의 리프에 해당합니다 $T_{e}$ 두 노드 사이에 에지를 추가하면 한 사이클의 그래프를 얻을 수 있습니다.
- 실제 트리 $T_{e}$ Te ${\$ 브라운 트리 참조).
- 단위 강도를 가진 $[0,1]\times \mathbb {R} _{+}$ [0 $]$ × R + ${\displaystyle [$ 0, 1 $]\times \mathbb {$ R} _{+}의 $[0,1]\times \mathbb {R} _{+}$ 포아송 점 프로세스 $\Xi$ ξ ${\displaystyle \$ $[0,1]\times \mathbb {R} _{+}$ }를 고려합니다. x ≤ e (s) {\displaystyle x\leeq(s)} $인$ \Xi }의 각 점 (x $(x,s)\in \Xi$ s $(x,s)\in \Xi$ ∈ ξ ${\$ displaystyle (x,s)\에 대해 Te {\displaystyle T_{e}의 기본 내부 노드 및 리프에 대응합니다. 두 정점을 식별하면, $T_{e}$ $T_{e}$ 가 $\Gamma _{e}$ γ $e {\$ displaystyle $\Gamma$ _ ${$ e}}

$(\Gamma _{i})_{i\in \mathbb {N} }$ 절차를 적용하면 $(\Gamma _{i})_{i\in \mathbb {N} }$ ∈ i) $(\Gamma _{i})_{i\in \mathbb {N} }$ i γ N ${\displaystyle(\Gamma$ _{ $i})_{i\$ in $(\Gamma _{i})_{i\in \mathbb {N} }$ \mathbb {N}}}에서 크기가 감소하는 무작위 무한 그래프 시퀀스를 얻을 수 있습니다. 이 정리는 이 그래프가 $n$ → + $n\to +\infty$ ∞ ${\displaystyle$ n\to $n\to +\infty$ infty}로서 $G_{n}$ {\ $displaystyle G_{n}}$ 의 극한 객체에 어떤 의미에서 대응한다는 것을 말합니다.

참고 항목

Rado 그래프 – 모든 셀 수 있는 그래프를 포함하는 무한 그래프로, G(n, p) 모델을 셀 수 있는 무한개의 정점을 가진 그래프로 확장하여 형성된 그래프입니다. 유한한 경우와는 달리, 이 무한한 과정의 결과는 (확률 1인) 동일한 그래프로 동형입니다.
이중 단계 진화 – 복잡한 적응 시스템 내에서 자기 조직화를 주도하는 프로세스는 Erd ős-Rennyi 모델과 관련된 속성이 시스템의 질서 출현에 기여하는 방법을 설명합니다.
지수 랜덤 그래프 모델 – 네트워크 분석을 위한 통계 모델 하는 페이지는 네트워크 통계 및 이와 관련된 다양한 파라미터가 주어진 "n" 노드에 대한 그래프의 일반적인 확률 분포를 설명합니다.
잠재적 커뮤니티 구조를 가진 그래프에 대한 Erd ő-Rennyi 모델의 일반화인 확률적 블록 모델
Watts–Strogatz 모형 – 랜덤 소세계 그래프 생성 방법
Barabási – Albert 모형 – 스케일 프리 네트워크 생성 알고리즘

참고문헌

^ ^a ^b Erdős, P.; Rényi, A. (1959). "On Random Graphs. I" (PDF). Publicationes Mathematicae. 6 (3–4): 290–297. doi:10.5486/PMD.1959.6.3-4.12. S2CID 253789267. Archived (PDF) from the original on 2020-08-07. Retrieved 2011-02-23.
^ ^a ^b Bollobás, B. (2001). Random Graphs (2nd ed.). Cambridge University Press. ISBN 0-521-79722-5.
^ ^a ^b Gilbert, E.N. (1959). "Random Graphs". Annals of Mathematical Statistics. 30 (4): 1141–1144. doi:10.1214/aoms/1177706098.
^ Fienberg, Stephen E. (2012). "A brief history of statistical models for network analysis and open challenges". Journal of Computational and Graphical Statistics. 21 (4): 825–839. doi:10.1080/10618600.2012.738106. MR 3005799. S2CID 52232135.
^ Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64 (2): 026118. arXiv:cond-mat/0007235. Bibcode:2001PhRvE..64b6118N. doi:10.1103/PhysRevE.64.026118. PMID 11497662. S2CID 360112.Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64 (2): 026118. arXiv:cond-mat/0007235. Bibcode:2001PhRvE..64b6118N. doi:10.1103/PhysRevE.64.026118. PMID 11497662. S2CID 360112.식 (1)
^ ^a ^b 여기서 사용되는 확률 p는 $N(n)={\tbinom {n}{2}}p$ = $N(n)={\tbinom {n}{2}}p$ ( $N(n)={\tbinom {n}{2}}p$ 2 $)$ p {\displaystyle N(n) = {\tbinom {n}{2}} $p}$ 를 의미합니다.
^ Matula, David W. (February 1972). "The employee party problem". Notices of the American Mathematical Society. 19: A-382.
^ Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (April 2003). "Generating correlated networks from uncorrelated ones". Physical Review E. 67 (4): 046107. arXiv:cond-mat/0212469. Bibcode:2003PhRvE..67d6107R. doi:10.1103/PhysRevE.67.046107. PMID 12786436. S2CID 33054818.
^ Bollobás, B.; Erdős, P. (1976). "Cliques in Random Graphs". Mathematical Proceedings of the Cambridge Philosophical Society. 80 (3): 419–427. Bibcode:1976MPCPS..80..419B. doi:10.1017/S0305004100053056. S2CID 16619643.
^ Saberi, Abbas Ali (March 2015). "Recent advances in percolation theory and its applications". Physics Reports. 578: 12. arXiv:1504.02898. Bibcode:2015PhR...578....1S. doi:10.1016/j.physrep.2015.03.003. S2CID 119209128. Retrieved 30 January 2022.
^ ^a ^b Addario-Berry, L.; Broutin, N.; Goldschmidt, C. (2012-04-01). "The continuum limit of critical random graphs". Probability Theory and Related Fields. 152 (3): 367–406. doi:10.1007/s00440-010-0325-4. ISSN 1432-2064. S2CID 253980763.
^ Aldous, David (1997-04-01). "Brownian excursions, critical random graphs and the multiplicative coalescent". The Annals of Probability. 25 (2). doi:10.1214/aop/1024404421. ISSN 0091-1798. S2CID 16578106.

문학.

West, Douglas B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall. ISBN 0-13-014400-2.
Newman, M. E. J. (2010). Networks: An Introduction. Oxford.

웹 링크

영상 : 에르도스-레니 랜덤 그래프

[er59-1] Erdős, P.; Rényi, A. (1959). "On Random Graphs. I" (PDF). Publicationes Mathematicae. 6 (3–4): 290–297. doi:10.5486/PMD.1959.6.3-4.12. S2CID 253789267. Archived (PDF) from the original on 2020-08-07. Retrieved 2011-02-23.

[b01-2] Bollobás, B. (2001). Random Graphs (2nd ed.). Cambridge University Press. ISBN 0-521-79722-5.

[g59-3] Gilbert, E.N. (1959). "Random Graphs". Annals of Mathematical Statistics. 30 (4): 1141–1144. doi:10.1214/aoms/1177706098.

[4] Fienberg, Stephen E. (2012). "A brief history of statistical models for network analysis and open challenges". Journal of Computational and Graphical Statistics. 21 (4): 825–839. doi:10.1080/10618600.2012.738106. MR 3005799. S2CID 52232135.

[5] Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64 (2): 026118. arXiv:cond-mat/0007235. Bibcode:2001PhRvE..64b6118N. doi:10.1103/PhysRevE.64.026118. PMID 11497662. S2CID 360112.Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64 (2): 026118. arXiv:cond-mat/0007235. Bibcode:2001PhRvE..64b6118N. doi:10.1103/PhysRevE.64.026118. PMID 11497662. S2CID 360112.식 (1)

[Erdos1960-6] 여기서 사용되는 확률 p는 $N(n)={\tbinom {n}{2}}p$ = $N(n)={\tbinom {n}{2}}p$ ( $N(n)={\tbinom {n}{2}}p$ 2 $)$ p {\displaystyle N(n) = {\tbinom {n}{2}} $p}$ 를 의미합니다.

[7] Matula, David W. (February 1972). "The employee party problem". Notices of the American Mathematical Society. 19: A-382.

[8] Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (April 2003). "Generating correlated networks from uncorrelated ones". Physical Review E. 67 (4): 046107. arXiv:cond-mat/0212469. Bibcode:2003PhRvE..67d6107R. doi:10.1103/PhysRevE.67.046107. PMID 12786436. S2CID 33054818.

[9] Bollobás, B.; Erdős, P. (1976). "Cliques in Random Graphs". Mathematical Proceedings of the Cambridge Philosophical Society. 80 (3): 419–427. Bibcode:1976MPCPS..80..419B. doi:10.1017/S0305004100053056. S2CID 16619643.

[10] Saberi, Abbas Ali (March 2015). "Recent advances in percolation theory and its applications". Physics Reports. 578: 12. arXiv:1504.02898. Bibcode:2015PhR...578....1S. doi:10.1016/j.physrep.2015.03.003. S2CID 119209128. Retrieved 30 January 2022.

[:0-11] Addario-Berry, L.; Broutin, N.; Goldschmidt, C. (2012-04-01). "The continuum limit of critical random graphs". Probability Theory and Related Fields. 152 (3): 367–406. doi:10.1007/s00440-010-0325-4. ISSN 1432-2064. S2CID 253980763.

[12] Aldous, David (1997-04-01). "Brownian excursions, critical random graphs and the multiplicative coalescent". The Annals of Probability. 25 (2). doi:10.1214/aop/1024404421. ISSN 0091-1798. S2CID 16578106.

[5]

[7]

[8]

[6]

[1]

[2]

[9]

[3]

[11]

Search