와츠-스트로가츠 모형

시리즈의 일부
네트워크 과학
이론.
그래프 복합망 전염 소세계 스케일 프리 커뮤니티 구조 퍼콜레이션 진화 제어가능성 그래프도면 사회적 자본 링크분석 최적화 호혜성 폐쇄 호모필리 감수성 우선첨부 균형이론 네트워크 효과 사회적 영향
네트워크 유형
정보(컴퓨팅) 텔레커뮤니케이션 운송 사회의 과학적 협업 생물학적 인공신경 상호의존적 시맨틱 공간의 의존 흐름 온칩의
그래프
특징들 클리크 요소 인하. 사이클 자료구조 가장자리 고리 이웃 경로. 꼭짓점 인접 목록 / 행렬 발생목록/행렬 종류들 초당파 완성하다 연출된 들뜬 라벨링 멀티 랜덤 가중
메트릭 알고리즘
중심성 도 모티프 클러스터링 정도분포 구색성 거리 모듈화 효율성.
모델들
위상 랜덤그래프 에르트 ő스 - 레니 바라바시-알베르트 비앙코니 바라바시 피트니스 모델 와츠-스트로가츠 지수난수(ERGM) 랜덤 기하학(RGG) 쌍곡선(HGN) 계층적 확률적 블록 블록모델링 최대 엔트로피 소프트 구성 LFR 벤치마크 역학 부울 네트워크 대리인 기반의 전염병/SIR
목록 분류
토픽 소프트웨어 네트워크 과학자 카테고리:네트워크 이론 카테고리:그래프이론
v t

Watts–Strogatz 모델은 짧은 평균 경로 길이와 높은 클러스터링을 포함한 소세계 속성의 그래프를 생성하는 랜덤 그래프 생성 모델입니다. 던컨 J. 와츠와 스티븐 스트로가츠가 1998년 네이처 과학 저널에 발표한 논문에서 제안했습니다.^[1] 이 모델은 Watts가 그의 인기 있는 과학 책 Six Degrees에서 $공식화$하기$$위해 $β${\displaystyle \$beta}$를 사용한 후 (Watts) 베타 모델로도 알려지게 되었습니다.

모형에 대한 이론적 근거

무작위 그래프에 대한 공식적인 연구는 Paul Erd ős와 Alfréd Rényi의 연구로 거슬러 올라갑니다. 그들이 고려한 그래프는 현재 고전 또는 Erd ős–Rényi(ER) 그래프로 알려져 있으며 많은 응용 분야에서 단순하고 강력한 모델을 제공합니다.

그러나 ER 그래프는 많은 실제 네트워크에서 관찰되는 두 가지 중요한 속성을 가지고 있지 않습니다.

1. 로컬 클러스터링 및 삼차 폐쇄를 생성하지 않습니다. 대신 ER 그래프는 두 노드가 연결될 확률이 일정하고 무작위적이며 독립적이기 때문에 군집화 계수가 낮습니다.
2. 그들은 허브의 형성을 설명하지 않습니다. 공식적으로 ER 그래프의 정도 분포는 많은 실제 규모가 없는 네트워크에서 관찰되는 거듭제곱 법칙이 아닌 포아송 분포로 수렴됩니다.^[3]

Watts and Strogatz 모델은 두 가지 한계 중 첫 번째 한계를 해결하는 가장 간단한 모델로 설계되었습니다. ER 모델의 짧은 평균 경로 길이를 유지하면서 클러스터링을 설명합니다. ER 그래프에 가까운 무작위 구조와 규칙적인 고리 격자 사이를 보간하여 수행합니다. 결과적으로, 이 모델은 전력망, 예쁜꼬마선충의 신경망, 영화 배우의 네트워크 또는 신진 효모의 지방 대사 통신과 같은 다양한 네트워크에서 "작은 세상" 현상을 적어도 부분적으로 설명할 수 있습니다.^[4]

알고리즘.

Given the desired number of nodes ${\displaystyle N}$, the mean degree ${\displaystyle K}$ (assumed to be an even integer), and a parameter ${\displaystyle \beta }$, all satisfying ${\displaystyle 0\leq \beta \leq 1}$ and ${\displaystyle N\gg K\gg \ln N\gg 1}$, $이{\displaystyle }$ 모델은 N개의 ${\displaystyle N}$개의$$ 노드와 ${\displaystyle \frac{}{}}$의 ${\$ {$NK}{2}}$개의$$ 모서리를 가진 무방향 그래프를 다음과 같이 구성합니다.

1. $N개$의 ${\$$displaystyle$ $N}$개의$$ 노드가 각각$$K {\$displaystyle$ K$}$개의 $이웃$, K / 2 {\displaystyle K/$2}$의 각 면에 연결된 그래프인 정규 링 격자를 구성합니다$.$ That is, if the nodes are labeled ${\displaystyle 0\ldots {N-1}}$, there is an edge ${\displaystyle (i,j)}$ if and only if ${\displaystyle 0< i-j \ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.}$
2. 모든 노드 $i$ = $…,$ N - 1 {\$displaystyle$ i = 0,\ dots,{N-1}}에 대해 i {\$displaystyle$ i}를 K/2$${\displaystyle K/2}에${\displaystyle 연결}$하는 모든 에지, 즉 모든 에지 (i, j) {\displaystyle (i,$j)}$ such that ${\displaystyle 0<(j-i)\ \mathrm {mod} \ N\leq K/2}$, and rewire it with probability ${\displaystyle \beta }$. Rewiring is done by replacing ${\displaystyle (i,j)}$ with ${\displaystyle (i,$$k)$$$서$k$ {\$displaystyle$k}은(는)${\displaystyle }$자체 $loops$을 피하면서 모든 가능한 노드에서 임의로 균일하게 선택됩니다$($k$$$≠$$i$ {\displaystyle k\n).$eqi$ 및 링크 복제(알고리즘의 이 $시점$에는 k${\displaystyle {}^{}}$$=$ ${\displaystyle k}$ ${\$displaystyle k'$=$ k}인 에지$$(${\displaystyle i,}$ ${\displaystyle k\text{'})}$ ${\displaystyle ($i$,$ ${k'})$가 없습니다.

특성.

모델의 기본 격자 구조는 로컬로 클러스터링된 네트워크를 생성하는 반면 무작위로 다시 연결된 링크는 평균 경로 길이를 극적으로 줄입니다. 알고리즘은 이러한 비격자 에지의$$ $\beta {\displaystyle }$ ${\displaystyle \frac{\mathrm{NK}}{}}$ ${\displaystyle \frac{\mathrm{}}{}}$ ${\$에 대해 소개합니다. Varying ${\displaystyle \beta }$ makes it possible to interpolate between a regular lattice (${\displaystyle \beta =0}$) and a structure close to an Erdős–Rényi random graph ${\displaystyle G(N,p)}$ with ${\displaystyle p={\frac {K}{N-1}}}$ at ${\displaystyle \beta =1}$. 모든 노드가 적어도 $K{\displaystyle /2\mathrm{}}$ ${\displaystyle K/2}$개의$$ 다른 노드에 연결되기 때문에 실제 ER 모델에는 접근하지 않습니다.

관심 있는 세 가지 속성은 평균 경로 길이, 군집화 계수 및 정도 분포입니다.

평균경로길이

링 격자의 경우 평균 경로 길이는${\displaystyle }$ℓ (${\displaystyle 0)}$ ≈ N / 2 K ≫ $1${\$displaystyle$ \$ell$ $($0)\approx N/2K\gg 1}이며 시스템 크기에 따라 선형으로 확장됩니다. ${\displaystyle \mathrm{\beta }}$ → 1 $\{\backslash$displaystyle \beta$$\rightarrow$$1}의 제한적인 경우, 그래프는 실제 수렴하지 않으면서 ℓ (1) ≈ ln ⁡ N ln ⁡ K {\displaystyle \ell (1)\approx {\frac {\ln N}{\ln K}}를 사용하여 랜덤 그래프에 접근합니다. 중간 영역 < < ${\displaystyle 0<\beta$< $1$에서 평균 경로 길이는 $\beta {\displaystyle }$ ${\displaystyle \beta}$가 증가함에 따라 매우 빠르게$$감소하여 제한 값에 빠르게 접근합니다.

군집계수

For the ring lattice the clustering coefficient^[5] ${\displaystyle C(0)={\frac {3(K-2)}{4(K-1)}}}$, and so tends to ${\displaystyle 3/4}$ as ${\displaystyle K}$ grows, independently of the system size.^[6] ${\displaystyle \mathrm{\beta }}$ → 1 $\{\backslash$displaystyle \ beta \rightarrow 1}의 한계 경우 클러스터링 계수는 고전적인 랜덤 그래프의 클러스터링 계수인 C = K / (N-1) {\displaystyle C = K / (N-1)}와 같은 순서이므로 시스템 크기에 반비례합니다. 중간 영역에서 클러스터링 계수는 일반 격자에 대한 값에 상당히 가깝게 유지되며 상대적으로 높은 $\beta {\displaystyle }$ ${\displaystyle \beta}$에서만 떨어집니다$.$ 따라서 평균 경로 길이는 빠르게 떨어지지만 클러스터링 계수는 그렇지 않은 영역이 발생하여 "작은 세계" 현상을 설명합니다.

${\displaystyle C{\text{'}(}^{}}$β)를 클러스터링하기 위해 Barrat and Weigt^[6]$$측도를 사용하면$$노드의 이웃 간의 평균 에지 수와 이러한 이웃 간의 평균 가능한 에지 수 사이의 $분수$로 정의되거나,$또는$ 다음과 같이,

${\displaystyle C'(\beta )\equiv {\frac {3\times {text{number of triangle}}{\text{number of connected triple}}}$

$그런{\displaystyle {}^{}}$ 다음 C${\displaystyle {\text{'}}^{}}$(${\displaystyle \beta )}$~ ${\displaystyle C}$ ${\displaystyle (0)}$(${\displaystyle 1}$- ${\displaystyle \beta {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle C'$ (\$beta )\sim C(0)$ ($1-\beta )^{3}$를 얻습니다.

정도분포

고리 격자의 경우 차수 분포는 $단지{\displaystyle }$ K$${\$displaystyle$ K$}$를 중심으로 하는 디랙 델타 함수입니다$.$ 많은 수의 와 0< < ${\displaystyle 0<\beta$< $1}$에 대한 차수 분포는 다음과 같이 쓸 수 있습니다.^[6]

${\displaystyle P(k)\approx \sum _{n=0}^{f(k,K)}{{K/2} \choose {n}}(1-\beta )^{n}\beta ^{K/2-n}{\frac {(\beta K/2)^{k-K/2-n}}{(k-K/2-n)!}}e^{-\beta K/2}}$

여기서 ${\displaystyle {ki}_{}}$ ${\$는 ${\$ i$^{\text{th}}$ ${\displaystyle {\text{노드}}^{}}$가 그 정도를 가지는 간선의 수이다$$. ${\displaystyle 여기}$서 ≥ K / 2 ${\displaystyle$k$\backslash$geq K/$2$},${\displaystyle f}$ (${\displaystyle k,}$ K ) = ${\displaystyle \min (k}$- K$$/ ${\displaystyle 2}$, K / 2) {\displaystyle f(k, K) =\min(k-K/2, K/2)}. 정도 분포의 모양은 랜덤 그래프와 유사하며 $k$ = ${\$displaystyle k=$K}$에서 뚜렷한 피크를 가지며 큰 k - K {\displaystyle $k-K$}에 대해 지수 함수적으로 감소합니다. 네트워크의 토폴로지는 비교적 균질하며, 이는 모든 노드의 정도가 비슷하다는 것을 의미합니다.

한계

모델의 가장 큰 한계는 비현실적인 정도 분포를 생성한다는 것입니다. 대조적으로, 실제 네트워크는 종종 규모가 없는 네트워크이며, 허브와 규모가 없는 정도의 분포를 가지고 있습니다. 이러한 네트워크는 Barabási-Albert(BA) 모델과 같은 우선 부착 모델군에 의해 그러한 측면에서 더 잘 설명됩니다. (반면 Barabási-Albert 모델은 실제 네트워크에서 볼 수 있는 높은 수준의 클러스터링을 생성하지 못하며, 이는 Watts and Strogatz 모델이 공유하지 못하는 단점입니다. 따라서 Watts and Strogatz 모형이나 Barabási-Albert 모형 모두 완전히 현실적인 것으로 간주해서는 안 됩니다.)

또한 Watts and Strogatz 모델은 고정된 노드 수를 의미하므로 네트워크 성장을 모델링하는 데 사용할 수 없습니다.

참고 항목

• 소규모 네트워크
• Erdős–Rényi (ER) model
• 바라바시-알베르트 모형
• 소셜 네트워크

참고문헌